I've been reading this http://www.haskell.org/haskellwiki/Hask. I'm struggling with this part..
undef1 = undefined :: a -> b
undef2 = \_ -> undefined
And why they behave like this..
seq undef1 () = undefined
seq undef2 () = ()
undef2 () = undefined
What is the reason for this? I would like to understand this behaviour but I don't even know where to begin. In particular, why does undef2 behave differently under strict evaluation?
The special function seq evaluates its first argument to weak head normal form and then returns its second argument. A good explanation of WHNF can be found here, but for the purposes of this answer I'll just use the Haskell wiki definition:
An expression is in weak head normal form (WHNF) if it's either:
- a constructor (eventually applied to arguments) like True, Just (square 42) or (:) 1
- a function applied to too few arguments (perhaps none) like (+) 2 or sqrt.
- or a lambda abstraction \x -> expression.
An important point is that when an expression is a constructor, seq only looks at the constructor's tag. Thus, seq (Just undefined) 1 evaluates to 1.
Another important point is that all types in Haskell are lifted - that is, evaluating a value of the type can lead to an infinite loop being executed or an exception being thrown (usually with error or undefined). After we've evaluated seq a b, we can be sure that evaluating a to WHNF won't lead to an infinite loop or an exception.
Armed with this knowledge, let's look at your example:
undef1 = undefined :: a -> b
undef2 = \_ -> undefined
When seq undef1 () is evaluated, seq first tries to find out which of the three categories above undef1 belongs to. But undef1 is undefined, and so the whole expression evaluates to undefined.
However, in the case of seq undef2 () = (), the first argument is a lambda abstraction. Since seq can't see past the lambda, it returns the second argument.
The third example, undef2 () = undefined, is just a straightforward result of evaluating the application (\_ -> undefined) ().
They're not the same thing. undef1 is a function from a to b, but which function is undefined. Evaluating undef1 to head normal form gives you undefined.
undef2 is a function from a to b. Specifically, it is a function that ignores its argument and returns undefined. But undef2 isn't undefined itself. Only when you try to evaluate the function (as in your third line) you get undefined. So when you evaluate undef2 to head normal form, you get a proper function, not undefined.
To put it into more imperative terms (always a source for inaccuracy, but if you're more familiar with that, it illustrates the point nicely), think of undef1 as a property getter that never returns. (In Haskell, not returning and undefined are semantically equivalent.) undef2 is a property getter that returns a function; it's that function that won't return if you call it. In C#:
Func<Object, Object> Undef1 {
get {
while (true) {}
return null;
}
}
Func<Object, Object> Undef2 {
get {
return _ -> {
while (true) {}
return null;
}
}
}
Now your tests become:
var x = Undef1;
var y = Undef2;
var z = Undef2(null);
For the sake of this question, let's say that there are three things that can force a value to actually be evaluated:
seqThe actual situation is slightly more complicated, but not in a way that matters here.
Furthermore, this forcing only occurs in the context of some outer expression, so rather than thinking of these as "forcing evaluation" in some abstract way, it helps to think of them as making the evaluation of the outer expression dependent on the evaluation of that value. This is why, for example, seq x x does not force x in any sense, since that's the final value of the expression anyway; it says that when the outer expression (whose value is x) is evaluated, it should also evaluate x, which is redundant.
Finally, any value that depends on forcing an undefined value is itself undefined.
Going through each expression:
seq undef1 () = undefined
In this case undef1 is undefined, and seq undef1 x is an expression whose value is x and depends on evaluating undef1. So the expression as a whole is undefined as well no matter what the second argument to seq is.
seq undef2 () = ()
In this case, undef2 is not undefined, but the result of applying it is. seq undef2 x is an expression whose value is x and depends on evaluating undef2. This causes no problems, and the first argument to seq is discarded, so the value of the expression is () here.
undef2 () = undefined
In this case, we're applying undef2 directly. The expression undef2 () depends on the evaluation of undef2 (which is fine) and evaluates to the result of applying undef2, which in this case is undefined.
Contrast this with a fourth case:
undef1 () = undefined
In this case, we're applying undef1, so the value of the expression depends on evaluating undef1, which is undefined and therefore so is the whole expression. This is the same "value" as the previous expression using undef2, but for a very different reason!
Well, just to write a briefer answer than the others: in order to force evaluation of an expression like f x, Haskell first needs figure out what function f is, then apply it x. In more technical terms, whenever f x is forced, f must be forced.
Let's go back to your definitions now:
undef1 :: a -> b
undef1 = undefined
undef2 :: a -> b
undef2 = \_ -> undefined
Forcing undef1 and undef2 produces different outcomes. Forcing undef1 produces undefined right away, whereas forcing undef2 produces a thunk that, when applied to some argument, produces undefined.
I suspect you're misunderstanding what seq does; I get the impression that you think seq undef2 () is supposed to apply undef2 to (), but it doesn't do that. What seq :: a -> b -> b does is to force its first argument and return the second one. The difference between seq undef1 () and seq undef2 () is simply that only the second one succeeds at forcing its first argument, but then it simply returns ().
If I'm right about your intent with the code above, what you're looking for is ($!) :: (a -> b) -> a -> b, which applies its first argument to the second one and forces the result. So both of these fail with undefined:
undef1 $! ()
undef2 $! ()
