haskell - 破译 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]

它给了我 [I,I,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)