在Haskell中添加存储为0和1的列表的两个二进制数，而不使用反向

Question

我试图以优雅和富有表现力的方式解决这个简单问题。通常，我会从两个列表的末尾开始，添加相应的元素并存储进位来计算下一个数字。但是，我正在努力通过递归来解决这个问题，并且不使用reverse函数。

这是我第一次尝试：

binarySum :: [Int] -> [Int] -> [Int] 
binarySum ls ls' 
    = let (res, c) = binarySum' ls ls' in c : res 
    where 
binarySum' [x] [y] 
    = let (s, c) = add x y in ([s], c) 
binarySum' (x : xs) (y : ys) 
    = (s : res, c') 
    where 
    (res, c) = binarySum' xs ys 
    (s, c') = add' x y c 

（其中添加，并添加”功能执行所需的操作）

结果列表看起来是正确的，但以相反的顺序。我不知道如何继续，因为我选择在辅助函数中随同进位一起返回的对中创建结果（通常我会执行类似s : binarySum'...的操作）。

此外，我觉得代码太混乱了，不像应该那样优雅。

任何帮助，非常感谢！

Answer 1

你几乎在那里（至少你的解释似乎表明如此 - 你的代码依赖于你没有包含的add函数）。诀窍确实是将进位作为一个单独的数字保存在一个辅助函数的元组中（我已经命名为binarySum'）。然后，你正在使用的不变量是返回的列表长度与所提供的两个列表中较大的那个长度相同（并且是它们的总和的第一个数字） - 如果有的话，分别持有一个进位。

binarySum :: [Int] -> [Int] -> [Int] 
binarySum xs ys 
    | length xs < length ys = binarySum (replicate (length ys - length xs) 0 ++ xs) ys 
    | length xs > length ys = binarySum xs (replicate (length xs - length ys) 0 ++ ys) 
    | otherwise = case binarySum' xs ys of 
        (0, zs) -> zs 
        (1, zs) -> 1:zs 
    where 
    binarySum' :: [Int] -> [Int] -> (Int, [Int]) 
    binarySum' [] ys = (0, ys) 
    binarySum' xs [] = (0, xs) 
    binarySum' (x:xs) (y:ys) = let (c, zs) = binarySum' xs ys 
            (c', z) = (x + y + c) `divMod` 2 
           in (c', z:zs)