On Tuesday 28 September 2004 01:54 am, Iavor S. Diatchki wrote:
OTOH there are a few classical cases in haskell where you run out of space even if you have a tail recursive function: e.g. sum n [] = n sum n (y:ys) = sum (n + y) ys the reason for this that the n+y expression never gets evaluated until the very end, so you create many suspensions in memory.
Eep. So that seems like being stuck between a rock and a hard place. (Thanks for mentioning it, btw) If I instead wrote: sum [] = 0 sum (x:xs) = x + sum(xs) then I have the same problem. What is the proper way to solve this little problem then? Would foldl suffer from the same issue?
5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell?
i'd imagine these would be much the same as in o'caml. a common functional programming pattern when you get tail recursion is to rewrite a function using an accumulator (i.e. a bit of local state).
Yup, I have done just that in OCaml. I find it more tasteful to hide the accumulator from the caller. To write the sum, I might do this (forgive me if this is not valid Haskell, I'm still new to this) sum x = let sum2 n [] = n in let sum2 n (y:ys) = sum (n + y) ys in sum2 0 x Or, in OCaml: let sum x = let rec sum2 n y = match y with [] -> n | x:xs -> sum2 (n + x) xs in sum2 0 x;;