2

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.

zaig
  • 391
  • 1
  • 11

1 Answers1

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.

behzad.nouri
  • 74,723
  • 18
  • 126
  • 124
  • I don't really understand how this works? Can you explain me? – zaig Apr 20 '16 at 23:38
  • @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 – behzad.nouri Apr 21 '16 at 10:06
  • 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? – zaig Apr 21 '16 at 13:44
  • @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 – behzad.nouri Apr 21 '16 at 13:47
  • 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. – zaig Apr 21 '16 at 17:46
  • @zaig [this question](http://stackoverflow.com/questions/6172004/writing-foldl-using-foldr) has a step by step example of a similar usage – behzad.nouri Apr 21 '16 at 17:49