list - 如何对两个列表的元素求和。 haskell

Question

我才刚刚开始学习 Haskell，目前我正在探索列表的可能性。 我想总结两个列表，但不知何故出错了。

所以:

输入:sumTwoLists [2,5,7,7,9] [1,2,2](基本上是 25779 + 122)

输出:[2,5,9,0,1]

首先，我把整个列表颠倒了，因为多位数字的相加必须从末尾开始:

reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

它有效。然后我实现了一个添加功能:

add :: (Num a) => [a] -> [a] -> [a]
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys

但是当一个列表比另一个短时，它就会出错。 (添加 [2,5,7,7,9] [1,2,2] = [3,7,9]) 所以 finction 也必须在较低数字的末尾添加 0 ([1,2,2] = [1,2,2,0,0].)

然后我尝试像这样实现 sumTwoLists 函数:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists (x:xs) (y:ys) = reverseList ((reverseList (x:xs)) add (reverseList (y:ys)))

但是这段代码没有考虑到元素不能大于9的事实。 我不想将元素转换为 Int 或 Integer，这就是我不使用它们的原因。

我基本上只是想反转列表，然后在最短列表中添加 0，然后将每个元素与另一个列表中的元素相加，如果结果 >9，则结果除以 10 (mod? )且相邻数增加

如有任何帮助，我将不胜感激!

Answer 1

用列表做这个没有多大意义，因为它会引入很多额外的问题:

1. 如果两个列表的长度不同，或者求和需要额外的元素，则用零填充；和
2. 考虑到将两位数相加可能会产生大于 9 的值，因此引入了一个进位。

add 函数无法正常工作，因为它会在其中一个列表用完时停止，而且它没有考虑到数字可能会“溢出”。因此，我们应该构造一个函数 add，它有一个额外的参数:进位:

add' :: Int -> [Int] -> [Int] -> [Int]
add' 0 [] [] = []
add' n [] [] = [n]
add' n xs [] = add' n xs [0]
add' n [] xs = add' n [0] xs
add' n (x:xs) (y:ys) = r : add' q xs ys
    where (q,r) = quotRem (x+y+n) 10

add 因此从零作为进位开始:

add :: [Int] -> [Int] -> [Int]
add = add' 0

如果我们这样计算反转列表的总和，我们得到:

Prelude> add [9,7,7,5,2] [2,2,1]
[1,0,9,5,2]

为了让它工作，你需要使用 add 作为中缀运算符，两个操作数可以是空或非空列表:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists xs ys = reverseList ((reverseList xs) <b>`add`</b> (reverseList ys))

或使用 on :: (b -> b -> c) -> (a -> b) -> a -> a -> c :

import Data.Function(on)

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists = add <b>`on`</b> reverse

对于给定的样本输入，我们现在得到:

Prelude> sumTwoLists [2,5,7,7,9] [1,2,2]
[2,5,9,0,1]

最后 reverseList 已经存在于 Prelude 中:reverse :: [a] -> [a] .您实现的reverseList 函数运行时间为O(n²)，效率不是很高，您可以使用累加器来获得线性时间。