OK, so I recently posted [this solution in Python][1] to the [longest non-decreasing subsequence problem][2], 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][3] [answers][4] 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 `n`.

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



  [1]: http://codereview.stackexchange.com/questions/10230/python-implementation-of-the-longest-increasing-subsequence-problem
  [2]: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
  [3]: http://stackoverflow.com/questions/9825693/looking-for-an-efficient-array-like-structure-that-supports-replace-one-member
  [4]: http://stackoverflow.com/questions/9856293/looking-for-a-generic-bisect-function