Longest non-decreasing subsequence, in Haskell

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

A few general remarks

I find that stepped whiles are as evil as nested if statements for readability of the code. Here, you have three levels of nesting.
Relying on the surrounding environment for variables can some times obscure possibility to generalize (You make use of x and m for inner definitions)

So here is what I would do

import Data.Sequence as DS
import Numeric.Search.Range as R

seqLast::Seq a -> a
seqLast xs = index xs ((DS.length xs) - 1)

insert_idx :: Ord a => a -> Seq [a] -> Maybe Int
insert_idx y m = searchFromTo (fn y) 0 $ (DS.length m) - 1
  where fn y idx = y  [Int]
nonDecreasing = Prelude.reverse . seqLast . makeM
  where makeM = foldl updateM empty
        updateM m x | DS.null m = singleton [x]
                    | otherwise = case insert_idx x m of
                        Nothing -> m |> (x: seqLast m)
                        Just l -> update l (x:geti l m) m
        geti 0 _ = []
        geti l m = index m (l -1)

StackExchange Code Review Q#10349, answer score: 2