2

長さが等しくない 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

あなたの正確なニーズを満たす標準的なプレリュード関数は知りませんが、これを高次関数に一般化する場合は、これよりも悪い結果になる可能性があります。zip 関数に渡される 2 つの新しい値は、短いリストが使い果たされた後、長いリストの残りの部分を計算する際に使用されるフィラーです。

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

これは 1 回の反復で実行できるため、長いリストの場合は大幅に改善されるはずです。明示的な再帰を使用すると、おそらく最も簡単です。

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

2 つの提案:

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 に答える