[Haskell-cafe] Optmiization of recursion

[Marcin 'Qrczak' Kowalczyk]

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/