[Haskell-cafe] Interesting problem from Bird (4.2.13)
rj248842 at hotmail.com
Wed Mar 4 10:07:29 EST 2009
Could someone provide an elegant solution to Bird problem 4.2.13?
Here are the problem and my inelegant solution:
Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures
concatenation as a primitive.
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".
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 []):
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe