只检查一次的声明？Haskell

Question

我有两个不等长的列表.当我添加它们时,我希望最终列表具有最长列表的长度.

addtwolists [0,0,221,2121] [0,0,0,99,323,99,32,2332,23,23]
>[0,0,221,2220,323,99,32,2332,23,23]
addtwolists [945,45,4,45,22,34,2] [0,34,2,34,2]
>[945,79,6,79,24,34,2]

zerolist :: Int -> [Integer]
zerolist x = take x (repeat 0)

addtwolists :: [Integer] -> [Integer] -> [Integer]
addtwolists x y = zipWith (+) (x ++ (zerolist ((length y)-(length x)))) (y ++ (zerolist ((length x)-(length y))))

这段代码效率低下.所以我尝试过:

addtwolist :: [Integer] -> [Integer] -> [Integer]
addtwolist x y = zipWith (+) (x ++ [head (zerolist ((length y)-(length x))) | (length y) > (length x)]) (y ++ [head (zerolist ((length x)-(length y))) | (length x) > (length y)]) 

还有其他方法可以提高效率吗？你能检查一次才能查看哪个列表更大吗？

Answer 1

您的实现很慢,因为看起来您在zipWith的每一步上多次调用每个列表上的length函数.Haskell通过遍历整个列表并计算它遍历的元素数来计算列表长度.

我想到的第一个快速方法是显式递归.

addLists :: [Integer] -> [Integer] -> [Integer]
addLists xs     []     = xs
addLists []     ys     = ys
addLists (x:xs) (y:ys) = x + y : addLists xs ys

我不知道任何标准的Prelude函数可以满足您的确切需求,但是如果您想将其推广到更高阶函数,那么您可能会比这更糟糕.传递给zip函数的两个新值是用于在短列表用尽后计算长列表的剩余部分的填充符.

zipWithExtend :: (a -> b -> c) -> [a] -> [b] -> a -> b -> [c]
zipWithExtend f []     []     a' b' = []
zipWithExtend f (a:as) []     a' b' = f a  b' : zipWithExtend f as [] a' b'
zipWithExtend f []     (b:bs) a' b' = f a' b  : zipWithExtend f [] bs a' b'
zipWithExtend f (a:as) (b:bs) a' b' = f a b   : zipWithExtend f as bs a' b'

用法:

> let as = [0,0,221,2121]
> let bs = [0,0,0,99,323,99,32,2332,23,23]
> zipWithExtend (+) as bs 0 0
[0,0,221,2220,323,99,32,2332,23,23]

Answer 2

这可以在一次迭代中完成,这应该是长列表的重大改进.使用显式递归可能最简单:

addTwoLists xs [] = xs
addTwoLists [] ys = ys
addTwoLists (x:xs) (y:ys) = x+y:addTwoLists xs ys