Does a function in Haskell always evaluate its return value?

Question

I'm trying to better understand Haskell's laziness, such as when it evaluates an argument to a function.

From this source:

But when a call to const is evaluated (that’s the situation we are interested in, here, after all), its return value is evaluated too ... This is a good general principle: a function obviously is strict in its return value, because when a function application needs to be evaluated, it needs to evaluate, in the body of the function, what gets returned. Starting from there, you can know what must be evaluated by looking at what the return value depends on invariably. Your function will be strict in these arguments, and lazy in the others.

So a function in Haskell always evaluates its own return value? If I have:

foo :: Num a => [a] -> [a]
foo [] = []
foo (_:xs) = map (* 2) xs

head (foo [1..]) -- = 4

According to the above paragraph, map (* 2) xs, must be evaluated. Intuitively, I would think that means applying the map to the entire list- resulting in an infinite loop. But, I can successfully take the head of the result. I know that : is lazy in Haskell, so does this mean that evaluating map (* 2) xs just means constructing something else that isn't fully evaluated yet?

What does it mean to evaluate a function applied to an infinite list? If the return value of a function is always evaluated when the function is evaluated, can a function ever actually return a thunk?

Edit:

bar x y = x
var = bar (product [1..]) 1

This code doesn't hang. When I create var, does it not evaluate its body? Or does it set bar to product [1..] and not evaluate that? If the latter, bar is not returning its body in WHNF, right, so did it really 'evaluate' x? How could bar be strict in x if it doesn't hang on computing product [1..]?

Answer 1

First of all, Haskell does not specify when evaluation happens so the question can only be given a definite answer for specific implementations.

The following is true for all non-parallel implementations that I know of, like ghc, hbc, nhc, hugs, etc (all G-machine based, btw).

BTW, something to remember is that when you hear "evaluate" for Haskell it normally means "evaluate to WHNF".

Unlike strict languages you have to distinguish between two "callers" of a function, the first is where the call occurs lexically, and the second is where the value is demanded. For a strict language these two always coincide, but not for a lazy language. Let's take your example and complicate it a little:

foo [] = []
foo (_:xs) = map (* 2) xs

bar x = (foo [1..], x)

main = print (head (fst (bar 42)))

The foo function occurs in bar. Evaluating bar will return a pair, and the first component of the pair is a thunk corresponding to foo [1..]. So bar is what would be the caller in a strict language, but in the case of a lazy language it doesn't call foo at all, instead it just builds the closure.

Now, in the main function we actually need the value of head (fst (bar 42)) since we have to print it. So the head function will actually be called. The head function is defined by pattern matching, so it needs the value of the argument. So fst is called. It too is defined by pattern matching and needs its argument so bar is called, and bar will return a pair, and fst will evaluate and return its first component. And now finally foo is "called"; and by called I mean that the thunk is evaluated (entered as it's sometimes called in TIM terminology), because the value is needed. The only reason the actual code for foo is called is that we want a value. So foo had better return a value (i.e., a WHNF). The foo function will evaluate its argument and end up in the second branch. Here it will tail call into the code for map. The map function is defined by pattern match and it will evaluate its argument, which is a cons. So map will return the following {(*2) y} : {map (*2) ys}, where I have used {} to indicate a closure being built. So as you can see map just returns a cons cell with the head being a closure and the tail being a closure.

To understand the operational semantics of Haskell better I suggest you look at some paper describing how to translate Haskell to some abstract machine, like the G-machine.

Answer 2

I always found that the term "evaluate," which I had learned in other contexts (e.g., Scheme programming), always got me all confused when I tried to apply it to Haskell, and that I made a breakthrough when I started to think of Haskell in terms of forcing expressions instead of "evaluating" them. Some key differences:

• "Evaluation," as I learned the term before, strongly connotes mapping expressions to values that are themselves not expressions. (One common technical term here is "denotations.")
• In Haskell, the process of forcing is IMHO most easily understood as expression rewriting. You start with an expression, and you repeatedly rewrite it according to certain rules until you get an equivalent expression that satisfies a certain property.

In Haskell the "certain property" has the unfriendly name weak head normal form ("WHNF"), which really just means that the expression is either a nullary data constructor or an application of a data constructor.

Let's translate that to a very rough set of informal rules. To force an expression expr:

• If expr is a nullary constructor or a constructor application, the result of forcing it is expr itself. (It's already in WHNF.)
• If expr is a function application f arg, then the result of forcing it is obtained this way:
  1. Find the definition of f.
  2. Can you pattern match this definition against the expression arg? If not, then force arg and try again with the result of that.
  3. Substitute the pattern match variables in the body of f with the parts of (the possibly rewritten) arg that correspond to them, and force the resulting expression.

One way of thinking of this is that when you force an expression, you're trying to rewrite it minimally to reduce it to an equivalent expression in WHNF.

Let's apply this to your example:

foo :: Num a => [a] -> [a]
foo [] = []
foo (_:xs) = map (* 2) xs

-- We want to force this expression:
head (foo [1..])

We will need definitions for head and `map:

head [] = undefined
head (x:_) = x

map _ [] = []
map f (x:xs) = f x : map f x

-- Not real code, but a rule we'll be using for forcing infinite ranges.
[n..] ==> n : [(n+1)..]

So now:

head (foo [1..]) ==> head (map (*2) [1..])       -- using the definition of foo
                 ==> head (map (*2) (1 : [2..])) -- using the forcing rule for [n..]
                 ==> head (1*2 : map (*2) [2..]) -- using the definition of map
                 ==> 1*2                         -- using the definition of head
                 ==> 2                           -- using the definition of *