Unsure of how to get the right evaluation order

Question

I'm not sure what the difference between these two pieces of code is (with respect to x), but the first one completes:

$ foldr (\x y -> if x == 4 then x else x + y) 0 [1,2 .. ]
10

and the second one doesn't (at least in GHCi):

$ foldr (\x (y, n) -> if x == 4 then (x, n) else (x + y, n + 1)) (0, 0) [1,2 .. ]
.......

What am I doing wrong that prevents the second example from completing when it hits x == 4, as in the first one?

I've tried adding bang-patterns to both the x and to the x == 4 (inside a let) but neither seems to make a difference.

Answer 1

Your second example has two related problems.

Recall that foldr produces a right-associative nesting, i.e., foldr f z [a, b, c] = f a (f b (f c z)). Thus, the second argument to the function you give foldr represents the final value of folding the entire remaining list. In the case of an infinite list, this is only possible if you either generate another lazy infinite data structure or, at some point, ignore the second parameter entirely, as your first example does.

Your second example always uses the second item in the input tuple to compute the second item of the result tuple, so when applied to an infinite list you end up with an infinite regress. Specifying 0 as the "starting" value doesn't help, because in foldr the starting value is placed at the end of the list, which an infinite list clearly doesn't have--it seems you want to pass the value along unchanged, but that requires having a value to begin (or perhaps "end") with!

That much only causes the second item in the result to be non-terminating. The first item of the result is well-defined, or at least could be. The problem here is that pattern matching forces evaluation, which prevents any result from being produced until the entire fold is finished. This can be avoided in several ways, but simply using fst and snd is easy enough: \x yn -> if x == 4 then (x, snd yn) else (x + fst yn, snd yn + 1) should give you a result consisting of a tuple whose first item is what you expect (but whose second item is undefined, as explained above).

Answer 2

The first one doesn't use the value from the "accumulator" (i.e. y), whereas the second one does, by using n. Computing n requires folding the entire list, which is why it never terminates. No amount of strictness will fix that.

In fact, your algorithm does not do what you think it does. You are probably confusing foldr's behavior with foldl. Even if you could somehow compute n, its value would be infinite. The best way to think about foldr is that it replaces every (:) in the list with the first function and replaces the terminal [] with the second value.

Answer 3

It's the way the pattern matching/evaluation happens. If you let f = \x (y, n) -> ... as you've defined it, then

foldr f (0, 0) [1,2 .. ] =
   f 1 (foldr f (0,0) [2..]) =
   (\x (y, n) -> ...) 1 (foldr f (0,0) [2..])

and that (y,n) pattern is matched strictly, so to compute anything at all, the second argument (foldr .. [2..]) needs to be computed, which then requires foldr .. [3..] and so on forever.

One can make the pattern match non-strict, using ~ (called a "irrefutable pattern"), which changes the behaviour somewhat.

> foldr (\x ~(y,n) -> if x == 4 then (x,n) else (x+y,n+1)) (0,0) [1..]
(10,

(where as the refutable version can't compute even the first element of the tuple.)