I am wondering if oCaml optimizes this code to be tail recursive and if so does F#?
let rec sum xs =
match xs with
| [] -> 0
| x :: xs' -> x + sum xs'
views:
105answers:
2
+4
A:
No, this code is not tail recursive, and ocaml won't transform it. You have to do it yourself.
I don't know for F#, but I doubt it will optimize this.
Rémi
2010-02-27 13:08:03
+6
A:
In the recursive case (i.e. the case that xs is not empty) the last evaluated operation is the addition. For the function to be tail-recursive the last evaluated operation needs to be the recursive call to sum.
Functions like this are usually define using a helper function with an accumulator to make them tail-recursive. In this case that would be a function that takes the list to be summed and the current value of the sum. If the list is empty, it would return the current value of the sum. If the list is not empty, it would call itself with the tail of the list and the current value of the sum + the head of the list as arguments. The sum function would then simply call the helper function with the list and 0 as the current value of the sum.
sepp2k
2010-02-27 13:22:19
Yes, so it doesnt sound hard for oCaml to optimize. Just add a currentVal param and call sum xs', currentSum. Knowing its this simple i wanted to know if it does optimize. So you say it doesnt hmm.. I dont have oCaml bins on this machine so i cant check and know why it would or wouldnt.
acidzombie24
2010-02-27 13:51:00
@acidzombie24 It could optimize in this case, but if you came to rely on it you would experience stack overflows on slightly more complicated cases where the compiler cannot do the transformation. For instance you could expect the same transformation with a pure function from another module, and you would be right to expect it, but it would be impossible for the compiler to do the transformation because of separate compilation and because interfaces do not specify which functions are pure.
Pascal Cuoq
2010-02-28 20:27:48