[Haskell-cafe] efficient and/or lazy partitions of a multiset

[Greg Meredith]

HC-er's,

Find below some simple-minded code from a naive Haskeller for generating all
partitions of a multiset about which i have two questions.

mSplit :: [a] -> [([a], [a])]
mSplit [x]     = [([x],[])]
mSplit (x:xs) = (zip (map (x:) lxs) rxs)
                      ++ (zip lxs (map (x:) rxs))
                      where (lxs,rxs) = unzip (mSplit xs)

   1. Is there a clever way to reduce the horrid complexity of the naive
   approach?
   2. How lazy is this code? Is there a lazier way?

i ask this in the context of checking statements of the form \phi * \psi |=
e_1 * ... * e_n where

   - [| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi |],
   b_2 \in [| \psi |] }
   - === is some congruence generated from a set of relations

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't the partition they meant).

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070521/e8293496/attachment.htm