[Haskell-cafe] Optmiization of recursion

[John Goerzen]

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;;