How does variable binding work with recursion in Haskell?

Question

I was reading about Haskell and it stated that once a variable is bound to an expression it cannot be rebound for example

x = 10
x = 11

Assign.hs:2:1: error:
    Multiple declarations of ‘x’
    Declared at: Assign.hs:1:1
                 Assign.hs:2:1

So if this is the case... how is recursion working where the same variable keeps getting bound to other things? For example

drop n xs = if n <= 0 || null xs
              then xs
              else drop (n-1) (tail xs)

the variable n... is being bound again and again every time the function recurses. Why is this allowed?

Also if you guys could tell me some key words to search for so I can learn more about this myself I'd highly appreciate it.

Answer 1

Haskell has lexical scoping. When you declare a variable inside a scope, it hides any variable with the same name from an outer scope. For example, in the following program,

x :: Int
x = 5

main :: IO ()
main = do
         x <- readLn :: IO Int
         print x

If you compile with ghc -Wall, it will compile correctly, but give you the following warnings:

sx-scope.hs:2:1: warning: [-Wunused-top-binds]
    Defined but not used: ‘x’

sx-scope.hs:6:10: warning: [-Wname-shadowing]
    This binding for ‘x’ shadows the existing binding
      defined at sx-scope.hs:2:1

So the x outside main and the x in main are different variables, and the one in the inner scope temporarily hides the one in the outer scope. (Okay, “temporarily” in this example means until main returns, which is as long as the program is running, but you get the concept.)

Similarly, when you declare drop n xs or \n xs ->, n and xs are local variables that only exist during that invocation of the function. It can be called more than once with different values of n and xs.

When a function is tail-recursive, that is, returns a call to itself, the compiler knows it is about to replace the old parameters, which were from a scope that no longer exists, with updated parameters of the same type. So it can re-use the stack frame and store the new parameters in the same locations as the previous ones. The resulting code can be as fast as iteration in a procedural language.