title: The next greatest number date: 2016-09-16 ---

*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) ---

<blockquote> Given an unsorted array `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]`

.

Example: given `[1,4,10,3,5]`

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

</blockquote>

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

and define an auxillary function from `Safe`

.

Our goal is a function

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.

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

implementing the following algorithm --- we 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.

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

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

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

Now `nextGreater`

can be written thusly:

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!

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.