7stud | 15 May 20:03 2013
Picon

recursion patterns?

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

(I am a haskell beginner)

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
(Continue reading)

Henning Thielemann | 15 May 20:17 2013
Picon

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)

Then you might want to post your question to haskell-beginners mailing 
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.
7stud | 15 May 21:16 2013
Picon

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.
David Virebayre | 21 May 12:09 2013
Picon

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.
_______________________________________________
Haskell mailing list
Haskell <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Gmane