Counting recursive calls

[John Hughes]

	Hi all, got some questions on recursive functions.
	I got a simple recursive function (f3)
	In *some* situations I'll want to know how many recursive calls did it make.
	I came up with two simple implementations to do that (f1) and (f2)


	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)

	...

	Anyway like I said I don't *always* want to know the n. of steps, so I could 
	chose either to:
	- use 2 different functions, 
	  one when I want the n. of steps (f or f2) 
	  another one when I don't need it (f3)
	- use just one function 
	  (f or f2) if I don't need the n. of steps, use fst.

	The second choice seemed to make more sense to me. Lazy evaluation should do 
	the trick, and the n. of steps would not have to be evaluated, so 
	efficiency-wise it would be the same as calling f3.

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.

	...

	[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.

	-----

	(**) 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.

John