15 May 20:03 2013

## recursion patterns?

```Well, my question does not meet the standards for a question at stackoverflow:

This example is from LYAH:

import System.Random

finiteRandoms :: (RandomGen g, Random a, Num n) => n -> g -> ([a], g)
finiteRandoms 0 gen = ([], gen)
finiteRandoms n gen =
let (value, newGen) = random gen
(restOfList, finalGen) = finiteRandoms (n-1) newGen
in  (value:restOfList, finalGen)

Looking at that function, I find it impossible to understand how that recursion works.  I have to pull out a
pencil and paper to figure it out.  If I was given the task of writing that function, I would write it like this:

import System.Random

finiteRands :: (RandomGen g, Random a) => Int -> g -> [a]
finiteRands n gen = finiteRands' n gen []

finiteRands' :: (RandomGen g, Random a) => Int -> g -> [a] -> [a]
finiteRands' 0 _ acc = acc
finiteRands' n gen acc =
let (rand_num, new_gen) = random gen
in finiteRands' (n-1) new_gen (rand_num:acc)

To me, it makes the function(s) simplistic to understand.  Is the first solution a known 'design pattern' in
```

15 May 20:17 2013

### Re: recursion patterns?

```
On Wed, 15 May 2013, 7stud wrote:

> Well, my question does not meet the standards for a question at stackoverflow:
>
> (I am a haskell beginner)

list.

> Is one solution more efficient than the other?  I believe my solution is
> tail recursive, but it's my understanding that compilers can now
> optimize just about anything into tail recursion.

The first solution works for infinite lists and the second one does not.
It's really like foldr vs. foldl.
```
15 May 21:16 2013

### Re: recursion patterns?

```>> Is one solution more efficient than the other?  I believe my solution is
>> tail recursive, but it's my understanding that compilers can now
>> optimize just about anything into tail recursion.

>The first solution works for infinite lists and the second one does not.

I don't see how that's possible.  Both traversals seem to be limited by n, and therefore they do not have to
touch the end of the list.  In any case, it would seem to me that the *first* solution would be the one that
wouldn't work on an infinite list.  Can you explain?

>It's really like foldr vs. foldl.

Hmm...I never thought of foldr and foldl in those terms.  Thanks.

I'l be sure to post any other questions I have on the beginner list.
```
21 May 12:09 2013

### Re: recursion patterns?

2013/5/15 7stud <7stud <at> excite.com>

> >The first solution works for infinite lists and the second one does not.

> I don't see how that's possible.  Both traversals seem to be limited by n, and therefore they do not have to touch the end of the list.  In any case, it would seem to me that the *first* solution would be the one that wouldn't work on an infinite list.  Can you explain?

The first version returns a tuple with a list and a generator.
If you want the first value, you will evaluate the list constructor ":", then evaluate "value", then "random gen" and you have the value.
For each new value you need, you will evaluate resteOfList, so will call finiteRandoms recursively just once.

To better see it, you can modify it by removing the n : (warning, this function doesn't make sense, I'll explain why afterwards)

finiteRandoms' :: (RandomGen g, Random a) => g -> ([a], g)
finiteRandoms' gen =
let (value, newGen) = random gen
(restOfList, finalGen) = finiteRandoms' newGen
in  (value:restOfList, finalGen)

and then you could try it like this :

l' :: [Int]
(l',f') = finiteRandoms' (mkStdGen 1)

in ghci, if you type l', it will run in an infinite loop. But it you type take 10 l', it works.
A warning though, this function (that was just for learning purpose) has a huge flaw: it returns the final generator, but you can't use it. If you try, it will run into an infinite loop.

Now In your version, the first thing the function does is call itself recursively. So before you can get a result, you will do all the recursive calls until the last one.

David.
```_______________________________________________