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

Good point Ryan, I did it in my lunch time and, being in a hurry, overlooked the fact that left adjust in (*2) is redundant and that (*1) can be completely removed by using (adjust x). I actually think I added (*2) for "safety"!! :-D R J, you should take a look on Chris Okasaki's book. This is pretty much what he does all the time to make sure invariants in his data structures are met. Best Regards, Rafael On Wed, Mar 4, 2009 at 15:55, Ryan Ingram wrote:

2009/3/4 R J :

...

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". _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.