OK, so I recently posted this solution in Python to the longest non-decreasing subsequence problem, and cleaned it up with some expert advice. As a next step, I wanted to translate this solution into Haskell. This presents a challenge because the algorithm as originally formulated depends heavily on mutable arrays with O(1) lookup and update behavior, which are standard in Python but a little harder to come by in Haskell.
Some excellent answers on Stackoverflow pointed me towards
Data.Seq as a mutable, indexable array type, and
Numeric.Search.Range for a generic binary search operation (which is key to making the algorithm efficient).
I wanted to express this algorithm as a fold over the input list because that seemed like a natural way to do it. However the Python version depends on many O(1) lookups to arbitrary places in the input list - not really possible within a Haskell fold over an ordinary list. I saw that this could be avoided by, rather than doing what the Python version does - namely storing indices into the input array of "the best subsequence of length n found so far" - storing the best actual subsequence as a Haskell list. At first sight, this seems incredibly wasteful, because at the end of the calculation for an input list of length
n there could be as many as
n "best subsequence" lists which are on average
n / 2 long, creating space requirements of order
n^2! However, since these are Haskell lists derived from each other, they actually share a lot of the same space... for example, in the case where the input list is already a non-decreasing list of length
n, the calculation will involve creating
n subsequence lists of lengths [1..n], but each one shares a tail with its predecessor and the total space requirement is just proportional to
The code is below. What I am looking for is: 1) general comments on readability, correctness, etc. and 2) a way to prove an upper bound on the space requirement.
import Data.Sequence as DS import Numeric.Search.Range seqLast::Seq a -> a seqLast xs = index xs ((DS.length xs) - 1) -- Return the longest non-decreasing subsequence of an input sequence of integers nonDecreasing::[Int]->[Int] nonDecreasing = Prelude.reverse . seqLast . makeM where makeM = foldl updateM empty where updateM m x | DS.null m = singleton [x] | insert_idx == Nothing = m |> (x:(seqLast m)) | just_insert_idx == 0 = update 0 [x] m | otherwise = update just_insert_idx (x:(index m (just_insert_idx - 1))) m where insert_idx = searchFromTo (\idx -> x < (head (index m idx))) 0 ((DS.length m) - 1) just_insert_idx = maybe 0 id insert_idx