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 arrayExample: given
A, return an array
Bwhere each element
B[i]is the index in array
Aof the next element in
Athe that is greater than the element
To avoid confusing ourselves, let us make a type alias for list indices.
and define an auxillary function from
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 includes the empty list as a suffix, we have to filter it out with
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
(_,e), we will find the index of the first element in the
tail greater than
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
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.
nextGreater can be written thusly:
Or with everything together:
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.