2

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

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)])

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

4

4 回答 4

7

您的实现很慢，因为看起来您在 zipWith 的每个步骤中多次调用每个列表上的长度函数。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]
于 2012-10-05T05:48:02.097 回答
6

这可以在一次迭代中完成，这对于长列表来说应该是一个显着的改进。使用显式递归可能最简单：

addTwoLists xs [] = xs
addTwoLists [] ys = ys
addTwoLists (x:xs) (y:ys) = x+y:addTwoLists xs ys
于 2012-10-05T05:15:46.153 回答
3

只是因为我忍不住要骑自行车，你可能会喜欢这个功能：

Prelude Data.Monoid Data.List> :t map mconcat . transpose
map mconcat . transpose :: Monoid b => [[b]] -> [b]

例如：

> map (getSum . mconcat) . transpose $ [map Sum [0..5], map Sum [10,20..100]]
[10,21,32,43,54,65,70,80,90,100]
于 2012-10-05T08:42:07.650 回答
0

两个建议：

addtwolists xs ys = 
  let common = zipWith (+) xs ys
      len = length common
  in common ++ drop len xs ++ drop len ys   

addtwolists xs ys | length xs < length ys = zipWith (+) (xs ++ repeat 0) ys
                  | otherwise = zipWith (+) xs (ys ++ repeat 0)
于 2012-10-05T11:18:01.860 回答