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 <ryani.s...@gmail.com> wrote: > 2009/3/4 R J <rj248...@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". > _______________________________________________ > 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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe