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

[Henning Thielemann]

On Mon, 21 May 2007, Greg Meredith wrote:

> 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],[])]

What about [] ?

See
  http://www.haskell.org/haskellwiki/Base_cases_and_identities

> 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?

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
requested.

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
      [(x:lxs,rxs), (lxs,x:rxs)]

Or more condensed:

mSplitFoldr =
   foldr
     (\x -> concatMap (\(lxs,rxs) -> [(x:lxs,rxs), (lxs,x:rxs)]))
     [([],[])]