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
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)])) [([],[])]
Henning,
In your reply, you made a number of interesting suggestions. You could also
have written
mSplitC :: [a] -> [([a], [a])] -- C for comprehension
mSplitC [] = [([],[])]
mSplitC [x] = [([x],[])]
mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
which Matthias Radestock suggested to me.
Note that if you only supply the empty multiset case, then you end up with
duplicates.
mSplitCD :: [a] -> [([a], [a])]
mSplitCD [] = [([],[])]
mSplitCD (x:xs) = concat [[(x:l,r),(l,x:r)] | (l,r) <- mSplitCD xs]
*Zoup> mSplitCD [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2]),([1,2],[3]),([2],[1,3]),([1],[2,3]),([],[1,2,3])]
*Zoup> mSplitC [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2])]
*Zoup>
Is there anyway to peer under the hood to see the code being generated? i
notice, for example, that the original concat/zip-based implementation
occasionally comes in quite a bit faster that the comprehension based
example.
Best wishes,
--greg
On 5/21/07, 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
-- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com
On Tue, 22 May 2007, Greg Meredith wrote:
mSplitC :: [a] -> [([a], [a])] -- C for comprehension
mSplitC [] = [([],[])] mSplitC [x] = [([x],[])] mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
which Matthias Radestock suggested to me.
Note that if you only supply the empty multiset case, then you end up with duplicates.
That is ([1,2],[3]) and ([3],[1,2]) are considered the same? But you need always pairs not only [1,2] and [3] ?
Henning,
i need the bi-partitions of a multiset. That is, all the ways you can split
a multiset, M, into two multisets, M1 and M2, such that M = M1
`multiset-union` M2.
Best wishes,
--greg
On 5/23/07, Henning Thielemann
On Tue, 22 May 2007, Greg Meredith wrote:
mSplitC :: [a] -> [([a], [a])] -- C for comprehension
mSplitC [] = [([],[])] mSplitC [x] = [([x],[])] mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
which Matthias Radestock suggested to me.
Note that if you only supply the empty multiset case, then you end up with duplicates.
That is ([1,2],[3]) and ([3],[1,2]) are considered the same? But you need always pairs not only [1,2] and [3] ?
-- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com
participants (2)
-
Greg Meredith -
Henning Thielemann