# [Haskell-cafe] Re: Permutation with k levels

Daniel McAllansmith dm.maillists at gmail.com
Tue Nov 7 14:23:51 EST 2006

On Wednesday 08 November 2006 05:41, DavidA wrote:
> To get the result you want, take the list of (letter, probability) pairs,
> and generate the Cartesian product of k copies of itself.
>
> cartProd 0 xs = [[]]
> cartProd k xs = [x:ys | x <- xs, ys <- cartProd (k-1) xs]
>
> The result is all sequences of k (letter,probability) pairs, allowing
> repetitions.
>
> Then you just need to unzip and multiply:
>
> (\lps -> let (ls,ps) = unzip lps in (concat ls, product ps))
>

It does the basically the same thing but, you might also want to check out the
Probabilistic Functional Programming library by Martin Erwig at
http://web.engr.oregonstate.edu/~erwig/pfp/
It's got all sorts of other probability goodies in it.

By importing the Probability module you can define your distribution and a
permute as so

probDist = mkD [("A", 0.8), ("B", 0.2)]

permute 0 d = mkD []
permute 1 d = d
permute k d = mapD (uncurry (++)) (prod d (permute (k - 1) d))