Haskell - How to transform map sum (map (x:) xss) to map (x+) (map sum xss)

Question

Reading "Thinking Functionally with Haskell" I came across a part of a program calculation that required that map sum (map (x:) xss) be rewritten as map (x+) (map sum xss)

Intuitively I know that it makes sense ...

if you have some lists that you are going to sum but, before summing, to those same lists you are also going to add one element 'x', then that is the same as taking a list of sums of the origninal lists and adding x's value to each of them.

But I would like to know how to transform one into the other only using equational reasoning. I feel like I'm missing a law or rule that would help me understand.

Delija

Answer 1

Using the law

map f (map g list) === map (f . g) list

We can deduce

map sum (map (x:) xss) =
map (sum . (x:)) xss =

eta-expand to give an argument to work with

map (\xs -> sum . (x:) $ xs) xss =

Substituting in for (f . g) x === f (g x)

map (\xs -> sum (x:xs)) xs =

Where

sum (x:xs) = x + sum xs
sum [] = 0

so

map (\xs -> sum (x:xs)) xss =
map (\xs -> x + sum xs) xss =

Substituting f (g x) === (f . g) x

map (\xs -> (x +) . sum $ xs) xss =

eta-reduce the lambda

map ((x +) . sum) xss =

The use the reverse of the first law from above

map (x+) (map sum xss)

Crosswalk

I disagree about the list comprehension, but it's certainly a matter of taste. Why not just use the definition of (.) and say map (sum . (x:)) xss = map (\ xs -> sum (x:xs)) xss = map (\ xs -> x + sum xs) = ... ? – Pomelo

@Pomelo Eh, personal taste. In this case it's rather unimportant, but I could see the argument for keeping map in there the whole time. – Crosswalk

@Pomelo look better? – Crosswalk

Somewhat :) But the eta-expansion is unnecessary. The lambda is introduced by reducing (.). – Pomelo

Answer 2

I recommend you look at the types and let them guide you through the transformation.

> let xss = [[1], [2], [3]]
> :t xss
xss :: Num t => [[t]]
> map sum xss     -- basically compacting the lists
[1,2,3]
> :t map sum xss  -- into just a list of numbers
map sum xss :: Num b => [b]

Next we need to do the addition

> :t (+5)
(+5) :: Num a => a -> a
> :t map (+5)     --  no magic in this
map (+5) :: Num b => [b] -> [b]
> map (+5) (map sum xss)
[6,7,8]

The bottom line I'd guess is that in the first example you're changing the types in the other way than in the second one. The point where a list of lists becomes just a list changes, and so has the way in which you add the number.

Moonfish