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 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 DSimport Numeric.Search.RangeseqLast::Seq a -> aseqLast xs = index xs ((DS.length xs) - 1)-- Return the longest non-decreasing subsequence of an input sequence of integersnonDecreasing::[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
Longest non-decreasing subsequence, in Haskell
optimization;haskell