Nested Scopes

The final comment I would like to make is that there is nothing that prevents us from nesting multiple where blocks, nest multiple let blocks, and mix and match let and where blocks. The following pieces of code are all valid (albeit not particularly meaningful or pretty):

veclen1 :: (Double, Double) -> Double
veclen1 (x, y) = sqrt sum
  where
    sum = x2 + y2
      where
        x2 = x * x
        y2 * y * y

veclen2 :: (Double, Double) -> Double
veclen2 (x, y) = sqrt sum
  where
    sum = x2 + y3
      where
        x2 = x * x
        y3 = y2
    y2 = y * y

veclen3 :: (Double, Double) -> Double
veclen3 (x, y) = let sum = let x2 = x * x
                               y2 = y * y
                           in  x2 + y2
                 in  sqrt sum

veclen4 :: (Double, Double) -> Double
veclen4 (x, y) = let sum = x2 + y2
                       where
                         x2 = x * x
                         y2 = y * y
                 in sqrt sum

veclen5 :: (Double, Double) -> Double
veclen5 (x, y) = sqrt sum
  where
    sum = let x2 = x * x
              y2 = y * y
          in  x2 + y2

Try them out in GHCi.

This brings us to the important concept of scopes. In class, we discuss that scoping rules in programming languages determine which names (functions, types, classes, variables, etc.) are visible at any given point in a program. The compiler uses these rules when evaluating an expression. For example, there may be multiple variables with the name x defined in our program. As long as they are all defined in different scopes, this is not a problem. In a statically scroped language, if we refer to x as part of some expression, say 2 * x, the compiler looks for a variable with name x in the scope containing the expression and then in the surrounding scopes, inside out, until it finds the smallest enclosing scope of the expression 2 * x that contains a variable with name x. The x in the expression 2 * x then refers to this variable in the smallest surrounding scope that contains a definition for x.

Many modern programming languages borrow curly brackets from C as the means to delimit code blocks, and thereby scopes. Haskell does not use curly brackets. This raises the question which language constructs in Haskell introduce scopes. The short answer: function definitions, let, where, and nothing else.

In more detail,

Every source code file constitutes a module in Haskell. That's the outermost scope of the source code file, within which all other scopes of this file are nested.
Every function definition introduces a scope. Without a where block, we cannot introduce any local variables in such a function scope. However, observe that from a function's point of view, function arguments are also local variables. If we have a function definition
```
f x = 2 * x
```
then we want the x in the expression 2 * x to refer to the function's argument x, not to some x defined in some surrounding scope.

So, function arguments are visible only in the scope defined by the function and in all nested scopes.
A where block does not introduce a new scope. The definitions in a where block merely become part of the scope corresponding to the function with which this where block is associated.
A let ... in ... expression defines a new scope. It introduces the variables defined after let.

Since where blocks contain equations to define local variables, we can attach where blocks to these equations and use let expressions in these equations. Similarly, the equations after let in a let ... in ... expression can contain nested let expressions and where blocks, and the equation after in can contain nested let expressions. This is the means by which we construct nested scopes.

A common idiom for constructing recursive functions is to define the actual recursion as a local function of the outer function. Since the local function has access to all variables and function arguments defined in surrounding functions, this eliminates the need to pass values defined in the outer function as arguments to each recursive call. The implementation of prune in the previous section used this trick. Here is another, simpler example: removing all elements that do not match a given predicate from a given list:

GHCi

>>> filter even [1,2,3,4,5]
[2,4]

Without the local function trick, we would implement filter like this:

filter :: (a -> Bool) -> [a] -> [a]
filter _    []                 = []
filter pred (x:xs) | pred x    = x : filter pred xs
                   | otherwise =     filter pred xs

We still haven't looked at lists in any detail, but the following explanation should help you read this function definition: The first argument to filter is a predicate that every element we don't throw away must satisfy. If we filter the empty list, [], then the result is the empty list because we don't have any elements to begin with. So we use the wildcard, _, for the predicate, because we don't care what it is. If the list is not empty, then it has a first element x, and a tail xs containing all the remaining elements. xs is empty if the list contains only one element. For a non-empty list x:xs, if x satisfies the predicate, then the first element in the filtered list should be x. The remainder of the list should then be produced by filtering the remainder of the list recursively. That's what the first branch of filter pred (x:xs) says: If pred x is true, then the result is x : filter pred xs, that is, the list that starts with x and has as tail the list produced by filtering xs recursively. If x does not satisfy the predicate pred, then x is not part of the result. Thus, the result of filtering x:xs is the same as filtering xs. That's what the second branch of filter pred (x:xs) says.

Note how we pass pred as the first argument to each recursive call. Here is how we eliminate this using a local function, often called go:

filter :: (a -> Bool) -> [a] -> [a]
filter pred = go
  where
    go []                 = []
    go (x:xs) | pred x    = x : go xs
              | otherwise =     go xs

go takes the list to be filtered as its only argument. To decide which elements to keep, it uses the predicate pred, which is filter's argument and to which go has access because the definition of go is nested inside the scope defined by filter.

Many Haskell programmers use local functions in this fashion for their terseness. However, this definition of filter using a local function that implements the recursion is in fact faster than our previous definition of filter. The reason is that passing around function arguments incurs a (small) runtime cost.