Re: Stream of random comments continues
Dave Tweed wrote: > On Fri, 4 Dec 1998, Keith Wansbrough wrote: > > > Surely it would be better to split the one stream into several infinite ones: > > - - - > > Closer inspection reveals this is not a necessarily a the best idea > (particularly if you're going to repeat the trick several times on various > subsets) because you can get nasty correlations between the various > streams even from quite a good random number generator. There was a paper > published in the JFP about a better way of splitting streams which I think > appeared sometime between January 1996--October 1996. This reminds me slightly of the Functional Pearl: On generating unique names (Augustsson, Rittri, Synek), which appeared in JFP in January 1994. [vol 4(1)] We showed how to simulate an infinite binary tree of unique names, by having a hidden call to gensym(). Instead of gensym(), I suppose one could hide a call to a random number generator. But I don't know if nasty correlations can appear in this case. -- Mikael Rittri
Re: Stream of random comments continues
> There was a paper > published in the JFP about a better way of splitting streams which I think > appeared sometime between January 1996--October 1996. Are you perhaps referring to the paper by me, Mikael Rittri, and Dan Synek called "On generating unique names" (Jan 94). It has a low level trick to split streams in a good way that could be applied here. -- Lennart
Re: Stream of random comments continues
On Fri, 4 Dec 1998, Lennart Augustsson wrote: > > > There was a paper > > published in the JFP about a better way of splitting streams which I think > > appeared sometime between January 1996--October 1996. > Are you perhaps referring to the paper by me, Mikael Rittri, and Dan Synek > called "On generating unique names" (Jan 94). It has a low level trick to > split streams in a good way that could be applied here. Looking on the JFP web-page I _think_ I was very off and it was in fact a 1992 paper that I skimmed through one day (whilst leafing through the entire set of back issues of the JFP trying to orient myself, which `explains' why I got confused enough to think it was a contemporary paper). F. Warren Burton and Rex L. Page. Distributed random number generation. Journal of Functional Programming, 2(2):203-212, April 1992. IIRC, it attempts to deal precisely with the point that you want to be able to pass infinite lists of (pseudo) random numbers (derived from a central source) into lazy functions without getting (a) bad space leaks or (b) nasty correlations between the sequences. Caveat: I've only looked at the title; I may be misremembering again. Anyway, hope this is of some assistance. ___cheers,_dave_ email: [EMAIL PROTECTED] "I'm guilty of a lot of things but I've www.cs.bris.ac.uk/~tweed/pi.htm never violated the law of conservation work tel: (0117) 954-5253 of energy!" -- Bart Kosko, Nanotime
Re: Stream of random comments continues
Keith Wansbrough wrote: > Surely it would be better to split the one stream into several infinite ones: > > splitStream :: [a] -> ([a],[a]) > > splitStream xs = unzip (spl xs) > where spl (x:y:xs) = (x,y):(spl xs) > > Then you don't have to know how many you are going to use from each stream. If I'm not mistaken, this definition has the danger of a space leak: Suppose you initially use a lot of elements of the first list/stream only and then elements from the second, e.g.: foo :: Int -> IO () foo n = do print . head . drop n $ xs print . head $ ys where (xs,ys) = splitStream (repeat 1) This gives you space usage linear in n... :-( Cheers, Sven -- Sven PanneTel.: +49/89/2178-2235 LMU, Institut fuer Informatik FAX : +49/89/2178-2211 LFE Programmier- und Modellierungssprachen Oettingenstr. 67 mailto:[EMAIL PROTECTED]D-80538 Muenchen http://www.pms.informatik.uni-muenchen.de/mitarbeiter/panne
Re: Stream of random comments continues
On Fri, 4 Dec 1998, Keith Wansbrough wrote: > Surely it would be better to split the one stream into several infinite ones: > > splitStream :: [a] -> ([a],[a]) > > splitStream xs = unzip (spl xs) > where spl (x:y:xs) = (x,y):(spl xs) > > Then you don't have to know how many you are going to use from each stream. Closer inspection reveals this is not a necessarily a the best idea (particularly if you're going to repeat the trick several times on various subsets) because you can get nasty correlations between the various streams even from quite a good random number generator. There was a paper published in the JFP about a better way of splitting streams which I think appeared sometime between January 1996--October 1996. (Sorry I can't be more specific -- I didn't really keep any notes on all the frantic background reading I was doing :-) ) ___cheers,_dave_ email: [EMAIL PROTECTED] "I'm guilty of a lot of things but I've www.cs.bris.ac.uk/~tweed/pi.htm never violated the law of conservation work tel: (0117) 954-5253 of energy!" -- Bart Kosko, Nanotime
Re: Stream of random comments continues
| The discussion of random numbers in Haskell should perhaps | move elsewhere as it is quite restricted, but it shows one | problem with the functional approach to *practical* programming: | in *my opinion* our fascination by the Monadic Approach to | Universe and Everything, and the possibility to program in an | imperative way has a negative side effect. My friends physicists | asked me once after being told that imperative constructs are | possible in Haskell: "so, what's the point in using this language? | Fortran code is simpler than "do" in Haskell..." Huuuh. Did you tell your friend that imperative constructs are the `only' thing possible? Surely not. So I don't quite understand this statement (on a scientific basis). | I would change the | Lennart example by using splitAt instead of take, and continuing the | next | instance with the remaining part of the master sequence. But now you are basically programming within a state monad, the infinite sequence of pseudo-random ints being the state. At its simplest: let (is1, ms1) = splitAt m ms (is2, ms2) = splitAt n ms1 vs do is <- ints m ds <- doubles m However, having re-thought the whole thing I guess it's a good idea to use an infinite stream as the state instead of the seed. As you remarked in a previous mail this would make it simple to provide a different generator. Nonetheless, I still believe that using a monad (note necessarily IO) is the RIGHT approach, because the state is passed implictly and it allows to hide the technical details (how many Ints do you need for an Integer in the range (l,r)?) from the user. Cheers, Ralf
Re: Stream of random comments continues
> Lennart advocates the use of streams : > > > let mis = take n (random ss1) > > is = take n (toInt (random ss2)) > > ds = take n (toDouble (random ss3)) > > in ... > > and I agree entirely with him, although the coding details might > be different. Streams are nice and safe. And methodologically > sane. Surely it would be better to split the one stream into several infinite ones: splitStream :: [a] -> ([a],[a]) splitStream xs = unzip (spl xs) where spl (x:y:xs) = (x,y):(spl xs) Then you don't have to know how many you are going to use from each stream. --KW 8-) -- : Keith Wansbrough, MSc, BSc(Hons) (Auckland) : : PhD Student, Computer Laboratory, University of Cambridge, England. : : (and recently of the University of Glasgow, Scotland. [><] ) : : Native of Antipodean Auckland, New Zealand: 174d47' E, 36d55' S.: : http://www.cl.cam.ac.uk/users/kw217/ mailto:[EMAIL PROTECTED] : :-:
Stream of random comments continues
The discussion of random numbers in Haskell should perhaps move elsewhere as it is quite restricted, but it shows one problem with the functional approach to *practical* programming: in *my opinion* our fascination by the Monadic Approach to Universe and Everything, and the possibility to program in an imperative way has a negative side effect. My friends physicists asked me once after being told that imperative constructs are possible in Haskell: "so, what's the point in using this language? Fortran code is simpler than "do" in Haskell..." == Lennart advocates the use of streams : > let mis = take n (random ss1) > is = take n (toInt (random ss2)) > ds = take n (toDouble (random ss3)) > in ... and I agree entirely with him, although the coding details might be different. Streams are nice and safe. And methodologically sane. Ralf Hinze : > My problem with your solution is that you must supply a seed for every > call (perhaps you don't know how many do you require) and that you may > end up with pseudo-random numbers which are not random at all. Because > you choose the seeds badly. That's why I thread the (current) seed > through all those value generators. Of course, instead of threadening > a seed one could thread an infinite list of Ints. Actually I remind you that *practically all classical* generators are based on integer congruences, and if the parametrization (A,C,M) of gen = \X -> (A*X + C) `mod` M is chosen correctly, the quality of the generator is ensured independently of the seed. The problem with the Lennart example is that you might get two, three, etc. generators which are clones, eventually shifted by some number of items. But the main idea is very simple. The only thing to do rnd = (iterate gen seed) and do whatever you wish with it, for example map (/ M) on order to have numbers in (0 .. 1), pick them by dozens in order to get Gaussians, etc. I would change the Lennart example by using splitAt instead of take, and continuing the next instance with the remaining part of the master sequence. But, if I really wished to have different random streams, I would change the parameteres in generating this master sequence, and this is all. Such Good Numbers could be provided in the library. Sometimes other schemes are used, for example one generator pumps the pseudo-randoms into a (short) array, and a second one picks up one of them, which kills the short and medium range correlations, even if the basic parametrization is not perfect... This would need monadic arrays or other similar contraptions. There is another issue which should be raised one day: there is no reason to discuss random numbers if we won't use them seriously. Well, in order to apply functional methods to simulations, Monte-Carlo integrations, optimizations, etc. we need to put a good deal of code into the functional framework. Best regards Jerzy Karczmarczuk Caen, France.
Re: Random comments
| First: I had forgotten that what the Random module actually | gives you is [Integer], not [Int], but the same reasoning | applies. What's the range for the Integers? I guess Int is better suited. | Well, you naturally need functions that convert a list of | [Integer] to what you need. I'm not at all against such functions, | and I think they should be included, e.g. | toDouble :: [Integer] -> [Double] | toInt :: [Integer] -> [Int] | etc. So I might write | let mis = take n (random ss1) | is = take n (toInt (random ss2)) | ds = take n (toDouble (random ss3)) | in ... | where ss1, ss2, ss3 are the seeds. You can get them from an initial | call to randomIO or use some known values if you need to repeat the sequence. My problem with your solution is that you must supply a seed for every call (perhaps you don't know how many do you require) and that you may end up with pseudo-random numbers which are not random at all. Because you choose the seeds badly. That's why I thread the (current) seed through all those value generators. Of course, instead of threadening a seed one could thread an infinite list of Ints. | I think using monads, and specially a powerful one like IO, everywhere is | a mistake. I can't see the need for most uses of random numbers. I agree that the IO monad is not necessary. However, a monad for random values seems perfectly reasonable. Ralf
Re: Random comments
> I guess you would end up with nearly the same code (unless I overlook > an obvious alternative in which case I would love to see the simple and > straightforward solution ;-). Let's be concrete: say you need n > Integers within range (l, r), m Ints and p Doubles. Using a monad-based > approach one writes > > ... > mis <- accumulate [ randomInteger (l, r) | i <- [1 .. n] ] > is <- accumulate [ randomInt | i <- [1 .. m] ] > ds <- accumulate [ randomDouble | i <- [1 .. p] ] > return (mis, is, ds) > > What's your solution based on an [Int] list of random numbers? First: I had forgotten that what the Random module actually gives you is [Integer], not [Int], but the same reasoning applies. Well, you naturally need functions that convert a list of [Integer] to what you need. I'm not at all against such functions, and I think they should be included, e.g. toDouble :: [Integer] -> [Double] toInt :: [Integer] -> [Int] etc. So I might write let mis = take n (random ss1) is = take n (toInt (random ss2)) ds = take n (toDouble (random ss3)) in ... where ss1, ss2, ss3 are the seeds. You can get them from an initial call to randomIO or use some known values if you need to repeat the sequence. I think using monads, and specially a powerful one like IO, everywhere is a mistake. I can't see the need for most uses of random numbers. -- Lennart
Re: Random comments
| > The stream-based approach has its problems if one requires random | > values of different types. If this is vital one automatically starts to | > use functions of type Seed -> (value, Seed). | I don't understand at all. Why would random values of different types | require that signature? Why can you use an infinite list of these | other values? Why can't you take the [Int] list of random numbers | and transform it into whatever you want? That's what I do. I guess you would end up with nearly the same code (unless I overlook an obvious alternative in which case I would love to see the simple and straightforward solution ;-). Let's be concrete: say you need n Integers within range (l, r), m Ints and p Doubles. Using a monad-based approach one writes ... mis <- accumulate [ randomInteger (l, r) | i <- [1 .. n] ] is <- accumulate [ randomInt | i <- [1 .. m] ] ds <- accumulate [ randomDouble | i <- [1 .. p] ] return (mis, is, ds) What's your solution based on an [Int] list of random numbers? Ralf
Re: Random comments
> The stream-based approach has its problems if one requires random > values of different types. If this is vital one automatically starts to > use functions of type Seed -> (value, Seed). I don't understand at all. Why would random values of different types require that signature? Why can you use an infinite list of these other values? Why can't you take the [Int] list of random numbers and transform it into whatever you want? That's what I do. -- Lennart
Re: Random comments
| Could somebody - perhaps outside this list - provide a serious | example showing the *necessity* for RandomIO() - the Monadic, | "side-effect" version? In a pure functional language? Well, I'm not outside this list ;-). Honestly, there is no necessity for using the IO monad, it is just a matter of convenience, see below. | I use random numbers from time to time. | I have always used sequences, lazily generated. No problem | with the seed injection/restoring, and - what is *much* more | important: | | No problem with having *several* generators within the program. The stream-based approach has its problems if one requires random values of different types. If this is vital one automatically starts to use functions of type Seed -> (value, Seed). Sooner or later you recognize that you are programming in a state monad. Now, one could define a specialized monad or misuse (if you like) IO. | In a serious application this is useful for generating random | vectors, or for using one generator to decorrelate another. | I agree with the comments of David Tweed. Please give the | People the Power to plug-in several generators, instead of | eine Sprache, eine Kirche, ein ZufallsZahlGeneratorIO()... I don't see why this should be a problem. The dilegent user is always free to plug in new generators, simply by supplying modules which have the same signature as `Random'. | You might answer that a primitive is more efficient. But in | typical simulations or other applications which use random | numbers (Monte-Carlo, etc.) this is usually not as important. It's probably both more efficient and more convenient ;-). Cheers, Ralf
Re: Random comments
| I think using monads, and specially a powerful one like IO, everywhere is | a mistake. I can't see the need for most uses of random numbers. | | -- Lennart Besides that, isn't the name "randomIO" a bit unfortunate? It sounds like it contrasts with "sequentialIO". --Joe Joseph H. Fasel, Ph.D. email: [EMAIL PROTECTED] Technology Modeling and Analysisphone: +1 505 667 7158 University of Californiafax:+1 505 667 2960 Los Alamos National Laboratory postal: TSA-7 MS F609 Los Alamos, NM 87545
Random comments
Could somebody - perhaps outside this list - provide a serious example showing the *necessity* for RandomIO() - the Monadic, "side-effect" version? In a pure functional language? I use random numbers from time to time. I have always used sequences, lazily generated. No problem with the seed injection/restoring, and - what is *much* more important: No problem with having *several* generators within the program. In a serious application this is useful for generating random vectors, or for using one generator to decorrelate another. I agree with the comments of David Tweed. Please give the People the Power to plug-in several generators, instead of eine Sprache, eine Kirche, ein ZufallsZahlGeneratorIO()... You might answer that a primitive is more efficient. But in typical simulations or other applications which use random numbers (Monte-Carlo, etc.) this is usually not as important. Best regards Jerzy Karczmarczuk Caen, France.
