3

the following Haskell code does not terminate, can someone please explain why? Thanks.

f = let x = 10 in let x = x * x in x

I think the interpreter first binds x : 10, then evaluates x * x to 100 and binds x : 100, and the environment becomes x : 100, then the whole expression evaluates to 100

However, this code does not terminate.

Improve this question
5
  • 5
    let expressions are recursive, so when you have let x = x * x, it's all the same x, not the one from the outer scope. Commented Feb 17, 2015 at 2:09
  • if that's the same one, why it doesn't report an error because the lookup of x fails? Commented Feb 17, 2015 at 2:23
  • 1
    Recursive definitions are central to many aspects of Haskell, such as map f [] = []; map f (x:xs) = f x : map f xs. We want the instance of map to the right of the = to be the same as the map on the left side of the =. There is even the function fix which is defined as fix f = let x = f x in x, and it can actually produce valuable results, a trivial one being fix (1:), which creates an infinite lazy list of 1s that refers to the same 1 over and over again so it won't blow up in RAM. Commented Feb 17, 2015 at 2:27
  • Do you mean this is infinite because of the lazy evaluation of x = x * x? I think if you first evaluate x in the RHS of x = x * x then there would be no problem. However, if you first evaluate x = x * x without first evaluating the x in the RHS, x is bound to x * x, then evaluating the x in x * x would lead to this non-termination, right? Commented Feb 17, 2015 at 2:37
  • 1
    Why is this downvoted? and the vote to close seems very unjustified too. Commented Feb 17, 2015 at 3:51

1 Answer 1

Reset to default
8

When evaluating a let-statement of the form let foo = bar in baz, foo is already bound to bar while evaluating bar - that is definitions are recursive and if there is an outer binding with the same name, it is simply ignored as it is no longer in scope.

In a comment you asked why you don't then get an error about the lookup of x failing. The reason for that is that the lookup of x does not fail. Haskell knows that x is equal to x * x, so that's what the lookup produces.

So when x is evaluated, it is replaced with its definition x * x. To evaluate that it then replaces the first of the xs with its definition, yielding x * x * x, then x * x * x * x and so on ad infinitum.

You might wonder why values are allowed to be recursive that way, so here's an example that is actually useful and does not just lead to an infinite loop: let xs = 42 : xs in take 2 xs produces the result [42, 42]. Here xs is expanded to 42 : xs and then 42 : 42 : xs and then it stops because take 2 only needs the first two elements, so that's where it stops.

And of course when the rhs is a function, it's immediately obvious that it's useful for the definition to be recursive: let fac = \n -> if n = 0 then 1 else n * fac (n-1) - here you obviously want fac to refer to itself and not some previous definition of fac.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I see, that's exactly what I was thinking. Can I think of this as the lazy evaluation of Haskell?
Seems like the environment allows binding non-values to variables.
@xwang: Yes, in a strict language recursive value definitions would not be possible (except in a few special cases like cyclic definitions using data constructors - let rec xs = 42 :: xs in OCaml would be an example of that).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.