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™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009
On 5 Mar 2009, at 4:02 am, R J wrote:
Could someone provide an elegant solution to Bird problem 4.2.13?
This is the classic Lisp "SAMEFRINGE" problem in disguise. You say that the method of converting CatLists to lists and then comparing those is a "hack", but I take leave to doubt that. It's easy to get right, and it works. == and < are, in general, O(n) operations on lists, so the O(n) cost of converting trees to lists isn't unreasonable. In fact given ((((((Wrap 1) ++ ..) ++ ..) ....) it can take O(n) time to reach the very first element. Best of all, the fact that Haskell is lazy means that converting trees to lists and comparing the lists are interleaved; if comparison stops early the rest of the trees won't be converted. One way to proceed in a strict language is to work with a (pure) state involving - the current focus of "list" 1 - the current focus of "list" 2 - the rest of "list" 1 (as a list of parts) - the rest of "list" 2 (as a list of parts). I thought I had demonstrated this when one last check showed a serious bug in my code. In any case, this relies on lists to implement the stacks we use for "the rest of the tree". Your "unwrap" approach is much easier to get right.
participants (2)
-
R J -
Richard O'Keefe