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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
