*I presented this article at the UCSD Math club lightning talks series, on September 30 2016.*

Today in the UCSD computer science facebook group someone posted this question (edited for clarity) ---

Given an unsorted array

Example: given`A`

, return an array`B`

where each element`B[i]`

is the index in array`A`

of the next element in`A`

the that is greater than the element`A[i]`

.`[1,4,10,3,5]`

return`[1,2,-1,4,-1]`

This is a prime candidate for some Bird-style equational reasoning! Let us calculate a solution.

```
import Control.Monad
import Data.List hiding (find)
```

To avoid confusing ourselves, let us make a type alias for list indices.

`type Index = Int`

and define an auxillary function from `Safe`

.

```
headMay :: [a] -> Maybe a
headMay [] = Nothing
headMay (x:_) = Just x
```

Our goal is a function

`nextGreater :: [Int] -> [Maybe Index]`

The first thing we have to do is to index the elements. We will use 0-based indexing, to be consistent with the problem statement.

```
indexed :: [a] -> [(Index, a)]
indexed = zip [0..]
```

For every element, we only examine the things to the right of it. We can enumerate all the subproblems with `tails`

. Because `tails`

includes the empty list as a suffix, we have to filter it out with `init`

.

Next, for each subproblem we shall scan its `tail`

, seeking the index of the first element greater than the `head`

. We want another function

`findGreater :: Ord a => [(Index, a)] -> Maybe Index`

implementing the following algorithm --- we shall first `uncons`

the list, which returns a `Nothing`

if the list has size < 1. Then, armed with a `head`

of `(_,e)`

, we will find the index of the first element in the `tail`

greater than `e`

.

This second step is simply a `filter ((> e) . snd)`

, plus some other guards to extract only the relevant information.

```
find :: Ord a => a -> [(Index, a)] -> Maybe Index
find e = headMay . map fst . filter ((> e) . snd)
```

In order to apply `find`

to an input `Maybe ((Index, a), [(Index, a)])`

, notice that the tuple returned by `uncons`

contain the two arguments to `find`

in a pair, and that the first element in this tuple is another tuple from which we must discard the `Index`

.

So we first sanitize the first argument with

`find . snd`

then uncurry the resulting function.

Finally note that we want to apply a monadic function to a value in the `Maybe`

monad, which we constructed by `uncons`

--- which is itself a monadic function with type

`[a] -> Maybe (a,[a])`

so we just plug the two functions together with Kleisli composition.

`findGreater = uncons >=> uncurry (find . snd)`

Now `nextMin`

can be written thusly:

`nextMin = map findGreater . init . tails . indexed`

Or with everything together:

```
nextGreater :: [Int] -> [Maybe Index]
nextGreater = map findGreater . init . tails . indexed
where
findGreater = uncons >=> uncurry (find . snd)
find e = headMay . map fst . filter ((> e) . snd)
```

And it works!

```
*Main> nextMin [1,4,10,3,5]
[Just 1,Just 2,Nothing,Just 4,Nothing]
```

I didn't even run the code until everything was written...

After writing this piece I flipped through *Pearls of Functional Algorithm Design* again, and found a problem surprisingly similar: *A Surpassing Problem* in Chapter 2. The interested reader encouraged to read it, and also the book in its entirety.