mixing foldr with OR in Haskell (laziness?)

Question

How can this function return true?

foldr (||) False [True,undefined] 

=> True

The first fold looks like this:

undefined || True 

, which should return an error

So im guessing haskell gives priority to the lazyness of the OR function over doing the folds step by step. Finds a True on the way and returns that before starting the fold

Is this correct? In that case, does haskell always give priority to a lazy function over the non lazy ones? I believe that is the definition for being lazy but it seems like that can change the answer to make it wrong

Jannajannel

Why do you believe the first fold looks like undefined || True? Because that is incorrect, so if you can explain why you believe that, we may be able to point to the error in your reasoning that led to that conclusion. – Chlorate

@DanielWagner it would be the first use of (||) evaluated if foldr actually folded from the right, the way it often does in strict languages. – Brunn

@Brunn One could argue that foldr does fold from the right, denotationally. Its "first" fold is undefined || False which is undefined. The "second" is True || undefined which is True since OR is lazy (as it would also be in Java,C,etc.). – Alcorn

Comparing "folds from the right" to "iterates right-to-left" is a sign that you're still thinking too imperatively. "folds from the right" is a statement about associativity, nothing more. – Rockery

@Brunn It does fold from the right in some sense; but in that sense, the "first" fold is actually undefined || False, not undefined || True! This does (would) become undefined, as you observed, but unlike in a lazy language, it turns out that just because some part of the computation has undefined doesn't mean the whole thing is undefined... – Chlorate

Answer 1

According to the definition of foldr,

foldr (||) False [True,undefined]
=
True || foldr (||) False [undefined]

According to the definition of (||),

True || _ = True

so there's no need to know the value of the right hand expression to know the answer.

foldr does not do steps on its own. The process is driven by the demands of the reducer function.

edit: Nothing funny's going on. Each evaluation step is straightforwardly done according to the definitions involved.

Zagreb