[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/
More information about the Haskell-Cafe
mailing list