CODEWITHSUNDEEP
haskell
Chiffa
Chiffa

Reputation: 1506

sum3 with zipWith3 in Haskell

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?

Upvotes: 2

Views: 1331

Answers (6)

Narek Karapetyan
Narek Karapetyan

Reputation: 11

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

Upvotes: 0

chi
chi

Reputation: 116139

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

Upvotes: 2

pigworker
pigworker

Reputation: 43383

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.

Upvotes: 6

Erik Kaplun
Erik Kaplun

Reputation: 38217

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)

Upvotes: 2

Erik Kaplun
Erik Kaplun

Reputation: 38217

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.

Upvotes: 2

Random Dev
Random Dev

Reputation: 52280

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]

Upvotes: 12

Related Questions