CODEWITHSUNDEEP
listhaskell
Nathan Edwards
Nathan Edwards

Reputation: 311

Working over a list of lists in Haskell

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

Upvotes: 5

Views: 23067

Answers (2)

AndrewC
AndrewC

Reputation: 32455

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.

Upvotes: 6

Chris Taylor
Chris Taylor

Reputation: 47392

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

Upvotes: 3

Related Questions