← back

The next greatest number

16 September 2016

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 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]

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

Preamble

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

Calculating a solution

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...

Remarks

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.