Why doesn't this function bottom out

Question

xs = [1, 2] ++ undefined
length $ take 2 $ take 4 xs

My brain is reading this as

length (take 2 ( take 4 xs ) )

If everything in the parenthesis is evaluated first, then why does this not error out with Exception: prelude.undefined?

The answer given by the book is that take 2 is only taking the first two indices, but shouldn't the take 4 take precedence here and get evaluated first?

Answer 1

If everything in the parenthesis is evaluated first, then why does this not error out with Exception: prelude.undefined?

Because Haskell is lazy. That means it does not evaluate anything unless it is necessary.

Indeed, length will need access to the list (but not to its elements if these contain calculations). It will thus ask the take 2 ( take 4 xs ) ) for the first elements, and then the second, and then the third, etc.

Now take is lazy as well. It means as long as it does not need to be evaluated, it will do nothing. In case the length asks the next element it will determine that element, if later another element is asked, it will provide the second element for the list. If the length asks for another one, then take 2 will stop, and thus return the empty list.

Haskell thus has not an evaluation strategy like Python or Java where the innermost functions are first evaluated and left to right.

Answer 2

Let's calculate! What is [1, 2] ++ undefined? Well, to know that, we first need to know what [1, 2] is. It's really just syntactic sugar for 1:2:[].

Next, we need to know what ++ is. The source code tells us:

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x : xs) ++ ys = x : xs ++ ys

Okay. So let's pattern match.

(1:2:[]) ++ undefined
= -- the second pattern matches
1 : (2:[]) ++ undefined
= -- the second pattern matches
1 : 2 : [] ++ undefined
= -- the first pattern matches
1 : 2 : undefined

Okay, so we've figured out that

xs = 1 : 2 : undefined

What about take 4 xs? Well, we first have to look at what take does. The real source code is somewhat complicated for performance reasons, but we can use this simpler, equivalent, version:

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (a : as) = a : take (n - 1) as

So

take 4 xs
= -- value of xs
take 4 (1:2:undefined)
= -- 4 is positive, so the first guard falls through.
  -- the second pattern fails (the list isn't empty)
  -- the third pattern succeeds
1 : take 3 (2:undefined)
= -- same analysis
1 : 2 : take 3 undefined
= -- 3 is positive, so the guard fails.
  -- the pattern match on undefined produces undefined
1 : 2 : undefined

That's just the same as xs!

Next we calculate

take 2 (take 4 xs)
= -- as shown above
take 2 (1 : 2 : undefined)
= -- following the same sequence above
1 : take 1 (2 : undefined)
= -- same same
1 : 2 : take 0 undefined
= -- this time the guard succeeds!
1 : 2 : []
= -- reinstalling syntactic sugar
[1, 2]

So now you have a fully defined list of two elements, and taking its length poses no special challenge at all.

---

Note that the above is a calculation. It does not represent the actual sequence of operations that occur when the program runs. But ... that doesn't actually matter. One of the great things about Haskell is that in your analysis, you can "substitute equals for equals" whenever you want. It won't affect the result. You do have to be a bit careful, however, not to let it confuse you. For example, suppose you want to evaluate null (repeat ()). You'd start out something like this:

repeat () = () : repeat ()

What do you do next? Well, one option is to continue to expand repeat ():

repeat () = () : () : repeat ()

It's totally valid. But if you keep going on that way forever, you'll never get to an answer. At some point, you have to look at the rest of the problem.

null (() : repeat ())

is immediately False. So just because you can find an infinite sequence of reductions doesn't mean there's an infinite loop. Indeed, the way Haskell works, there's only an infinite loop if every possible sequence of reductions is infinite.

Answer 3

Because you're not forcing the thunk after take 4 xs. Consider the following code in the repl

Prelude> xs = [1, 2] ++ undefined
Prelude> take 4 xs
[1,2*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries\base\GHC\Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:16 in interactive:Ghci1

This happens because of the implicit show in GHCi. But what if we don't use a bare expression?

Prelude> xs = [1, 2] ++ undefined
Prelude> ys = take 4 xs

Hey look no error! Let's keep going

Prelude> xs = [1, 2] ++ undefined
Prelude> ys = take 4 xs
Prelude> zs = take 2 ys
Prelude> length zs
2