# Implementing concatMap

### Implementing concatMap

The `concat`

function joins a list of lists into a single
list:

```
concat [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]
```

Prelude provides a function named `concatMap`

that can be
naively implemented by composing `concat`

and
`map`

:

`concatMap f = concat . map f`

Try implementing `concatMap`

using
`foldl`

and `foldr`

. Which one is
better? Why?

### Hints

## Click to reveal

Remember that you can concatenate two lists using the `(<>)`

operator:

```
1,2,3] <> [4,5,6]
λ [1,2,3,4,5,6] [
```

## Click to reveal

You can concatenate two lists by folding over them using the `(<>)`

operator.

```
= foldl (<>) []
λ concatFoldl 1,2],[3,4],[5,6]]
λ concatFoldl [[1,2,3,4,5,6] [
```

## Click to reveal

You can map over a list by applying your function and then adding the result to
a new list using `(:)`

```
= foldr (\x acc -> f x : acc) []
λ mapFoldr f +1) [1..10]
λ mapFoldr (2,3,4,5,6,7,8,9,10,11] [
```

### Solution

## Click to reveal

We can write `concatMap`

easily using either `foldl`

or `foldr`

. Let’s take a
look at a `foldr`

based version first:

`= foldr (\x acc -> f x <> acc) [] concatMapFoldr f `

Like the other examples where we’ve used `foldr`

, this version of `concatMap`

is
lazy and well-behaved when we need to deal with infinite lists. The most obvious
example of this is directly passing an infinite list to `concatMapFoldr`

:

```
take 10 $ concatMapFoldr (\x -> [x,x]) [1..]
λ 1,1,2,2,3,3,4,4,5,5] [
```

We can also handle cases where the input is a finite list, but our function
outputs infinite lists that we we want to concatenate together. You’ll notice in
this example we’re using a new function: `repeat`

. This function takes a value
and generates a list of that value repeated indefinitely:

```
-- When we return an infinite list for each finite input element
take 10 $ concatMapFoldr (\x -> repeat x) [1,2,3]
λ 1,1,1,1,1,1,1,1,1,1] [
```

As you might expect, we can also handle both cases at the same time. Even with an infinitely long input, and a function that generates infinitely long lists from each input, we’re still able to get a finite result:

```
-- When we return an infinite list for each of infinite inputs
take 10 $ concatMapFoldr (\x -> repeat x) [1..]
λ 1,1,1,1,1,1,1,1,1,1] [
```

We can implement a `foldl`

based version of `concatMap`

just as easily as our
`foldr`

version, we just need to flip around the order of some of our operations:

`= foldl (\acc x -> acc <> f x) [] concatMapFoldl f `

As you might expect, this version of `concatMap`

doesn’t do well with infinite
lists. Whether you pass in an finitely list, generate one with the function you
pass in, or both, `concatMapFoldl`

will hang and ever complete.

#### So, Which One Is Better?

In most cases, `concatMapFoldr`

is the version of this function that we’d want.
If we look at the behavior of the `concatMap`

defined for us in `Prelude`

you’ll notice it’s behavior with infinite lists matches our `foldr`

based
implementation:

```
take 10 $ concatMap repeat [1..]
λ 1,1,1,1,1,1,1,1,1,1] [
```