Re: [Haskell-cafe] efficient and/or lazy partitions of a multiset
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)])) [([],[])] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] efficient and/or lazy partitions of a multiset
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
