Working over a list of lists in Haskell

Question

I'm a bit of a beginner to Haskell so I'm struggling a little with the strict type stuff, just wondering if someone can help me with a function I'm trying to build. Basically, it takes a list of lists, for example:

[[1,2,3], [7,6,8], [0,3,4]]

and adds them together into one list translating the later lists by the number of positions along it is. So working on the example list it would actually be doing something like:

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

Here's my current function (which gets type errors):

    addLists :: [[Integer]] -> [Integer]
    addLists [[]] = []
    addLists [[x]] = [x]
    addLists [x:xs] = zipWith (+) [x] ([0]++ (addLists xs))

Please state explicitly what you want the result of addLists [[1,2,3], [7,6,8], [0,3,4]] to be. It is not obvious from your question. — dave4420
– dave4420, Commented Oct 31, 2012 at 11:45
It appears that you've edited your question to clarify it, but I'm afraid I still don't understand. What should the result of addLists [[1,2,3], [7,6,8], [0,3,4]] look like? The example you gave, foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]] doesn't type-check, and I can't figure out what you intended it to do. — mhwombat
– mhwombat, Commented Oct 31, 2012 at 11:56
Do you want the result to be [1, 2+7, 3+6+0, 8+4, 4] = [1,9,9,12,4]? — mhwombat
– mhwombat, Commented Oct 31, 2012 at 12:00

AndrewC · Accepted Answer · 2012-10-31 14:41:15Z

6

Note that ([0]++) is the same as (0:), which will make it look tidier and save us a nanosecond or two. (I'm joking with the nanosecond thing - no human can tell when something's a nanosecond faster, but it is nicer this way anyway.)

Let's first think about making the lists you need. We want

postponeLists [[1,2,3], [7,6,8], [10,20,30,40]] 
             = [[1,2,3], [0,7,6,8], [0,0,10,20,30,40]]
             = [1,2,3] : ones that should have zero in front of them

That's enough information for a definition:

postponeLists [] = []
postponeLists (l:ls) = l : map (0:) (postponeLists ls)

Now you said

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

but you mean

foldl (zipWith (+)) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]]

but unfortunately, that gives you [] because zipWith stops as soon as any of the lists run out of elements. We need some way of zipping them that doesn't stop.

Solution 1: find the longest one, make them all that maxlength using take maxlength.(++ repeat 0)
Solution 2: write another zipWith function that doesn't stop.

I prefer solution 2. Let's look at the definition of zipWith

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = [] -- here's the problem - it stops as soon as any list is empty

OK, let's not stop then:

zipWithMore :: (a -> a -> a) -> [a] -> [a] -> [a]
zipWithMore f (a:as) (b:bs) = f a b : zipWithMore f as bs
zipWithMore f []      bs      = bs -- if there's more in bs, use that
zipWithMore f as      []      = as -- if there's more in as, use that

Now you can replace zipWith (+) with zipWithMore (+). I'll leave the punchline to you.

edited Oct 31, 2012 at 14:41

answered Oct 31, 2012 at 12:21

AndrewC

32.5k7 gold badges81 silver badges115 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

shachaf Over a year ago

(0:) won't save you any nanoseconds over ([0]++), at least not with ghc -O2. (:) sometimes is nicer than (++) where either is applicable, but you shouldn't let nanosecond speculation like that shape your code.

AndrewC Over a year ago

@shachaf Of course not! I was pointing out by jokingly saying "save a nanosecond or two" that it's unnecessary. (0:) is nicer though, and I wanted to introduce that habit. Who cares about nanoseconds with a problem like this? I've made it clearer it wasn't meant seriously.

Chris Taylor · Accepted Answer · 2012-10-31 12:26:41Z

3

I think this does what you want

import Data.List (transpose)

addLists :: Num a => [[a]] -> [a]
addLists xs = map sum . transpose $ zipWith (\n x -> replicate n 0 ++ x) [0..] xs

edited Oct 31, 2012 at 12:26

answered Oct 31, 2012 at 12:14

Chris Taylor

47.7k15 gold badges113 silver badges156 bronze badges

3 Comments

Nathan Edwards Over a year ago

Thanks, can you explain exactly how it works? I can pretty much follow, but not quite!

Chris Taylor Over a year ago

@npfedwards Sorry, I meant to come back and expand this answer, but somethign else came up. Will get to it soon, I hope!

shachaf Over a year ago

A bit nicer: addLists = map sum . transpose . zipWith (++) (inits (repeat 0)). The interesting part is transpose, which is a Data.List function worth being familiar with with. Since this is a composition, you can play with each part individually to figure out how it works.

Collectives™ on Stack Overflow

Working over a list of lists in Haskell

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related