Sum corresponding elements of two lists, with the extra elements of the longer list added at the end

Question

I'm trying to add two lists together and keep the extra elements that are unused and add those into the new list e.g.

addLists [1,2,3] [1,3,5,7,9] = [2,5,8,7,9]

I have this so far:

addLists :: Num a => [a] -> [a] -> [a]
addLists xs ys = zipWith (+) xs ys

but unsure of how to get the extra elements into the new list.

and the next step is changing this to a higher order function that takes the combining function as an argument:

longZip :: (a -> a -> a) -> [a] -> [a] -> [a]

Take a look at how `zipWith` is implemented, and use explicit recursion. — Willem Van Onsem, Nov 18 '20 at 11:45
im stuck on how to write the explicit recursion part @WillemVanOnsem — moxem, Nov 18 '20 at 11:47

score 0 · Accepted Answer · answered Nov 18 '20 at 11:48

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] is implemented as [src]:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys

It thus uses explicit recursion where go will check if the two lists are non-empty and in that case yield f x y, otherwise it stops and returns an empty list [].

You can implement a variant of zipWith which will continue, even if one of the lists is empty. THis will look like:

zipLongest :: (a -> a -> a) -> [a] -> [a] -> [a]
zipLongest f = go
  where go [] ys = …
        go xs [] = …
        go (x:xs) (y:ys) = f x y : go xs ys

where you still need to fill in ….

Will Ness · Answer 2 · 2020-11-18T15:27:57.553

You can do it with higher order functions as simple as

import Data.List (transpose)

addLists :: Num a => [a] -> [a] -> [a]
addLists xs ys = map sum . transpose $ [xs, ys]

because the length of transpose[xs, ys, ...] is the length of the longest list in its argument list, and sum :: (Foldable t, Num a) => t a -> a is already defined to sum the elements of a list (since lists are Foldable).

transpose is used here as a kind of a zip (but cutting on the longest instead of the shortest list), with [] being a default element for the lists addition ++, like 0 is a default element for the numbers addition +:

cutLongest [xs, ys] $
  zipWith (++) (map pure xs ++ repeat []) (map pure ys ++ repeat [])

See also:

Zip with default value instead of dropping values?

score 0 · Answer 3 · answered Nov 18 '20 at 17:55

You're looking for the semialign package. It gives you an operation like zipping, but that keeps going until both lists run out. It also generalizes to types other than lists, such as rose trees. In your case, you'd use it like this:

import Data.Semialign
import Data.These

addLists :: (Semialign f, Num a) => f a -> f a -> f a
addLists = alignWith (mergeThese (+))

longZip :: Semialign f => (a -> a -> a) -> f a -> f a -> f a
longZip = alignWith . mergeThese

The new type signatures are optional. If you want, you can keep using your old ones that restrict them to lists.

Sum corresponding elements of two lists, with the extra elements of the longer list added at the end

3 Answers3