Matthias Görgens <matthias.goerg...@googlemail.com> writes:
> 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.
Well, you could implement a function 'split' as
split (x:xs) = (evens (x:xs), evens xs)
where evens (y:_:ys) = y:evens ys
This would divide your supply of random numbers in two - this is lazy,
but forcing any of the sublists would force the spine of the original
list, so not optimal.
So the obvious followup is why not pass a randomGen around instead,
which has a split operation already defined, and which causes no
laziness headaches?
> What I wondered was, if one could hid the random plumbing in some data
> structure, like the state monad, but less linear.
This problem cries for a State monad solution - but you don't need to
do it yourself, there's already a Random monad defined for you.
-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
