[Haskell-cafe] (no subject)

[Richard O'Keefe]

On 5 Mar 2009, at 4:02 am, R J wrote:

> Could someone provide an elegant solution to Bird problem 4.2.13?

This is the classic Lisp "SAMEFRINGE" problem in disguise.

You say that the method of converting CatLists to lists and then
comparing those is a "hack", but I take leave to doubt that.
It's easy to get right, and it works.

== and < are, in general, O(n) operations on lists,
so the O(n) cost of converting trees to lists isn't
unreasonable.  In fact given ((((((Wrap 1) ++ ..) ++ ..) ....)
it can take O(n) time to reach the very first element.
Best of all, the fact that Haskell is lazy means that
converting trees to lists and comparing the lists are
interleaved; if comparison stops early the rest of the
trees won't be converted.

One way to proceed in a strict language is to work with a
(pure) state involving
	- the current focus of "list" 1
	- the current focus of "list" 2
	- the rest of "list" 1 (as a list of parts)
	- the rest of "list" 2 (as a list of parts).

I thought I had demonstrated this when one last check showed
a serious bug in my code.  In any case, this relies on lists
to implement the stacks we use for "the rest of the tree".
Your "unwrap" approach is much easier to get right.