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.