<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
</style>
</head>
<body class='hmmessage'>
<font style="" face="Courier New">Could someone provide an elegant solution to Bird problem 4.2.13?</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Here are the problem and my inelegant solution:</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Problem</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">-------</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">concatenation as a primitive.</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">For example,</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">data (CatList a)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp; CatNil</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |&nbsp; Wrap a</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |&nbsp; Cat (CatList a) (CatList a)</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">x ++ y.</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs"</font><font style="" face="Courier New"> should be regarded as equal.</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Define appropriate instances of "Eq" and "Ord" for "CatList".</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Inelegant Solution</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">------------------</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">The following solution works:</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">instance (Eq a) =&gt; Eq (CatList a) where</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ==&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp;&nbsp;&nbsp; True</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ==&nbsp; Wrap&nbsp;&nbsp; z&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp;&nbsp;&nbsp; False</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ==&nbsp; Cat&nbsp;&nbsp;&nbsp; z w&nbsp;&nbsp; =&nbsp; ( z == CatNil&nbsp; &amp;&amp; w == CatNil )</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Wrap&nbsp;&nbsp; x&nbsp;&nbsp;&nbsp; ==&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp;&nbsp;&nbsp; False</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Wrap&nbsp;&nbsp; x&nbsp;&nbsp;&nbsp; ==&nbsp; Wrap&nbsp;&nbsp; z&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp;&nbsp;&nbsp; x == z</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Wrap&nbsp;&nbsp; x&nbsp;&nbsp;&nbsp; ==&nbsp; Cat&nbsp;&nbsp;&nbsp; z w&nbsp;&nbsp; =&nbsp; ( Wrap x == z&nbsp; &amp;&amp; w == CatNil ) ||<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ( Wrap x == w&nbsp; &amp;&amp; z == CatNil )</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Cat&nbsp;&nbsp;&nbsp; x y&nbsp; ==&nbsp; CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp;&nbsp;&nbsp; x == CatNil&nbsp; &amp;&amp; y == CatNil</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Cat&nbsp;&nbsp;&nbsp; x y&nbsp; ==&nbsp; Wrap&nbsp;&nbsp; z&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp; ( x == Wrap z&nbsp; &amp;&amp; y == CatNil ) ||<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ( x == CatNil&nbsp; &amp;&amp; y == Wrap z )</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; Cat&nbsp;&nbsp;&nbsp; x y&nbsp; ==&nbsp; Cat&nbsp;&nbsp;&nbsp; z w&nbsp;&nbsp; =&nbsp; unwrap (Cat x y) == unwrap (Cat z w)</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">unwrap&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; :: CatList a -&gt; [a]</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">unwrap CatNil&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp; []</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">unwrap (Wrap x)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; =&nbsp; [x]</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">unwrap (Cat x y)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =&nbsp; unwrap x ++ unwrap y</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">instance (Eq a, Ord a) =&gt; Ord (CatList a) where</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">&nbsp;&nbsp;&nbsp; x &lt; y = unwrap x &lt; unwrap y</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">This solution correctly recognizes the equality of the following, including nested lists</font><font style="" face="Courier New">(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]):</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Wrap 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; == Cat (Wrap 1) CatNil</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3))</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Wrap (Wrap 1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; == Wrap (Cat (Wrap 1) CatNil)</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">Although this solution works, it's a hack, because unwrap converts CatLists to lists</font><font style="" face="Courier New">.&nbsp; The question clearly seeks a pure solution that does not</font><font style="" face="Courier New"> rely on Haskell's built-in lists.<br></font><font style="" face="Courier New"><br></font><font style="" face="Courier New">What's the pure solution that uses cases and recursion on</font><font style="" face="Courier New"><br></font><font style="" face="Courier New">CatList, not Haskell's built-in lists, to capture the equality of nested CatLists?</font><font style="" face="Courier New"><br></font><font style="" face="Courier New"><br></font><br /><hr />Windows Live™: Life without walls. <a href='http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009' target='_new'>Check it out.</a></body>
</html>