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..100000] 0
(5000050000,100001)
(3.65 secs, 20702676 bytes)
Main> f2 [0..100000] 0 0
(5000050000,100001)
(3.15 secs, 14718856 bytes)
Main> fst (f [0..100000] 0)
5000050000
(2.04 secs, 18720784 bytes)
Main> fst (f2 [0..100000] 0 0)
5000050000
(2.36 secs, 13372372 bytes)
Main> f3 [0..100000] 0
5000050000
(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... :)
