Statement for checking only once?Haskell

Question

I have two lists of unequal length. When I add both of them I want the final list to have the length of the longest list.

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

This code is inefficient. So I tried:

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

Any other way to increase the efficiency?Could you only check once to see which list is bigger?

Answer 1

Your implementation is slow because it looks like you call the length function on each list multiple times on each step of zipWith. Haskell computes list length by walking the entire list and counting the number of elements it traverses.

The first speedy method that came to my mind was explicit recursion.

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

I'm not aware of any standard Prelude functions that would fill your exact need, but if you wanted to generalize this to a higher order function, you could do worse than this. The two new values passed to the zip function are filler used in computing the remaining portion of the long list after the short list has been exhausted.

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'

Usage:

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