Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: simplifying algebraic expression (Alexander.Vladislav.Popov ) 2. Re: randomize the order of a list (Heinrich Apfelmus) ---------------------------------------------------------------------- Message: 1 Date: Wed, 1 Sep 2010 17:50:03 +0600 From: "Alexander.Vladislav.Popov " <alexander.vladislav.po...@gmail.com> Subject: Re: [Haskell-beginners] simplifying algebraic expression To: beginners@haskell.org Message-ID: <aanlktin6spnjlihfz_zyhgzwbxt+yq+lhcu5j3o=t...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" Thank you, Jürgen and Jean. I'll try. There was no a particular reason to write it through fixed-point combinator only my deep despair, because I could not find some workaround. 2010/9/1 Jürgen Doser jurgen.do...@gmail.com > > Btw., is there a particular reason why you did not try to write the > recursion explicitely, but used the function s? > > Jürgen > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20100901/15e28cbc/attachment-0001.html ------------------------------ Message: 2 Date: Wed, 01 Sep 2010 13:58:11 +0200 From: Heinrich Apfelmus <apfel...@quantentunnel.de> Subject: [Haskell-beginners] Re: randomize the order of a list To: beginners@haskell.org Message-ID: <i5lf4j$hb...@dough.gmane.org> Content-Type: text/plain; charset=UTF-8; format=flowed Gabriel Scherer wrote: > Heinrich Apfelmus wrote: >> For another approach, see also >> >> http://apfelmus.nfshost.com/articles/random-permutations.html > > Thanks for the link apfelmus, it's fairly interesting. The key to > making it work is the weighting of lists during merging based on their > lengths. I wonder if other sort algorithm can be adapted in such a > way, while preserving uniformity. Quicksort for example : is it enough > to choose the result position of the pivot randomly, and then placing > elements on either side with a probability of 1/2 ? Interesting question! Adapting quick sort is not that easy, though. First, you can skip choosing the pivot position because it is already entailed by the choices of elements left and right to it. Second, probability 1/2 won't work, it doesn't give a uniform distribution. In order to get that, the remaining input xs has to be partitioned into two lists xs = (ls,rs) such that probability that length ys == k is 1/(n `over` k) where n `over` k = n! / (k! * (n-k)!) is the binomial coefficient. After all, calling "quickrandom" recursively on each of the two lists will give two permutations with probability 1/k! and 1/(n-k)! and the probability for a compound permutation is 1/(n `over` k) * 1/k! * 1/(n-k)! = 1/n! as desired. In contrast, distributing elements with probability 1/2 would give probability that length ys == k is (n `over` k) * 2^(-n) which would skew the distribution heavily towards permutations where the pivot element is in the middle. However, it is possible to divide the list properly, though I haven't worked out the exact numbers. The method would be divide (x:xs) = do (ls,rs) <- divide xs random <- uniform (0, 1) :: Random Double if random <= p (length xs) (length ls) then return (x:ls, rs) else return (ls, x:rs) where the probability p of putting the element x into the left part has to be chosen such that 1/(n `over` k) = 1/(n-1 `over` k-1) * p (n-1) (k-1) + 1/(n-1 `over` k ) * (1 - p (n-1) k) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 27, Issue 2 ****************************************