# [Haskell-cafe] Optmiization of recursion

Marcin 'Qrczak' Kowalczyk qrczak at knm.org.pl
Tue Sep 28 15:44:25 EDT 2004

```John Goerzen <jgoerzen at complete.org> writes:

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

sum n []     = n
sum n (x:xs) = (sum \$! n + x) xs

It's unfortunate that it requires \$! or seq, but it's the only
*reliable* way (not relying on optimizing compilers).

That's why I would prefer to have foldl' in the standard. It's too
easy to forget about it. It should be encouraged in these accumulator
loop patterns.

> 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

The first "in" and second "let" should be removed.

For my language Kogut I invented a loop syntax which would look like
this if it was available in Haskell (loop and again are keywords):

sum l = loop (l, 0) of
(x:xs, n) -> again (xs, x + n)
([],   n) -> n

or maybe like this (unfortunately it would be inconsistent with case
which uses a single expression only):

sum l = loop l 0 of
(x:xs) n -> again xs (x + n)
[]     n -> n

This suffers from the same laziness problem as foldl, \$! or seq should
be used.

--
__("<         Marcin Kowalczyk
\__/       qrczak at knm.org.pl
^^     http://qrnik.knm.org.pl/~qrczak/
```