解读ADDC代码并进行

好了，所以我有这样的代码在Haskell：解读ADDC代码并进行

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不是我（代表1）和O（代表0）。

我想通了，类型签名添加和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列表。但是，我不明白用什么模式来匹配这个。我很困惑“携带”是什么意思。任何人都可以尝试和帮助吗？

来源

2011-11-20 user1056769

顺便说一句，这段代码写得相当不错。你通常会为此使用'foldr'。 – fuz

'addC'函数实现了一个波纹进位加法器，case语句只是一个完整的加法器。你需要学习二进制算术来理解代码，一旦你做了它几乎微不足道。 – augustss

哦，代码是错误的。案件陈述中的一个“左”应该是“carry”。哪一个并不重要。 – augustss

正如在注释中说明，该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)

来源

2013-09-28 21:53:42

解读ADDC代码并进行

回答

相关问题