GADT для полиморфного списка

Question

Я разбор несколько утверждений вида

v1 = expression1 
v2 = expression2 
... 

Я использую государство монаду и мое состояние должна быть парой (String, Expr а), я действительно настаиваю на том, чтобы набираемые выражения. Я пытался реализовать государство как [PPair], где я определяю PPair по GADT:

data PPair where 
    PPair :: (String, Expr a) -> PPair 

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

evalVar k ((PPair (kk, v)):s) = if k == kk then v else evalVar k s 

я получаю:

Inferred type is less polymorphic than expected 

который вполне ожидаемый. Как мне решить эту проблему? Я знаю, что могу решить эту проблему, разбив тип по всем типам кандидатов a, но нет ли способа более аккуратного?

Answer 1

Проблема заключается в том, что нет никакой возможности типа evalVar может иметь:

evalVar :: String -> [PPair] -> Expr ? 

Вы не можете сказать ? является a, потому что тогда вы подтвердили ваше возвращение значение работает любой значение a. Что вы можете сделать, однако, завернуть «в Expr неизвестного типа» в свой собственный тип данных:

data SomeExpr where 
    SomeExpr :: Expr a -> SomeExpr 

или, что то же самое, с RankNTypes, а не GADTs:

data SomeExpr = forall a. SomeExpr (Expr a) 

Это экзистенциальная количественная оценка. Затем вы можете переписать PPair с помощью SomeExpr:

data PPair = PPair String SomeExpr 

и evalVar работает: (. Конечно, вы могли бы просто использовать [(String,SomeExpr)] вместо этого, и стандартную lookup функцию)

evalVar k (PPair kk v : xs) 
    | k == kk = v 
    | otherwise = evalVar k xs 

В целом, однако, попытка сохранить выражения, полностью набранные на уровне Haskell, как это, вероятно, является бесполезным упражнением; язык с зависшим от типа языка, например, Agda, не будет с ним проблем, но вы, вероятно, столкнетесь с чем-то, что Haskell не может сделать довольно быстро или ослабить ситуацию до такой степени, в которой вы хотели бы избежать компромиссной безопасности потерян.

Это не значит, что он никогда не работает, конечно; типизированные языки были одним из мотивирующих примеров для GADT. Но это может не сработать так, как вам хочется, и вы, вероятно, столкнетесь с проблемами, если на вашем языке есть нетривиальные системные функции типа, такие как полиморфизм.

Если вы действительно хотите сохранить ввод, тогда я бы использовал более богатую структуру, чем строки, чтобы назвать переменные; имеют Var a тип, который явно несет в себе тип, например:

data PPair where 
    PPair :: Var a -> Expr a -> PPair 

evalVar :: Var a -> [PPair] -> Maybe (Expr a) 

Хороший способ добиться чего-то похожее на это было бы использовать vault пакет; вы можете построить Key с ST и IO и использовать Vault в качестве гетерогенного контейнера. В основном это похоже на Map, где клавиши имеют тип соответствующего значения. В частности, я предлагаю определить Var a как Key (Expr a) и использовать Vault вместо [PPair]. (Полное раскрытие: Я работал на упаковке хранилища.)

Конечно, вы все равно должны отображать имена переменных в Key значений, но вы можете создать все Key сек сразу после разбора, и носить те вокруг, а не строки. (Однако было бы неплохо перейти от Var к соответствующему имени переменной с помощью этой стратегии, но вы можете сделать это со списком экзистенций, но решение слишком долго, чтобы вставить этот ответ.)

(Кстати, вы можете иметь несколько аргументов для конструктора данных с GADT, как и обычные типы: data PPair where PPair :: String -> Expr a -> PPair.)