[Haskell-cafe] Optmiization of recursion
John Goerzen
jgoerzen at complete.org
Tue Sep 28 15:17:47 EDT 2004
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;;
More information about the Haskell-Cafe
mailing list