Good point Ryan,<br><br>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<br>
<br>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.<br><br>Best Regards,<br><br>Rafael<br><br><div class="gmail_quote">
On Wed, Mar 4, 2009 at 15:55, Ryan Ingram <span dir="ltr"><<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
2009/3/4 R J <<a href="mailto:rj248842@hotmail.com">rj248842@hotmail.com</a>>:<br>
<div class="im">> What's the pure solution that uses cases and recursion on<br>
> CatList, not Haskell's built-in lists, to capture the equality of nested<br>
> CatLists?<br>
<br>
</div>As Rafael pointed out, the simplest thing to do is to convert to a<br>
canonical form; you can prove that each CatList has a single canonical<br>
form and that two equal CatLists always have the same canonical form.<br>
<br>
Something from Rafael's solution was bugging me, though.<br>
<div class="im">> adjust :: CatList a -> CatList a<br>
> adjust (Cat CatNil x) = x<br>
</div>> adjust (Cat x CatNil) = x -- *1<br>
<div class="im">> adjust (Cat (Cat x y) z) = adjust (Cat x (Cat y z))<br>
</div>> adjust (Cat x y) = Cat (adjust x) (adjust y) -- *2<br>
> adjust x = x<br>
<br>
*2 is the more odd one. I was sure he had missed a case where the<br>
result of the left "adjust" was incorrect. But he didn't; the<br>
interesting thing is that the left adjust is redundant. The only case<br>
left is "Wrap" which does nothing.<br>
<br>
*1 is a bit odd because it breaks the nice symmetry of the pattern-matching.<br>
<br>
Also, the CatNil cases both fail to adjust the results.<br>
<br>
Here's my solution:<br>
<br>
> canonical (Cat CatNil xs) = canonical xs<br>
> canonical (Cat (Cat x y) z) = canonical (Cat x (Cat y z))<br>
> canonical (Cat x xs) = Cat x (canonical xs) -- x is "Wrap e" for some e<br>
> canonical (Wrap e) = Cat (Wrap e) CatNil<br>
> canonical CatNil = CatNil<br>
<br>
However, this is basically just converting to a list! In canonical<br>
form, a CatList always looks like this:<br>
<br>
Cat (Wrap e1) $ Cat (Wrap e2) $ Cat (Wrap e3) $ ... $ CatNil<br>
<br>
> canon_eq CatNil CatNil = True<br>
> canon_eq (Cat (Wrap x) xs) (Cat (Wrap y) ys) = x == y && canon_eq xs ys<br>
> canon_eq _ _ = False<br>
<br>
> instance Eq a => Eq (CatList a) where xs == ys = canonical xs `canon_eq` canonical ys<br>
<br>
Gleb's "viewCL" solution is also interesting, but it is also<br>
equivalent to using lists, due to lazy evaluation. In fact, an<br>
efficient "toList" on CatLists is just "unfoldr viewCL".<br>
<div><div></div><div class="h5">_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Rafael Gustavo da Cunha Pereira Pinto<br>Electronic Engineer, MSc.<br>