[Haskell-cafe] Re: efficient and/or lazy partitions of a multiset
Greg Meredith
lgreg.meredith at biosimilarity.com
Tue May 22 13:59:24 EDT 2007
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 <lgreg.meredith at biosimilarity.com> 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],[])]
> 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
--
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/20070522/148dbf3f/attachment.htm
More information about the Haskell-Cafe
mailing list