Haskell: List Comprehensions and higher-order functions

Question

I've tried to transform the following list comprehension:

f xs = [ x+8 | (x,_) <- xs ]

using higher-order functions.

My first solution was:

f' xs = map (\(x,_) -> x+8) xs

After I tried various other approaches, I found out that the following also works:

f' xs = map((+8).fst) xs

Both versions of f' give the same (correct) output, but I don't understand why (+8).fst is equal to \(x,_) -> x+8 when using map on a list of tuples.

Answer 1

The definition of fst is

fst :: (a, b) -> a
fst (a, _) = a

and the definition of (.) is

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) = \x -> f (g x)

If we use these definitions to expand your function, we get

f' xs = map ((+8) . fst) xs
f' xs = map (\x -> (+8) (fst x)) xs         -- definition of (.)
f' xs = map (\x -> (+8) ((\(a, _) -> a) x)) -- definition of fst
f' xs = map (\(a, _) -> (+8) a)             -- we can move the pattern matching
f' xs = map (\(a, _) -> a + 8)              -- expand section

Answer 2

Both versions of f' give the same (correct) output, but I don't understand why (+8).fst is equal to (x,_) -> x+8 when using map on a list of tuples.

The type of fst is:

fst :: (a, b) -> a

and what it does is it takes the first element of a pair (a tuple of two elements).

The type of (+8) is:

(+8) :: Num a => a -> a

and what it does is it takes as input a Num, applies + 8 to it and returns the result.

Now, the type of (+8) . fst is:

((+8).fst) :: Num c => (c, b) -> c

which is the composition of fst and (+8). Specifically it's the function that takes as input a pair, extracts the first element and adds 8 to it.

This can be easily seen by seen an example:

((+8).fst) (3, 'a')
-- 11

The same thing happens with \ (x, _) -> x + 8. You take a pair as input (in the lambda), pattern match the first argument to x, increment it by 8 and return it:

(\ (x, _) -> x + 8) (3, 'a')
-- 11