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
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
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 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
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
(_,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.
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
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)
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.