[Haskell-cafe] efficient and/or lazy partitions of a multiset
lemming at henning-thielemann.de
Tue May 22 07:53:42 EDT 2007
On Mon, 21 May 2007, Greg Meredith wrote:
> 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],)]
What about  ?
> 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
> 2. How lazy is this code? Is there a lazier way?
The code looks good. Maybe instead of doing
zip ... ++ zip ...
you should interleave the generated lists. This will probably reduce the
need of constructing elements if only a prefix of (mSplit xs) is
mSplitLazy  = [(,)]
mSplitLazy (x:xs) =
let (lxs,rxs) = unzip (mSplitLazy xs)
lys = zip (map (x:) lxs) rxs
rys = zip lxs (map (x:) rxs)
in concat (zipWith (\a b -> [a,b]) lys rys)
If you are also after elegance - how about the List monad?
mSplitMonad  = [(,)]
mSplitMonad (x:xs) =
do (lxs,rxs) <- mSplitMonad xs
Or more condensed:
(\x -> concatMap (\(lxs,rxs) -> [(x:lxs,rxs), (lxs,x:rxs)]))
More information about the Haskell-Cafe