Search code examples
listhaskelllazy-evaluationevaluationfold

Why is foldr not returning undefined when folding over a list containing undefined?


I'm having trouble understanding why the following:

foldr (\x y -> x && y) True [False,undefined,True]

is not giving me an undefined exception.

How I see it is, foldr compares True and the last element of the list, which would be True, thus returning True and now comparing it to undefined. Does Haskell ignore the operation if it involves an undefined type? I'd understand that the output were True if in the anonymous function we had x || y instead of (&&), since the compiler would see that one of the operators is already set to True, but since we're working with an (&&) it has to check that both values are set to True or one of them to False, right?

Any clue as to why it returns False?


Solution

  • It's not ignoring undefined so much as undefined is never seen.

    The real definition of foldr is slightly more complicated, but we can pretend that it is defined (in part) as

    foldr f z (x:xs) = f x (foldr f z xs)
    

    Thus, after one step, we have

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

    Since False && _ == False, there is no need to evaluate the recursive call to foldr, and thus no need to do anything with undefined.


    undefined only raises an exception if it is evaluated. It doesn't need to be evaluated to define the list [False, undefined, True], which is syntactic sugar for False : undefined : True : [], and (:) is lazy in its second argument.