sum3 with zipWith3 in Haskell

Question

I'm trying to write a Haskell function that would take three lists and return a list of sums of their elements. Currently I'm trying to do it using zipWith3:

sum3 :: Num a => [a] -> [a] -> [a] -> [a]
sum3 xs ys zs  = zipWith3 (\x y z -> x+y+z) xs ys zs

The problem is it only works for lists of equal lengths. But I wish sum3 to work with lists of unequal lengths, so that

sum3 [1,2,3] [4,5] [6]

would return

[11,7,3]

I think that I should redefine zipWith3 to work with lists of unequal lengths, but can't figure out how to do it (I suspect that I have to exhaust all possibilities of empty lists). Is there a solution?

You will have to pass an additional argument, the default value to use when some of the lists are exhausted. — n. m. could be an AI, Oct 14 '15 at 10:34
btw: you could extent the solution here if you just concat `repeat 0` to the smaller lists - but IMO this is to ugly to propose ;) — Random Dev, Oct 14 '15 at 10:37
@Carsten but how should zipWith know whether you are summing up or doing something else? — n. m. could be an AI, Oct 14 '15 at 10:40
Actually, I suspect that there's a solution that should work with any function normal `zipWith3` works with, not just addition. — Chiffa, Oct 14 '15 at 10:42
Add `a` to the beginning of every element, resulting in `[ab,ac,ad]` — Chiffa, Oct 14 '15 at 10:50
Let's talk `zipWith` for simplicity (no 3). What should `zipWith (:) "a" ["b", "c"]` do? — n. m. could be an AI, Oct 14 '15 at 10:52
Sorry edited for correctness. But that's not what you specified for your sum function. It doesn't add the last element from the exhausted list, it adds zero. Please try to specify your desired result formally for generic arguments. Again start with the two-list version for simplicity. — n. m. could be an AI, Oct 14 '15 at 10:56

score 12 · Answer 1 · answered Oct 14 '15 at 10:29

12

a nice trick is to use transpose:

import Data.List (transpose)

sum3 :: Num a => [a] -> [a] -> [a] -> [a]
sum3 as bs cs = map sum $ transpose [as,bs,cs]

because obviously you want to sum up the columns ;)

> sum3 [1,2,3] [4,5] [6]
[11,7,3]

answered Oct 14 '15 at 10:29

Random Dev

51,810
9
92
119

Quite nice, thanks! Still, it's interesting to implement it with `zipWith3` – Chiffa Oct 14 '15 at 10:37

score 6 · Answer 2 · edited May 23 '17 at 11:59

I've seen this sort of question before, here: Zip with default value instead of dropping values? My answer to that question also pertains here.

The ZipList applicative Lists with a designated padding element are applicative (the applicative grown from the 1 and max monoid structure on positive numbers).

data Padme m = (:-) {padded :: [m], padder :: m} deriving (Show, Eq)

instance Applicative Padme where
  pure = ([] :-)
  (fs :- f) <*> (ss :- s) = zapp fs ss :- f s where
    zapp  []        ss        = map f ss
    zapp  fs        []        = map ($ s) fs
    zapp  (f : fs)  (s : ss)  = f s : zapp fs ss

-- and for those of you who don't have DefaultSuperclassInstances
instance Functor Padme where fmap = (<*>) . pure

Now we can pack up lists of numbers with their appropriate padding

pad0 :: [Int] -> Padme Int
pad0 = (:- 0)

And that gives

padded ((\x y z -> x+y+z) <$> pad0 [1,2,3] <*> pad0 [4,5] <*> pad0 [6])
= [11,7,3]

Or, with the Idiom Brackets that aren't available, you vould write

padded (|pad0 [1,2,3] + (|pad0 [4,5] + pad0 6|)|)

meaning the same.

Applicative gives you a good way to bottle the essential idea of "padding" that this problem demands.

