# Reduce is flatMap

I used to think of `reduce`

and `flatMap`

as two fundamental functions. But could I
imagine they were two versions of the same function?

```
flatMap :: (a -> [b]) -> [a] -> [b]
reduce :: (b -> a -> b) -> b -> [a] -> b
```

Do they look similar? Not at all.

We are not going to use Functor and Foldable abstractions for now

to keep this article accessible for most programmers.

To begin with, `flatMap`

is a terrible name. Yes, `flatMap = flatten . map`

but names
should not derive from implementation. That's in the basics of naming things.

Describe what function

doesrather than how it'sbuilt...

– But `flatMap`

flattens and maps! – you say.

Not exactly. Ironically, it's easy to increase nesting with `flatMap`

but impossible to decrease.

```
flatMap (\x -> x) [1, 2, 3] -- -1 nesting level... ERROR
flatMap (\x -> [x]) [1, 2, 3] -- 0 same nesting
flatMap (\x -> [[x]]) [1, 2, 3] -- +1 nesting level
flatMap (\x -> [[[x]]]) [1, 2, 3] -- +2 nesting levels
```

Now let's look at implementations:

```
flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f [] = []
flatMap f (x : xs) = f x ++ flatMap xs
```

```
reduce :: (a -> b -> b) -> b -> [a] -> b
reduce f z [] = z
reduce f z (x : xs) = f x (foldr f z xs)
```

In ECMAScript `Array.reduce`

accepts arguments in the `acc, item`

order. In Haskell there are plenty of
`reduce`

versions. Some of them are left- and some are right-associative.

```
reduceFn :: b -> a -> b -- b is acc type
-- or --
reduceFn :: a -> b -> b -- --//--
```

Technically speaking, they are equivalent. Who cares about argument order nowadays?
But second version is interesting because it returns an endofunctor `b -> b`

. Keeping
that in mind, let's move along.

You probably tried to express `flatMap`

in terms of `reduce`

.

It's rather trivial

`flatMap f = reduce ((++) . f) []]`

Now let's try to express `reduce`

in terms of `map`

.

`reduce f z xs = ???`

The only thing that comes to mind is

`reduce f z xs = ??? (map f xs) ???`

but is this even possible, given that `f`

for `map`

and `f`

for `reduce`

have different number of arguments?

In second thought – yes. We just end up with a list of functions

`map (+) [1, 2, 3] -- [(+1), (+2), (+3)]`

Looks like a middle step. Now we just need to somehow merge those functions together. And also do something about initial value.

We merge functions by composing them. So we can write `compose`

function

```
compose :: [(b -> b)] -> (b -> b)
compose [] = id
compose (f : fs) = f . (compose fs)
```

which basically does `f5 . f4 . f3 ...`

for imaginary list of five functions.

So if we compose funcs from that list and apply the result to initial value...

should it reproduce the original `reduce`

behavior? Let's check.

```
reduce f z xs = compose (map f xs) z
---
reduce (+) 0 [1, 2, 3] -- 6
reduce (*) 0 [1, 2, 3] -- 6
```

It works! Interesting.

Now `flatMap`

is like

```
flatMap f xs = ... ++ (ys !! 2) ++ (ys !! 1) ++ (ys !! 0)
where ys = map f xs
```

while `reduce`

is like

```
reduce f z xs = ... . (ys !! 2) . (ys !! 1) . (ys !! 0) $ z
where ys = map f xs
```

And if we remove accumulator and just return a final function

```
reduce f xs = ... . (ys !! 2) . (ys !! 1) . (ys !! 0)
where ys = map f xs
```

Oops. Now it's obvious the only difference between `flatMap`

and `reduce`

is a "glue" operation.
It's `++`

for `flatMap`

and `.`

for `reduce`

.

In this particular case `++`

"glues" lists and `.`

"glues" functions. Which functions?
It depends on the `reduceFn`

argument order and is either `a -> b`

or `b -> b`

.
We'll concentrate on the second case.

`b -> b`

is an endofunctor and a straighforward monoid.

List has an identity element of `[]`

(empty list) and
endofunctor has an identity element of `id`

(identity) function.

```
[] ++ [] ++ [] == []
id . id . id == id
```

Can't we rely on that to abstract things furher? Yes we can.

```
[1] ++ [2] ++ [3] == mconcat [[1], [2], [3]] == [1, 2, 3]
(+1) . (+2) . (+3) == mconcat [(+1), (+2), (+3)] == (\x -> ((x + 3) + 2) + 1)
```

Well, the latter actually does not work... Because in Haskell `a -> a`

has no predefined
monoid instance. The one of possible workarounds is `Endo`

.

```
import Data.Monoid
mconcat [Endo (+1), Endo (+2), Endo (+3)] `appEndo` 0 == 6
```

So we have this candidate function which should behave (almost) like both `flatMap`

and `reduce`

given the right arguments.

`fancyMap f xs = mconcat (map f xs)`

Check:

```
fancyMap (\x -> [2 * x]) [1, 2, 3] -- [2, 4, 6]
fancyMap (Endo . (+)) [1, 2, 3] `appEndo` 0 -- 6
```

We can also mess with GHC a tiny bit

```
{-# LANGUAGE FlexibleInstances #-}
instance {-# OVERLAPPING #-} Monoid (a -> a) where
mempty = id
mappend f g = f . g
```

Behold:

```
fancyMap (\x -> [2 * x]) [1, 2, 3] == [2, 4, 6]
fancyMap (+) [1, 2, 3] 0 == 6
```

Now you see how `flatMap`

and `reduce`

are the same thing ;)

We can definitely abstract remaining list stuff

```
import Data.Monoid
import Data.Foldable
fmap :: Functor f => (a -> b) -> f a -> f b -- abstracted `map`
fold :: (Foldable t, Monoid m) => t m -> m -- abstracted `mconcat`
fancyMap :: (Monoid m, Functor f, Foldable f) => (a -> m) -> f a -> m
fancyMap f xs = fold (fmap f xs)
```

and Haskell goes even further, removing `Functor`

requirement but the more
abstractions we pile up – the more esoteric it becomes.

Enough for today. I hope it was useful. At the very least now you can explain
why it's possible to both map and filter with `reduce`

and `flatMap`

.