# Clojure's Short Circuit Reduce in Haskell

Clojure's `reduce`

has a feature its users are quite fond of: the ability to short-circuit evaluate using the `reduced`

function. Here I'm going to reconstruct this behaviour from scratch in Haskell, and then show it's built into Haskell's fundamental abstractions.

`reduced`

works by wrapping the return value. The `reduce`

function specially detects this type and unwraps it before returning the value.

The declaration of `foldr`

in Haskell is as follows:

`foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b`

(At least that's the sensible definition, but let's not go there.)

Here, `b`

is the accumulator value, the initial value and the return value. Since we want to represent the value that may or may not be a short circuit value, let's use `Either`

.

`foldr2 :: Foldable t => (a -> b -> Either b b) -> b -> t a -> b`

We're assuming `Left`

is the short circuit value, and `Right`

is a normal accumulator value. Let's say we're building `foldr2`

using foldr. If we substituted `Either b b`

for `b`

we'd get the following:

`foldr' :: Foldable t => (a -> Either b b -> Either b b) -> Either b b -> t a -> Either b b`

We need to figure out how to take the inputs of `foldr2`

and turn them into the inputs of `foldr'`

(which are actually just the inputs of `foldr`

).

## Don't Fear The Monad

`Either`

is a monad. Don't worry, I'm not about to explain what a monad is. I'm just going to tell you. `Either`

being a monad means there's two functions, `pure`

and `=<<`

(the second of which I wish had a name).

```
pure :: (Monad m) => a -> m a
=<< :: (Monad m) => (a -> m b) -> (m a -> m b)
```

or, in the case of `Either a a`

`pure :: a -> Either a a`

which is actually just the `Right`

constructor

`=<< :: (a -> Either c b) -> (Either c a -> Either c b)`

which just means "map the right side but not the left". (Usually Haskell doesn't show the brackets on the right, I think it's more clear for our purposes though.)

## Resolving the Reduction Function

So, how can we use this to solve our problem?

`reduceFunction :: (a -> b -> Either b b) -> (a -> Either b b -> Either b b)`

Let's put some more brackets in it:

`reduceFunction :: (a -> (b -> Either b b)) -> (a -> (Either b b -> Either b b))`

Interesting, the bits in brackets are just the `=<<`

function.

```
reduceFunction :: (a -> b -> Either b b) -> a -> Either b b -> Either b b
reduceFunction rf a b = (=<<) (rf a) b
```

So we partially applied the original reduction function with the first argument, then applied `=<<`

to promote it to `Either b b -> Either b b`

.

Let's apply a little trick: if you add a `.`

to a function, you can take the last expression in the next bracket outside of the bracket (in paredit talk, a barf).

`reduceFunction rf a b = ((=<<) .) (rf) a b`

or, in fact

`reduceFunction rf = (=<<) . rf`

## Finishing Off The Details

If we now need to make the initial value an `Either b b`

. That's easy, that's the other `Monad`

function: `pure`

. Finally, we need to extract the value out at the end

```
extract :: Either b b -> b
extract = either id id
```

`either`

is a function that takes two extraction functions that return the same type and applies the correct one. In our case, we just use the identity function on both sides.

```
foldr2 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr2 rf i l = extract $ foldr (reduceFunction rf) (pure i) l
```

I'm sure I've mentioned `$`

before, but it just means "put brackets around everything after this point". With some trickery (actually, just the trick I described before, applied multiple times) we can turn that into

```
foldr3 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr3 rf i = extract . (foldr ((=<<) . rf) . pure) i
```

Let's do a quick test as well

```
sumOdd :: (Integral a) => a -> a -> Either a a
sumOdd x y = if' (odd x) (Right $ x + y) (Left y)
```

```
result :: Int
result = foldr9 sumOdd 0 [1, 3, 5, 6, 2, 3, 5]
```

Note that this gives us the sum of odd numbers from the right, not the left. This is the natural thing in Haskell, but completely crazy in Clojure. Strictly speaking, we should have been working on `fold'`

in the first place.

## Dubious Extraction

We've established that we *can* implement Clojure's `reduce`

abstraction. But if we take a look at our solution, only `extract`

actually relies on it being an `Either`

. So, if we threw that away we'd have

```
foldr3' :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> Either b b
foldr3' rf i = (foldr ((=<<) . rf) . pure) i
```

Now we're returning the still wrapped value, but we're only using functions that depend on `Monad`

. So, we could have the type signature a lot more general without changing the code:

`foldr4 :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b`

That looks pretty general. What happens if `m`

is a `Maybe`

? Then you get something that short circuits on `nil`

. If `m`

is `List`

you get something that keeps expanding a list, like how we solved the Fox Goose Corn problem. I have no idea what it does for `State`

and `Reader`

, but it's probably useful.

Let's hoogle it.

`foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b`

Oh, the function already exists (with a very different implementation, but it's functionally identical to what we did above).

So, our final version should probably just use that:

```
foldr5 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr5 rf initial list = extract $ foldrM rf initial list
```