Mine is somewhat more elegant... data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) deriving Show instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True Wrap x == Wrap y = x==y a@(Cat x y) == b = case (adjust a) of CatNil -> b==CatNil Wrap x -> (adjust b)==Wrap x Cat x y -> case (adjust b) of Cat z w -> (x==z) && (y==w) otherwise -> False b == a@(Cat x y) = a==b _ == _ = False adjust :: CatList a -> CatList a adjust (Cat CatNil x) = x adjust (Cat x CatNil) = x adjust (Cat (Cat x y) z) = adjust (Cat x (Cat y z)) adjust (Cat x y) = Cat (adjust x) (adjust y) adjust x = x You don't have to evaluate everything. Just do a recursion fixing the associative rule. 2009/3/4 R J

Could someone provide an elegant solution to Bird problem 4.2.13?

Here are the problem and my inelegant solution:

Problem -------

Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive.

For example,

data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a)

The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y.

However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal.

Define appropriate instances of "Eq" and "Ord" for "CatList".

Inelegant Solution ------------------

The following solution works:

instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True CatNil == Wrap z = False CatNil == Cat z w = ( z == CatNil && w == CatNil )

Wrap x == CatNil = False Wrap x == Wrap z = x == z Wrap x == Cat z w = ( Wrap x == z && w == CatNil ) || ( Wrap x == w && z == CatNil )

Cat x y == CatNil = x == CatNil && y == CatNil Cat x y == Wrap z = ( x == Wrap z && y == CatNil ) || ( x == CatNil && y == Wrap z ) Cat x y == Cat z w = unwrap (Cat x y) == unwrap (Cat z w)

unwrap :: CatList a -> [a] unwrap CatNil = [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y

instance (Eq a, Ord a) => Ord (CatList a) where x < y = unwrap x < unwrap y

This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]):

Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1) == Wrap (Cat (Wrap 1) CatNil)

Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists.

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?

------------------------------ Windows Live™ Contacts: Organize your contact list. Check it out.http://windowslive.com/connect/post/marcusatmicrosoft.spaces.live.com-Blog-c...

_______________________________________________ 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.

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".

2009/3/4 R J :

Could someone provide an elegant solution to Bird problem 4.2.13?

Here are the problem and my inelegant solution:

Problem -------

Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive.

For example,

data (CatList a)       =  CatNil                        |  Wrap a                        |  Cat (CatList a) (CatList a)

The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y.

However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal.

Define appropriate instances of "Eq" and "Ord" for "CatList".

Inelegant Solution ------------------

The following solution works:

instance (Eq a) => Eq (CatList a) where     CatNil      ==  CatNil       =    True     CatNil      ==  Wrap   z     =    False     CatNil      ==  Cat    z w   =  ( z == CatNil  && w == CatNil )

    Wrap   x    ==  CatNil       =    False     Wrap   x    ==  Wrap   z     =    x == z     Wrap   x    ==  Cat    z w   =  ( Wrap x == z  && w == CatNil ) ||                                     ( Wrap x == w  && z == CatNil )

    Cat    x y  ==  CatNil       =    x == CatNil  && y == CatNil     Cat    x y  ==  Wrap   z     =  ( x == Wrap z  && y == CatNil ) ||                                     ( x == CatNil  && y == Wrap z )     Cat    x y  ==  Cat    z w   =  unwrap (Cat x y) == unwrap (Cat z w)

unwrap                           :: CatList a -> [a] unwrap CatNil                    =  [] unwrap (Wrap x)                  =  [x] unwrap (Cat x y)                 =  unwrap x ++ unwrap y

instance (Eq a, Ord a) => Ord (CatList a) where     x < y = unwrap x < unwrap y

This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]):

Wrap 1                               == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1)                        == Wrap (Cat (Wrap 1) CatNil)

Although this solution works, it's a hack, because unwrap converts CatLists to lists.  The question clearly seeks a pure solution that does not rely on Haskell's built-in lists.

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?

________________________________ Windows Live™ Contacts: Organize your contact list. Check it out. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Here's my solution. I first "right factor" each catlist by converting a catlist into a difference catlist[1] and then turning that into a catlist again by applying it to Nil. At this point the converted catlist always has a right factored form: 'Cat a (Cat b (Cat c Nil)))' which also doesn't contain Nils except at the end. That right factored catlist is easy to compare with 'eq'. ------------------------------------------------------------------------------- data CatList a = Nil | Wrap a | Cat (CatList a) (CatList a) deriving Show type DiffCatList a = CatList a -> CatList a diff :: CatList a -> DiffCatList a diff (Cat xs ys) = diff xs . diff ys diff Nil = id diff w = Cat w rightFactor :: CatList a -> CatList a rightFactor xs = diff xs Nil instance Eq a => Eq (CatList a) where xs == ys = rightFactor xs `eq` rightFactor ys where Nil `eq` Nil = True Wrap x `eq` Wrap y = x == y Cat xs1 ys1 `eq` Cat xs2 ys2 = xs1 `eq` xs2 && ys1 `eq` ys2 _ `eq` _ = False ------------------------------------------------------------------------------- (Right now I'm thinking if it's possible to fuse the 'diff' and the 'eq' somehow so that we don't have to turn the DiffCatList into a catlist again...) regards, Bas [1] http://haskell.org/haskellwiki/Difference_list