[Haskell-cafe] Implementing Las Vegas algorithms in Haskell
matthias.goergens at googlemail.com
Tue Jul 7 03:46:30 EDT 2009
Yes, I thought of a similar scheme. Say we want to implemented
randomized quicksort. Passing a list of random numbers would destroy
laziness and linearise the algorithm --- because the right recursion
branch would need to know at least how many random numbers where
consumed by the left branch.
So for the example of quicksort I thought of passing an infinite
binary tree of random numbers.
> data RandomTree v = Node (RandomTree v) v (RandomTree v)
> splitOnMedian :: Ord a => SomeRandomType -> [a] -> ([a],a,[a])
> quicksort :: RandomTree (SomeRandomType) -> [a] -> [a]
> quicksort _  = 
> quicksort _ [a] = [a]
> quicksort (Node left here right) s
> = let (l,median,r) = splitOnMedian here s
> in quicksort left l ++ median ++ quicksort right r
Of course one would need a special data structure for each recursion
scheme with this approach. For a number of algorithms something like
the rose trees of Data.Tree should work, though.
What I wondered was, if one could hid the random plumbing in some data
structure, like the state monad, but less linear.
More information about the Haskell-Cafe