Is there a reason we can't simply write `(|pad0 [1,2,3] + pad0 [4,5] + pad0 [6]|)` (you missed the `[]` around `6`, BTW)? Or, more generally, can we treat `(...)` inside `(|...|)` as `(|...|)`? — effectfully, Oct 14 '15 at 13:47
definitely not the answer the OP's looking for but a good advanced applicative tutorial nevertheless! — Erik Kaplun, Oct 14 '15 at 14:37
@user3237465 It's a moot point. The short, bad answer is that I never got around to adding precedence/associaitivity handling to the SHE parser. The better answer is that idiom brackets give you one top level application. But arguably, they should apply for a whole code region, provided there is a clear way to signal which subtrees have gone back to "normal". — pigworker, Oct 15 '15 at 07:28

Erik Kaplun · Answer 3 · 2015-10-14T12:03:28.607

Well if you must use zipWith3:

sum3 :: Num a => [a] -> [a] -> [a] -> [a]
sum3 xs ys zs = zipWith3 (\x y z -> x + y + z) xs' ys' zs'
  where
    xs' = pad nx xs;  nx = length xs
    ys' = pad ny ys;  ny = length ys
    zs' = pad nz zs;  nz = length zs
    n   = nx `max` ny `max` nz
    pad n' = (++ replicate (n-n') 0)

Some samples:

*> sum3 [] [] []
[]
*> sum3 [0] [] []
[0]
*> sum3 [1] [1] [2, 2]
[4,2]
*> sum3 [1,2,3] [4,5] [6]
[11,7,3]

but I'd recommend going with Carsten's transpose based implementation.

Erik Kaplun · Answer 4 · 2015-10-14T12:22:04.777

Perhaps you could get away with something that is almost zipWith3 but which relies on Default to generate empty values on the fly if one of the lists runs out of elements:

import Data.Default

zipWith3' :: (Default a, Default b, Default c)
          => ( a  ->  b  ->  c  ->  r )
          -> ([a] -> [b] -> [c] -> [r])
zipWith3' f = go where
  go  []     []     []    =           []
  go (x:xs) (y:ys) (z:zs) = f x y z : go xs    ys    zs
  go  []     ys     zs    =           go [def] ys    zs
  go  xs     []     zs    =           go xs    [def] zs
  go  xs     ys     []    =           go xs    ys    [def]

and 'sum3'`:

sum3' :: (Default a, Num a) => [a] -> [a] -> [a] -> [a]
sum3' = zipWith3' (\x y z -> x + y + z)

chi · Answer 5 · 2015-10-14T16:03:10.243

2

One could generalize zipWith so to handle the excess tails, instead of discarding them silently.

zipWithK :: (a->b->c) -> ([a]->[c]) -> ([b]->[c]) -> [a] -> [b] -> [c]
zipWithK fab fa fb = go
  where go [] [] = []
        go as [] = fa as
        go [] bs = fb bs
        go (a:as) (b:bs) = fab a b : go as bs

The original zipWith is then

zipWith' :: (a->b->c) -> [a] -> [b] -> [c]
zipWith' f = zipWithK f (const []) (const [])

Back to the original problem,

sum2 :: Num a => [a] -> [a] -> [a]
sum2 = zipWithK (+) id id

sum3 :: Num a => [a] -> [a] -> [a] -> [a]
sum3 xs ys zs  = xs `sum2` ys `sum2` zs

edited Oct 14 '15 at 16:03

answered Oct 14 '15 at 12:51

chi

111,837
3
133
218

The previous answer seems correct, but this one is more general. Which should be accepted as the correct one? – Chiffa Oct 14 '15 at 13:31
Whichever you prefer! it doesn't matter at all in this case. – Erik Kaplun Oct 14 '15 at 14:33

score 0 · Answer 6 · answered Jul 23 '20 at 14:47

This is my solution:

sumLists :: Num a => [a] -> [a] -> [a]
sumLists (x : xs) (y : ys) = (x + y) : sumLists xs ys
sumLists _ _ = []

sum3 :: (Num a, Enum a) => [a] -> [a] -> [a] -> [a]
sum3 xs ys zs = foldr sumLists defaultList (map addElems list)
  where list = [xs, ys, zs]
        defaultList = [] ++ [0, 0 ..]
        maxLength = maximum $ map length list
        addElems = \x -> if length x < maxLength then x ++ [0, 0 ..] else x

sum3 with zipWith3 in Haskell

6 Answers6