[Haskell-beginners] [Haskell-cafe] select :: [(Float, a)] -> a -- Weighted stochastic selection - help?

[Daniel Fischer]

Am Freitag, 5. September 2008 18:54 schrieb Tim Millea:
> I am already using the following function
>
>   pickOne xs g = (xs !! r, g')
>      where (r, g') = Random.randomR (0, length xs - 1) g
>
> but I need to weight the items in the list, e.g. [(0.1, 'a') , (0.9, 'b')]
> for stochastic selection in a purely functional way, i.e. no monads. Any
> ideas welcome.
>
> Tim.
>

You could pair each item with the cumulative probability of all items up to 
and including it, that would be [(0.1,'a'),(1.0,'b')] in the above example, 
then

pickOne prs g = (snd p,g')
      where
	(r,g') = Random.randomR (0,1.0)
	(smll,lrge) = span ((< r) . fst) prs
	p = case lrge of
	      (x:_) -> x
	      [] -> last smll