[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 
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))

More information about the Haskell-Cafe mailing list