Re: Counting recursive calls
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
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.
On Tue, 13 Nov 2001 13:09:17 +0000, Jorge Adriano wrote:
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 :)
:) I'll try to tackle this one. I have always had trouble understanding this concept, and I haven't been able to find a good definition or description on the web. It's always assumed you know what's being talked about, for some reason. A closure is a function and the context in which it runs. It's used mainly in those languages where functions can be passed around as values. Another way to see it, the C/C++ way, is that a closure is a function together with some contextual data attached to it. I guess the best way to describe it is by using an example in pseudocode: function MakeIncrementer (increment: int) : (function(int): int) { function Incrementer(num: int) : int { return num + increment; } return Incrementer; } Ok. MakeIncrementer returns a function that maps ints to ints, by adding an arbitrary value passed in to MakeIncrementer by its caller. You can use it to make functions that increment numbers by any amount you wish. Evidently, MakeIncrementer can return an infinite amount of different functions. This is made possible by returning a context together with that function. For example, you could manually implement this in C++ in this manner (returning a function object): --- struct IncrementerFuncObj { int increment; int operator()(int num) const { return num + increment; } }; IncrementerFuncObj MakeIncrementer(int increment) { IncrementerFuncObj result; result.increment = increment; return result; } --- And then use it as such: --- IncrementerFuncObj incrementer = MakeIncrementer(3); int five = incrementer(2); --- You can see it also as something similar to function pointers in C and C++, only a bit extended with a context that can be implemented as an object (like above) or an extra pointer that must be passed around. If I got anything wrong, or if I missed anything, I'd like to hear about it :)
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.
Same here. Salutaciones, JCAB email: jcab@roningames.com ICQ: 101728263 The Rumblings are back: http://www.JCABs-Rumblings.com
participants (3)
-
John Hughes -
Jorge Adriano -
Juan Carlos Arevalo-Baeza