Церковные цифры в хаскеле - PullRequest
Новая
       6

Церковные цифры в хаскеле

9 голосов
/ 24 июня 2011

Я пытаюсь напечатать церковные цифры в haskell, используя определения: 

0 := λfx.x
1 := λfx.f x

Код Haskell: 

c0 = \f x -> x
c1 = \f x -> f x

Когда я ввожу его в консоль haskell, я получаю ошибку, котораяговорит 

    test> c1

    <interactive>:1:0:
    No instance for (Show ((t -> t1) -> t -> t1))
      arising from a use of `print' at <interactive>:1:0-1
    Possible fix:
      add an instance declaration for (Show ((t -> t1) -> t -> t1))
    In a stmt of an interactive GHCi command: print it

Я не могу точно понять, что говорит ошибка.

Спасибо!

Ответы [ 2 ]

15 голосов
/ 24 июня 2011

Проблема в том, что по умолчанию невозможно напечатать значения в Haskell. Способ печати по умолчанию, используемый, в частности, функцией print и GHCi REPL, - это функция show, определяемая классом типа Show.

Получаемая ошибка информирует вас о том, что вы вычислили выражение типа, для которого не определен экземпляр Show. По модулю словоблудия, это все сообщение об ошибке: 

No instance for (Show ((t -> t1) -> t -> t1))

Тип ((t -> t1) -> t -> t1) - это то, что было выведено для выражения, которое вы вычислили. Это допустимый тип для церковной цифры 1, хотя «правильный» тип для церковной цифры на самом деле должен быть (a -> a) -> a -> a. 

  arising from a use of `print' at <interactive>:1:0-1

Это неявное использование функции print для отображения значений. Обычно это говорит вам, где в вашей программе была обнаружена ошибка, но в этом случае она говорит <interactive>:1:0-1, потому что ошибка была вызвана выражением в REPL. 

Possible fix:
  add an instance declaration for (Show ((t -> t1) -> t -> t1))

Это просто говорит о том, что вы можете исправить ошибку, указав ожидаемый экземпляр.

Теперь, вы, вероятно, хотите распечатать свои церковные цифры, а не просто знать, почему вы не можете. К сожалению, это не так просто, как добавить запрашиваемый экземпляр: если вы пишете экземпляр для (a -> a) -> a -> a, Haskell интерпретирует это как экземпляр для любого конкретного a, тогда как правильная интерпретация Церковная цифра - это полиморфная функция, которая работает на любом произвольном a.

Другими словами, вы хотите, чтобы ваша функция show была примерно такой: 

showChurch n = show $ n (+1) 0

Если вы действительно хотите, вы можете реализовать экземпляр Show следующим образом: 

instance (Show a, Num a) => Show ((a -> a) -> a -> a) where
    show n = show $ n (+1) 0

и добавьте {-#LANGUAGE FlexibleInstances#-} в первую строку файла. Или вы можете реализовать нечто подобное, чтобы преобразовать их в обычное число 

> churchToInt c1
1
> showChurch c1
"1"

и т.д.

6 голосов
/ 24 июня 2011

РЕДАКТИРОВАТЬ: Оповещение о спойлере, как упомянуто в комментарии

Или, вы можете иметь тип для церковных цифр, что-то вроде этого: 

data Church x = Church ((x -> x) -> x -> x)

zero :: Church x
zero = Church (\f x -> x)

-- Hack to not clash with the standard succ
succ_ :: Church x -> Church x
succ_ (Church n) = Church (\f x -> (f (n f x)))

instance (Num x) => Show (Church x) where
  show (Church f) = show $ f (1 +) 0
...