2009/3/4 R J <[email protected]>: > 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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
