[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

[Matthias Görgens]

Dear Hector,

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.

Matthias.