Как (или почему) `Data.Set String` не является единственным типом? - PullRequest
Новая
       35

Как (или почему) `Data.Set String` не является единственным типом?

0 голосов
/ 31 января 2019

Я изучаю Хаскель трудным путем, пытаясь написать что-то, что мне кажется интересным, и сейчас я пытаюсь выяснить, как получить полукольцо в Хаскеле для определенного набора проблем синтаксического анализа: 

class Semiring s where
    zero, one :: s
    mul, add  :: s -> s -> s

instance Semiring Bool where
    zero = False
    one = True
    add = (||)
    mul = (&&)

instance Semiring (Set String) where
    zero    = empty 
    one     = singleton ""
    add a b = union a b
    mul a b = Data.Set.map (\(c, d) -> c ++ d) $ cartesianProduct a b

Версия Bool ({true, false}, ∨, ∧, false, true) прекрасно работает.Так же как и версия Int.Последний из них называется Parse Forest , и его представление (E, ∪, ·, ∅, {<>}), где E - набор строк, а {<>} - наборпустой строки.

Когда я пытаюсь скомпилировать это, я получаю: 

Rigge…   115  10 error           • Illegal instance declaration for ‘Semiring (Set String)’
(All instance types must be of the form (T a1 ... an)
where a1 ... an are *distinct type variables*,
and each type variable appears at most once in the instance head.

Что не имеет для меня особого смысла.Set String - это отдельный тип, верно, и все операции class Semiring должны быть выражены исключительно в терминах наборов строк.

Если вам нужен контекст, проект находится на RiggedРегулярные выражения .Версия Bool просто сообщает, что регулярное выражение совпадает;версия Int сообщает количество различных способов сопоставления регулярному выражению (т. е. "a" ~ /(a|a*)/ вернет 2, поскольку совпадают два отдельных и уникальных подвыражения);ParseForest должен возвращать не количество путей, а набор всех возможных путей - но он не может этого сделать, потому что я не понимаю, почему я не могу использовать конкретный тип данных, Set String, где другой конкретный тип данныхвроде Int или Bool работал нормально.

Ответы [ 2 ]

0 голосов
/ 31 января 2019

ответ Чи описывает, как это сделать, включив расширение, что совершенно нормально.Но если вам интересно, как можно обойтись без этого расширения, есть пара подходов.

Самым простым изменением было бы введение обертки нового типа для явного избавления от переменной типа самостоятельно перед определением экземпляра. 

newtype StringSet = StringSet (Set String)
instance Semiring StringSet where {...}

Но, конечно, это кажется несколько неуклюжим и примитивным.

В качестве альтернативы мне кажется, что вам не нужно быть таким конкретным, как String: ваш экземпляр будет работать для любого типа Monoid, не так ли? 

instance (Ord a, Monoid a) => Semiring (Set a) where
  zero = empty
  one = singleton mempty
  add = union
  mul a b = Data.Set.map (uncurry (<>)) $ cartesianProduct a b
0 голосов
/ 31 января 2019

Важнейшей частью является 

of the form (T a1 ... an) where a1 ... an are *distinct type variables*,

Ваш тип Set String, поэтому T = Set и a1 = String (и n=1).Но String это тип, а не переменная типа.Вместо этого совместимый экземпляр был бы 

instance (....) => Semiring (Set a) where
   ...

В любом случае, это древнее ограничение Haskell2010, которое вы можете игнорировать.В современном GHC Haskell вы можете включить расширение FlexibleInstances и без проблем использовать свой собственный экземпляр.Сам GHC должен предложить включить это в сообщении об ошибке.

Обратите внимание, что в настоящее время почти никто не программирует на строгом Haskell2010: существует так много расширений, которые стали слишком часто используемыми.Можно утверждать, что должен быть пересмотрен Отчет, например Haskell2020, в котором большинство распространенных безвредных расширений включены для большой пользы.Тем не менее, пока кто-то на самом деле не сделает это, нам нужно будет часто включать расширения.

...