Re: Counting recursive calls
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. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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) It's easy to see that f xs = f2 xs 0 fst (f xs w) = fst(f2 xs 0 w) = f3 xs w Even though f looks better, I'd say f2 is more efficient as it uses an accumulation process to calculate the number of steps - tested it in ghci and seems like I was right. 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. I have tested this functions in ghci with g = (+) -- Main f [0..10] 0 (55,11) (3.65 secs, 20702676 bytes) Main f2 [0..10] 0 0 (55,11) (3.15 secs, 14718856 bytes) Main fst (f [0..10] 0) 55 (2.04 secs, 18720784 bytes) Main fst (f2 [0..10] 0 0) 55 (2.36 secs, 13372372 bytes) Main f3 [0..10] 0 55 (1.90 secs, 10315336 bytes) - (**) So, - f3 is better then f and f2, if I don't need the n. of steps. - f2 is better then if if I want the n. of steps. - f is better then f2 if I don't want the n. of steps. Now what I want: [1] I would appreciate if someone could explain this behavior. I tried simulating what this functions do, and see if by using 'fst' they will, or will not, need to evaluate the n. of steps. (obviously it is not that simple, because fst always makes some difference, more in f than f2) I have some ideas that might explain what is happening, but I since I still do not feel confortable with this sort of efficiency reasoning, so I have some trouble expressing myself about it. (##) Yes, I am going to start reading about efficiency in haskell :) I'd just prefer to have the answer sooner. [2] Any tips on which function(s) should I choose, or any way to make them more efficient. Thanks in advance J.A. - (**) 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... (##) OK, I can't say my english is perfect, mainly when it comes to technical issues, so sometimes I have trouble expressing about many other things things. Feel free to correct my spelling, grammar, etc... :) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
