HC-er&#39;s,<br><br>Find below some simple-minded code from a naive Haskeller for generating all partitions of a multiset about which i have two questions.<br><br>mSplit :: [a] -&gt; [([a], [a])]<br>mSplit [x]&nbsp;&nbsp;&nbsp;&nbsp; = [([x],[])]
<br>mSplit (x:xs) = (zip (map (x:) lxs) rxs)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ++ (zip lxs (map (x:) rxs))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; where (lxs,rxs) = unzip (mSplit xs)<br><ol><li>Is there a clever way to reduce the horrid complexity of the naive approach?
</li><li>How lazy is this code? Is there a lazier way?</li></ol>i ask this in the context of checking statements of the form \phi * \psi |= e_1 * ... * e_n where<br><ul><li>[| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi |], b_2 \in [| \psi |] }
</li><li>=== is some congruence generated from a set of relations<br></li></ul>A nice implementation for checking such statements will iterate through the partitions, generating them as needed, checking subconditions and stopping at the first one that works (possibly saving remainder for a rainy day when the client of the check decides that wasn&#39;t the partition they meant).
<br><br>Best wishes,<br><br>--greg<br><br>-- <br>L.G. Meredith<br>Managing Partner<br>Biosimilarity LLC<br>505 N 72nd St<br>Seattle, WA 98103<br><br>+1 206.650.3740<br><br><a href="http://biosimilarity.blogspot.com">http://biosimilarity.blogspot.com
</a>