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

[Rafael Gustavo da Cunha Pereira Pinto]

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.spam at gmail.com> wrote:

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



-- 
Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090304/a32ef4d3/attachment.htm