[Haskell-cafe] Code Review Request - Unbalanced Parenthesis correction

[Richard A. O'Keefe]

I note that Ying's thesis on repairing bracket structure in XML
is a cubic time algorithm.  It's not immediately obvious to me
that an algorithm computing "optimal" repairs for bracket structures
can be faster than quadratic time.  Everything hinges on what the
requirements actually are.

space?
> I'm certain that my use of Data.Sequence, and therefore finger trees, has this code at O(1) time.
> Doesn't using a lazy list mean I am using O(1) space?

If the input has m characters and the output has n characters,
the algorithm MUST take at least O(m+n) time.

Two people have independently proposed basically the same
streaming algorithm taking O(m+n) time and O(1) space with
lazy Strings, and one of them proposed an algorithm that
would reproduce the few test cases you provided, still with
O(m+n) time and O(1) space, without finger or any other trees.

Negotiating the specification comes first.