Лэмбда-исчисление в Haskell: Есть ли способ сделать проверку типа цифр в церкви?

Я играю с некоторыми материалами лямбда-исчисления в Haskell, в частности церковными цифрами. У меня определено следующее:

let zero = (\f z -> z)
let one = (\f z -> f z)
let two = (\f z -> f (f z))
let iszero = (\n -> n (\x -> (\x y -> y)) (\x y -> x))
let mult = (\m n -> (\s z -> m (\x -> n s x) z))

Это работает:

:t (\n -> (iszero n) one (mult one one))

Это не выполняется с проверкой наличия:

:t (\n -> (iszero n) one (mult n one))

Я играл с iszero и mult с моими константами, и они кажутся правильными. Есть ли способ сделать этот тип? Я не думал, что то, что я делаю, слишком сумасшедшее, но, может быть, я что-то делаю неправильно?

Ответы

Ответ 1

Ваши определения верны, как и их типы, когда они видны на верхнем уровне. Проблема заключается в том, что во втором примере вы используете n двумя разными способами, которые не имеют одного и того же типа, или, скорее, их типы не могут быть унифицированы, и попытка сделать это приведет к бесконечный тип. Подобное использование one работает правильно, потому что каждое использование независимо специализировано для разных типов.

Чтобы сделать эту работу простым способом, вам нужен полиморфизм более высокого ранга. Правильный тип для церковной цифры (forall a. (a -> a) -> a -> a), но типы более высокого ранга не могут быть выведены и требуют расширения GHC, такого как RankNTypes. Если вы включите соответствующее расширение (вам кажется, что в этом случае вам нужен только ранг-2), дайте явные типы для ваших определений, они должны работать без изменения фактической реализации.

Обратите внимание, что существуют (или, по крайней мере, были) некоторые ограничения на использование полиморфных типов более высокого ранга. Тем не менее, вы можете обернуть свои церковные цифры чем-то вроде newtype ChurchNum = ChurchNum (forall a. (a -> a) -> a -> a), что позволит дать им экземпляр Num.

Ответ 2

Добавьте некоторые сигнатуры типа:

type Nat a = (a -> a) -> a -> a

zero :: Nat a
zero = (\f z -> z)

one :: Nat a
one = (\f z -> f z)

two :: Nat a
two = (\f z -> f (f z))

iszero :: Nat (a -> a -> a) -> a -> a -> a
iszero = (\n -> n (\x -> (\x y -> y)) (\x y -> x))

mult :: Nat a -> Nat a -> Nat a
mult = (\m n -> (\s z -> m (\x -> n s x) z))

Как вы можете видеть, все выглядит довольно нормально, за исключением типа iszero.

Посмотрим, что произойдет с вашим выражением:

*Main> :t (\n -> (iszero n) one n)
<interactive>:1:23:
    Occurs check: cannot construct the infinite type:
      a0
      =
      ((a0 -> a0) -> a0 -> a0)
      -> ((a0 -> a0) -> a0 -> a0) -> (a0 -> a0) -> a0 -> a0
    Expected type: Nat a0
      Actual type: Nat (Nat a0 -> Nat a0 -> Nat a0)
    In the third argument of `iszero', namely `(mult n one)'
    In the expression: (iszero n) one (mult n one)

Посмотрите, как ошибка использует наш псевдоним Nat!

Мы можем получить аналогичную ошибку с более простым выражением \n -> (iszero n) one n. Вот что случилось. Поскольку мы вызываем iszero n, мы должны иметь n :: Nat (b -> b -> b). Кроме того, из-за iszero введите второй и третий аргументы, n и one, должны иметь тип b. Теперь мы имеем два уравнения для типа n:

n :: Nat (b -> b -> b)
n :: b

Что не может быть согласовано. Облом.