Тип данных с ограничением типов в Wadler - Суть функционального программирования,

Question

В статье Фила Уодлера: Суть функционального программирования, Вадлер описывает применение Монад с помощью простой программы-интерпретатора.Программа выглядит так:

Термин - это либо переменная, либо константа, сумма, лямбда-выражение или приложение.Следующие данные будут служить тестовыми данными.

term0 = (App (Lam "x" (Add (Var "x") (Var "x"))) (Add (Con 10) (Con 11)))

Для наших целей монада - это тройка (M,unitM,bindM), состоящая из конструктора типа M и пары полиморфных функций.

unitM :: a -> M a
bindM :: M a -> (a -> M b) -> M b

Тогда программа интерпретатора описывается так:

type Name = String

data Value = Wrong
           | Num Int
           | Fun (Value -> M Value)

Я не вижу, как сюда включён M Value.Насколько я понимаю, что Haskell не допускает ограничения типов для конструкторов типов данных?

Дополнительные сведения: Полная программа приведена ниже:

type Name = String
data Term = Var Name
          | Con Int
          | Add Term Term
          | Lam Name Term
          | App Term Term
data Value = Wrong
           | Num Int
           | Fun (Value -> M Value)
type Environment = [(Name, Value)]
interp :: Term -> Environment -> M Value
interp (Var x) e = lookup x e
interp (Con i) e = unitM (Num i)
interp (Add u v) e = interp u e `bindM` (\a ->
                                            interp v e `bindM` (\b ->
                                                                  add a b))
interp (Lam x v) e = unitM (Fun (\a -> interp v ((x,a):e)))
interp (App t u) e = interp t e `bindM` (\f ->
                                             interp u e `bindM` (\a ->
                                                                     apply f a))

lookup :: Name -> Environment -> M Value
lookup x [] = unitM Wrong
lookup x ((y,b):e) = if x==y then unitM b else lookup x e

add :: Value -> Value -> M Value
add (Num i) (Num j) = unitM (Num (i+j))
add a b = unitM Wrong

apply :: Value -> Value -> M Value
apply (Fun k) a = k a
apply f a = unitM Wrong

Как видно, interp (Lam x v) e = unitM (Fun (\a -> interp v ((x,a):e))) требует определения data Value = ... | Func (Value -> M Value)

Я пытался реализовать interp (Lam x v) с помощью data Value = ... | Func (Value -> Value), но мне это не казалось возможным.

Answer 1

M не является ограничением, это конструктор типа.Таким образом, написание M Value похоже [Value], Maybe Value и т. Д. Ограничение будет выглядеть примерно так: Monad m => m Value, где m - это переменная типа, а не конструктор типа, а Monad m - это ограничение (Monad является классом типа).

В статье определение типа M value не представлено, и позже будет показано, что вы можете дать ему различные определения (определения будут включать определение data M v = ... и функций bindM и unitM).

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

data Value m = Wrong
             | Num Int
             | Fun (Value m -> m (Value m))

И затем получите ограничение втипы функций, например:

interp :: Monad m => Term -> Environment -> m (Value m)