[Haskell-cafe] Interesting problem from Bird (4.2.13)

[Ryan Ingram]

2009/3/4 R J <rj248842 at hotmail.com>:
> What's the pure solution that uses cases and recursion on
> CatList, not Haskell's built-in lists, to capture the equality of nested
> CatLists?

As Rafael pointed out, the simplest thing to do is to convert to a
canonical form; you can prove that each CatList has a single canonical
form and that two equal CatLists always have the same canonical form.

Something from Rafael's solution was bugging me, though.
> adjust                           :: CatList a -> CatList a
> adjust (Cat CatNil x) = x
> adjust (Cat x CatNil) = x -- *1
> adjust (Cat (Cat x y) z) = adjust (Cat x (Cat y z))
> adjust (Cat x y) = Cat (adjust x) (adjust y)  -- *2
> adjust x = x

*2 is the more odd one.  I was sure he had missed a case where the
result of the left "adjust" was incorrect.  But he didn't; the
interesting thing is that the left adjust is redundant.  The only case
left is "Wrap" which does nothing.

*1 is a bit odd because it breaks the nice symmetry of the pattern-matching.

Also, the CatNil cases both fail to adjust the results.

Here's my solution:

> canonical (Cat CatNil xs) = canonical xs
> canonical (Cat (Cat x y) z) = canonical (Cat x (Cat y z))
> canonical (Cat x xs) = Cat x (canonical xs) -- x is "Wrap e" for some e
> canonical (Wrap e) = Cat (Wrap e) CatNil
> canonical CatNil = CatNil

However, this is basically just converting to a list!  In canonical
form, a CatList always looks like this:

Cat (Wrap e1) $ Cat (Wrap e2) $ Cat (Wrap e3) $ ... $ CatNil

> canon_eq CatNil CatNil = True
> canon_eq (Cat (Wrap x) xs) (Cat (Wrap y) ys) = x == y && canon_eq xs ys
> canon_eq _ _ = False

> instance Eq a => Eq (CatList a) where xs == ys = canonical xs `canon_eq` canonical ys

Gleb's "viewCL" solution is also interesting, but it is also
equivalent to using lists, due to lazy evaluation.  In fact, an
efficient "toList" on CatLists is just "unfoldr viewCL".