Counting recursive calls

Jorge Adriano jadrian@mat.uc.pt
Tue, 13 Nov 2001 13:09:17 +0000


The functions:

> 	f []     w =   (w,0)
> 	f (x:xs) w =   (nextw, steps+1)
> 	    where
> 	    (nextw, steps) = f xs (g x w)
>
>
> 	f2 []     k w  =   (w,k)
> 	f2 (x:xs) k w  =   f2 xs (k+1) (g x w)
>
>
> 	f3 [] w     = w
> 	f3 (x:xs) w = f3 xs (g x w)


> Oh oh --- lazy evaluation isn't what you want here! Certainly it will avoid
> *computing* the number of steps, but it will do so by building up a
> gigantic unevaluated closure of the form
> (((((((((0+1)+1)+1)+1)+1)+1)+1)+1)+1). So you'll be using memory linear in
> the running time -- not good. Moreover, when you finally come to evaluate
> that closure, you'll need a *huge* stack to do it on.

Yeap, that's exactly what I thought (I think - what exactly is a 'closure'? 
don't know if this question is off topic in here or not, anyway some pointers 
to some definition on the web will do :)

And why does the benifits of not computing the n. of steps are higher in f 
than in f2? 


> 	[2] Any tips on which function(s) should I choose, or any way to make them
> 	more efficient.
>
> Most efficient will be to force strict evaluation of the count. In GHC
> you can do that by using an unboxed integer.

Strictness will probably do the trick, (anyway that way I'll always compute 
the number of steps).
For some other stuff that I'm thinking about, the computation wil be a lot 
heavier, so strictness is maybe an option if I do want to compute it, but not 
if I don't need it. So in this case options are:
* (f2 +strictness) and f3 - depending on whether I want the computation or not
* f for both cases using fst. (but I'd have the stack problem)


I don't think I want to use unboxed integers, at least right now. I rather 
not use too much non-standard stuff. When I got my code where I want it maybe 
I'll try to make it run faster using some 'dirty' tricks, but not now. :)
There's also the chance that gch is smart enough to optimize it that way :)



> 	(**) would I get a different behavior if I had compiled the program.
> 	I've had some problems when trying to compile and use getCPUTime.
> 	Some stack overflows for big values of w, and for smaller values 0 in the
> 	execution time... I'll try to figure out what I'm doing wrong here...
>
> What did I say about the stack?
>
> If you compile your code, and especially if you use an unboxed integer as I
> suggest, then the cost for counting steps should be very low. In
> particular, it will certainly be cheaper to *compute* k+1 (single unboxed
> addition) than to build a suspension for it (memory allocation). You might
> get a different result in the interpreter, because of all the
> interpretation overhead, but in compiled code there should be no question
> about it.

Yes, I will try to complile it and see what I get.

Thanks :)

J.A.

P.S.: 
I for one, would rather have 'reply' directing our messages to the mailing 
list. My apologies to John Hughes for the personal reply.