Haskell generate random numbers with a propriety without explicit recursion

Question

Here I have a function to generate a stream of random numbers between 0 and 999.

randomHelp :: RandomGen g => g -> [Int]
randomHelp g = zipWith (mod) (map fst $ iterate (next . snd) $ next $ snd $ split g) $ repeat 1000

I would like to select all numbers from the stream defined above and each elem(i) and elem(i + 1) must respect a propriety. For example their gcd have to be one. All I can think is a fold function with because I can start with and accumulator which contains the number 1 (let's assume 1 will be the first element I want to show) then I check the propriety in fold's function and if it is respected i add the element to the accumulator, but the problem is the program blocks because of stackoverflow I think.

Here is the function:

randomFunc :: RandomGen g => g -> [Int]
randomFunc g = foldl (\acc x -> if (gcd x (last acc) == 1) then acc ++ [x] else acc) [1] (randomHelp g)

Note: I don't want to use explicit recursion.

behzad.nouri · Accepted Answer · 2016-04-20 21:22:26Z

2

A right fold would probably fit better, something like:

import System.Random (RandomGen, randomRs, mkStdGen)

randomFunc :: RandomGen g => g -> [Int]
randomFunc g = foldr go (const []) (randomRs (1, 20) g) 1
    where go x f lst = if gcd x lst == 1 then x: f x else f lst

then

\> take 20 . randomFunc $ mkStdGen 1
[16,7,6,19,8,15,16,1,9,2,15,17,14,3,11,17,15,8,1,5]

Doing so you may build the list using : instead of ++ which may cause quadratic performance cost, and you may bypass the call to last.

edited Apr 20, 2016 at 21:22

answered Apr 20, 2016 at 21:17

behzad.nouri

78.5k18 gold badges130 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

zaig Over a year ago

I don't really understand how this works? Can you explain me?

behzad.nouri Over a year ago

@zaig this is an application of foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b where b itself is a function, like c -> d, so the signature would be (a -> (c -> d) -> c -> d) -> (c -> d) -> t a -> c -> d. if you follow the signature should make sense how it works

zaig Over a year ago

I still don't understand who is the function f? By the order I would say it will be randomRs when go will be called, but randomRs takes a generator and lst and x are not generators. I am still a little confused. What am I missing?

behzad.nouri Over a year ago

@zaig (randomRs (1, 20) g) is an infinite list, and it has already passed in the generator g. you can replace (randomRs (1, 20) g) with an arbitrary list, say [2, 3, 6, 8, 5], to see how this works

zaig Over a year ago

If you can explain step by step the code with the list [2, 3, 6] I'd be grateful. I don't get who f is when the go function is called. And also which are the parameters go is taking.

|

Collectives™ on Stack Overflow

Haskell generate random numbers with a propriety without explicit recursion

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related