如何在Haskell中实现二进制数

Question

我已经看到教会数字的以下数据构造函数

data Nat = Zero | Succ Nat deriving Show

但这是一元数字.我们如何以这种方式在Haskell中实现二进制数的数据构造函数？

我试过这个:

data Bin = Zero | One | BinC [Bin] deriving Show

在此之后,我们可以得到,十进制5编码为 BinC [One,Zero,One]

但我想我在这里遗漏了一些东西.我的解决方案似乎不像教会的解决方案那么聪明.毫不奇怪,我不是教会.一点点思考,我发现我的解决方案依赖于列表,而Nat不依赖于列表之类的任何外部结构.

我们是否可以使用Succ类型的二进制数构造函数编写类似于Church的解决方案？如果有,怎么样？我尝试了很多,但似乎我的大脑无法摆脱列表或其他一些这样的结构的需要.

Answer 1

我能想到的最接近的就是

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

这使得构建二进制数字成为可能

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

人们还可以想象一个解码功能的工作原理(Ingo在评论中提出的更好的版本)

?> 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

Answer 2

只是您收到的其他答案的附录:

您创建的数据值实际上是Peano数字,而不是Church数字.它们密切相关,但它们实际上是彼此双重/反向的.Peano数字建立在从Set概念构造数字的概念之上,在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数字的折叠!并且(peano . church)是Peano数字的标识,尽管上面给出的类型Haskell不会让你直接组成它们.如果省略类型声明,Haskell将推断出足够多的类型,您可以将它们组合起来.

在Ralf Hinze的理论珍珠教堂数字中,函数式编程的背景下,有一个很好的概述差异和它们之间的关系,两次!.

你可以进一步概括这种二元性; Peano数字本质上是自然数的初始F-代数,教会数字本质上是自然数的最终/终端F-代数.对此的一个很好的介绍是Bart Jacobs和Jan Rutten 关于(Co)代数和(Co)归纳的A教程.