解密addC代码并随身携带

Question

好的,所以我在Haskell中有这个代码:

data Bigit = O | I deriving (Show,Eq)

add x y = reverse $ addC O (reverse x) (reverse y)

addC O [] [] = []
addC I [] [] = [I]
addC carry [] r = addC carry [O] r
addC carry l [] = addC carry l [O]
addC carry (left:leftOver) (right:rightOver) = sumBigit :(addC newCarry leftOver    
                                                                             rightOver)
where
    (sumBigit,newCarry)
        = case (left,right,left) of
            (O,O,O) -> (O,O)
            (O,I,O) -> (I,O)
            (I,O,O) -> (I,O)
            (I,I,O) -> (O,I)
            (O,O,I) -> (I,O)
            (O,I,I) -> (O,I)
            (I,O,I) -> (O,I)
            (I,I,I) -> (I,I)

我需要弄清楚它意味着什么.到目前为止,我知道它使用bigits和bigits列表作为类型,并且bigit是I(表示1)和O(表示0).

我想出了add和addC的类型签名:

add :: [Bigit] -> [Bigit] -> [Bigit]
addC :: Bigit -> [Bigit] -> [Bigit] -> [Bigit]

为了帮助我理解,我已经将代码加载到GHCI中,我一直在玩它.例如,我知道如果我告诉它:

add [I,O] [I,O]

它给了我[我,我,O],因为它遵循:

reverse (addC O (reverse x) (reverse y))
reverse (addC O [O,I] [O,I])

但是从这里开始,我对如何搞清楚addC部分感到困惑.我有正确的论点:Bigit和两个Bigits列表.但是,我不明白要匹配这个模式.我对"携带"的含义感到很困惑.有人可以尝试和帮助吗？

Answer 1

正如注释中所解释的，该addC函数对反向二进制代码进行操作（没有真正原因的位名为 Bigits），并且存在一个需要在模式中包含进位的错误case。的许多变体addC覆盖所有可能的输入组合，特别是在递归调用中：

addC O [] [] = []

在这种情况下，我们已经用完了数字，并且进位输入为零。这意味着我们不需要添加另一个数字并且可以返回一个空列表。

addC I [] [] = [I]

当我们用完输入项时，我们会剩下一个进位，因此我们用一位数字扩展结果。一旦两个列表都用尽，这些情况中的任何一个都将匹配，并终止递归计算，因为它们不会再次调用 addC。

addC carry [] r = addC carry [O] r

这用于扩大左项，因为右项尚未用尽（如果用尽，则较早的模式将与其匹配）。

addC carry l [] = addC carry l [O]

同样，当左项未穷尽时，扩大右项。

通过所有这些模式，可以保证主 addC 定义可以处理相同长度的列表，并且进位不会在长度溢出中丢失。它可以用不同的方式编写，这样我们只要复制任一项的剩余部分，一旦进位是 O 并且另一个项是 []，但模式是详尽的和终止的，这是最重要的。附注是，就该加法器而言，[] 是有效的零值。

addC carry (left:leftOver) (right:rightOver) = 
     sumBigit :(addC newCarry leftOver rightOver)
     where (sumBigit,newCarry) = ....

这是该函数的核心内容。它从左项和右项中的每一项中提取一个 Bigit，并使用真值表来计算这些项和进位位的两位和（好吧，如果没有问题的话，它会的）。结果保存该和的最低有效位，然后保存两项具有新进位值的其余项的递归和。

作为练习，我冒昧地使用foldr. 结果不是很漂亮，但确实避免了逆转步骤；相反，排列不同长度的列表需要一个单独的扩展步骤，我是通过测量列表的长度来完成的。

extMatch :: a -> b -> [a] -> [b] -> [(a,b)]
extMatch a0 b0 a b = zip (ext a0 (lb-la) a) (ext b0 (la-lb) b)
  where ext x0 l x | l>0 = concat [replicate l x0, x]
                   | l<=0 = x
        la = length a
        lb = length b

add2 :: [Bigit] -> [Bigit] -> [Bigit]
add2 x y = extsum $ foldr addC2 (O, []) (extMatch O O x y)
  where extsum (O,sum) = sum
        extsum (I,sum) = I:sum

addC2 :: (Bigit, Bigit) -> (Bigit, [Bigit]) -> (Bigit, [Bigit])
addC2 (O, O) (O, sumbits) = (O, O:sumbits)
addC2 (O, O) (I, sumbits) = (O, I:sumbits)
addC2 (O, I) (O, sumbits) = (O, I:sumbits)
addC2 (O, I) (I, sumbits) = (I, O:sumbits)
addC2 (I, O) (O, sumbits) = (O, I:sumbits)
addC2 (I, O) (I, sumbits) = (I, O:sumbits)
addC2 (I, I) (O, sumbits) = (I, O:sumbits)
addC2 (I, I) (I, sumbits) = (I, I:sumbits)