map

Remember our good old map function. It allows us to transform the elements in a list by applying a function to each list element. The resulting list can have a different type than the input list, if the function we apply to each list element has different argument and return types. For example,

GHCi

>>> :t show
show :: Show a => a -> String
>>> map show [1,2,3,4,5]
["1","2","3","4","5"]

Since show turns its argument into a string, mapping show over a list of integers turns this list into a list of strings.

Here's the implementation of map:

map :: (a -> b) -> [a] -> [b]
map f = go
  where
    go (x:xs) = f x : go xs
    go _      = []

As we will learn when talking about functors, map is in fact merely the list-specific version of a more general function called fmap. fmap works for arbitrary containers, such as arrays, binary trees, etc.

Exercise

The standard library has a function

replicate :: Int -> a -> [a]

replicate n x creates a list of n copies of x:

GHCi

>>> replicate 3 1
[1,1,1]
>>> replicate 10 100
[100,100,100,100,100,100,100,100,100,100]

Implement this function. You should try to implement it manually, without the help of any functions in the standard library, and using map. For the implementation using map, you need two tools. First, the list comprehension [1..n] generates the list of all numbers between 1 and \(n\):

GHCi

>>> [1..10]
[1,2,3,4,5,6,7,8,9,10]

Second, there's a function we will use later when talking about functors and monads:

const :: a -> b -> a
const x _ = x

This function simply ignores its second argument and returns its first argument. It's more illuminating to partially apply it. const 5, for example, is a function that ignores its argument and always returns 5. Hence the name: it's the constant function.

Solution

Here's the manual implementation:

replicate :: Int -> a -> [a]
replicate n x = go n
  where
    go 0 = []
    go m = x : go (m - 1)

The implementation using map uses the following idea: We generate a list of length n. It doesn't matter what it contains, only that it has length n. An easy way to generate a list of length n is to use the list comprehension [1..n]. Now we use map to replace every element in this list with x. That gives us a list of n copies of x. The function we use to replace every element in [1..n] with x is const x. This gives the following implementation:

replicate :: Int -> a -> [a]
replicate n x = map (const x) [1..n]

Exercise

map allows us to apply a function to every list element and collect the results in a list. This works even if the function we apply returns a list. In that case, the result is a list of lists:

GHCi

>>> map (\x -> replicate x x) [1..5]
[[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5]]

It is quite common that we don't want a list of lists as the result but that we want the concatenation of the lists produced by applying our function to each list element. We can do this by applying concat to the result of map:

GHCi

>>> concat $ map (\x -> replicate x x) [1..5]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

Since this is a common thing to do, the standard library has a function that combines concat and map:

concatMap :: (a -> [b]) -> [a] -> [b]

It behaves exactly as if it were defined as

concatMap f xs = concat $ map f xs

GHCi

>>> concatMap (\x -> replicate x x) [1..5]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

However, in the interest of efficiency, concatMap is implemented directly, without the help of concat or map. Provide your own implementation of concatMap without using concat or map.

Solution

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = go
  where
    go []     = []
    go (x:xs) = f x ++ go xs