Ok. I was confused about left vs. right associative versions of foldl*.
But, foldl' doesn't have the right behavior either. Suppose you define (+/):
> x +/ y = 5
> foo' n = foldl' (+/) 0 [1..n]
foo' takes O(n) time when it should be a constant time operation.
The reason is that foldl' insists on making a pass through the
entire list. This pass is unnecessary because the function does not
actually use its arguments. foldl' fails to terminate on infinite data
structures. The problem is that Haskell evaluates foldl or foldl' like
this:
foldl version foldl' version
= foldl (+) 0 [1..10000] = foldl' (+) 0 [1..10000]
= foldl (+) (0+1) [2..10000] = foldl' (+) 1 [2..10000]
= foldl (+) ((0+1)+2) [3..10000] = foldl' (+) 3 [3..10000]
It should really evaluate like this:
= foldl (+) 0 [1..10000]
= 0 + foldl (+) 1 [2..10000]
= (0+1)+ foldl (+) 2 [3..10000]
= ((0+1)+2) + foldl (+) 3 [4..10000]
If Haskell evaluated foldl in the second manner then foldl (+/) 0 [1..n]
would be constant time rather than O(n) and could be applied to infinite
sequences.
That being said, I don't know how to write foldl so that it evaluates in
constant time.
-Alex-
* There are two versions of lazy foldl, one that is left associative
(the one in report) and one that is right associative (the one I
proposed). They are different because e.g.
foldl (/) 1 [1.0..10.0] /= myfoldl (/) 1 [1.0..10.0]
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-212-697-0184 voice 1-212-697-1427 fax
On Sat, 27 Jun 1998, Koen Claessen wrote:
> On Fri, 26 Jun 1998, S. Alexander Jacobson wrote:
>
> | > myFoldl f s [] = s
> | > myFoldl f s (x:xs) = f s (foldl f x xs)
>
> | > total = 3 + (myFoldl (+) 3 [4..100000])
>
> | > total = 3 + 4 + (myFoldl (+) 4 [5..100000])
>
> The problem is parenthesis; the last expression should have been:
>
> total = 3 + (4 + (myFoldl (+) 4 [5..100000]))
>
> So there is no way to add 3 and 4, unless you require the runtime system
> to look for associative operators partially applied to closures. Which is
> undoable, in my opinion.
>
> Regards,
> Koen.
>
> --
> Koen Claessen,
> [EMAIL PROTECTED],
> http://www.cs.chalmers.se/~koen,
> Chalmers University of Technology.
>
