Как реализовать двоичные числа в Haskell

Самое близкое, о чем я могу думать, было бы чем-то вроде

λ> data Bin = LSB | Zero Bin | One Bin
λ|  -- deriving Show

Это позволяет строить двоичные числа, выполняя только

λ> One . One . Zero . Zero . One . One $ LSB
One (One (Zero (Zero (One (One LSB)))))

Можно также представить функцию декодирования, работающую по принципу (намного лучшая версия, предложенная Инго в комментариях)

λ> let toInt :: (Integral a) => Bin -> a
λ|     toInt = flip decode 0
λ|       where decode :: (Integral a) => Bin -> a -> a
λ|             decode LSB value = value
λ|             decode (Zero rest) value = decode rest (2*value)
λ|             decode (One rest) value = decode rest (2*value + 1)

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

λ> toInt (Zero . One . One . One . Zero . Zero . One $ LSB)
57

Трудность с тем, чего вы хотите достичь, заключается в том, что вам нужно читать двоичные числа «наизнанку» или, так сказать. Чтобы узнать значение старшей значащей цифры, нужно знать, сколько цифр у вас в числе. Если бы вы записали свои двоичные числа в «обратном» порядке, то есть самая внешняя цифра является наименее значащей цифрой, тогда с этим было бы намного проще справиться, но числа смотрели бы назад, когда вы их создаете и распечатываете, используя экземпляр по умолчанию. из Show.

Причина, по которой это не проблема с унарными числами, заключается в том, что не существует «наименее значащей цифры», поскольку все цифры имеют одинаковое значение, поэтому вы можете анализировать число в любом направлении, и вы получите тот же результат.

Для полноты, вот то же самое, но с самой дальней цифрой, являющейся младшей значащей цифрой:

λ> data Bin = MSB | Zero Bin | One Bin
λ|   -- deriving Show

Это выглядит почти так же, как и раньше, но вы заметите, что когда реализована функция декодирования,

λ> let toInt = flip decode (1,0)
λ|       where
λ|         decode (One rest) (pos, val) = decode rest (pos*2, val+pos)
λ|         decode (Zero rest) (pos, val) = decode rest (pos*2, val)
λ|         decode MSB (_, val) = val

Цифры пишутся наоборот!

λ> toInt (Zero . Zero . Zero . One . Zero . One $ MSB)
40

Однако справиться с этим намного проще. Например, мы можем добавить два двоичных числа в каждом конкретном случае. (Внимание: много случаев!)

λ> let add a b = addWithCarry a b False
λ|      where
λ|        addWithCarry :: Bin -> Bin -> Bool -> Bin
λ|        addWithCarry MSB MSB True = One MSB
λ|        addWithCarry MSB MSB False = MSB
λ|        addWithCarry MSB b c = addWithCarry (Zero MSB) b c
λ|        addWithCarry a MSB c = addWithCarry a (Zero MSB) c
λ|        addWithCarry (Zero restA) (Zero restB) False = Zero (addWithCarry restA restB False)
λ|        addWithCarry (One restA)  (Zero restB) False = One (addWithCarry restA restB False)
λ|        addWithCarry (Zero restA) (One restB)  False = One (addWithCarry restA restB False)
λ|        addWithCarry (One restA)  (One restB)  False = Zero (addWithCarry restA restB True)
λ|        addWithCarry (Zero restA) (Zero restB) True = One (addWithCarry restA restB False)
λ|        addWithCarry (One restA)  (Zero restB) True = Zero (addWithCarry restA restB True)
λ|        addWithCarry (Zero restA) (One restB)  True = Zero (addWithCarry restA restB True)
λ|        addWithCarry (One restA)  (One restB)  True = One (addWithCarry restA restB True)

В этот момент добавить два двоичных числа очень просто:

λ> let forty = Zero . Zero . Zero . One . Zero . One $ MSB
λ|     eight = Zero . Zero . Zero . One $ MSB
λ|
λ> add forty eight
Zero (Zero (Zero (Zero (One (One MSB)))))

И действительно!

λ> toInt $ Zero (Zero (Zero (Zero (One (One MSB)))))
48

Просто дополнение к другим ответам, которые вы получили:

Значения данных, которые вы создаете, на самом деле являются числами Пеано, а не числами Черча. Они тесно связаны, но на самом деле они двойственны/обратны друг другу. Числительные Пеано построены на идее построения чисел из концепции множества, для представления которой в Haskell мы используем тесно связанную концепцию типа данных.

{-# LANGUAGE RankNTypes #-}

import Prelude hiding (succ)

data Peano = Zero
           | Succ Peano
  deriving (Show)

Цифры Черча, с другой стороны, кодируют цифры как функции:

type Church = forall n. (n -> n) -> n -> n

zero :: Church
zero = \p -> id

succ :: Church -> Church
succ = \n p -> p . n p

Теперь вы можете собрать их вместе:

peano :: Church -> Peano
peano c = c Succ Zero

fold :: forall n. (n -> n) -> n -> Peano -> n
fold s z Zero     = z
fold s z (Succ p) = s (fold s z p)

church :: Peano -> Church
church p = \s z -> fold s z p

Таким образом, цифры Чёрча, по сути, являются сгибом над цифрами Пеано! И (peano . church) - это идентификатор для чисел Пеано, хотя с типами, указанными выше, Haskell не позволит вам напрямую составить их таким образом. Если вы пропустите объявления типов, Haskell выведет достаточно общие типы, чтобы вы могли их составить.

Хороший обзор различий и их связи друг с другом в контексте функционального программирования можно найти здесь, в Theoretical Pearl Ральфа Хинце Церковные цифры, дважды!.

Вы можете еще больше обобщить эту двойственность; цифры Пеано, по сути, являются начальной F-алгеброй для натуральных чисел, а цифры Черча, по сути, являются конечной / конечной F-коалгеброй для натуральных чисел. Хорошим введением в это является Учебное пособие по (Co)алгебрам и (Co) алгебрам Барта Джейкобса и Яна Руттена. Индукция.