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 _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe