[More ch03 progress Bryan O'Sullivan **20080319064005] { addfile ./examples/ch03/RoundToEven.hs addfile ./examples/ch03/roundToEven.ghci hunk ./en/ch03-funcs-types.xml 91 - must explicitly coerce types by calling functions . + must explicitly coerce types by applying coercion + functions. hunk ./en/ch03-funcs-types.xml 608 + + Understanding a function's type signature + + Let's take a look at a function's type. + + &func.ghci:lines.type; + + We can read the -> above as + to, which loosely translates to + returns. The signature as a whole thus reads as + lines has the type + String to list-of-String. + Let's try applying the function. + + &func.ghci:lines; + + The \n in the input string is an + escaped newline (line ending) character: + lines splits a string on line boundaries. + Notice that its type signature gave us a strong hint as to what + the function might actually do. This is an incredibly valuable + property of types in a functional language. + + A side effect modifies the state of the + system, for example by reading or writing a file. Most Haskell + functions can't cause side effects, so we refer to them as + pure. The result of applying a pure + function can only depend on its arguments. We can often get a + strong hint of what a pure function does by simply reading its + name and understanding its type signature. As an example, let's + look at not. + + &func.ghci:not.type; + + Even if we didn't know the name of this function, its + signature alone limits the possible valid behaviours it could + have. + + + + Ignore its argument, and always return either + True or False. + + + Return its argument unmodified. + + + Negate its argument. + + + + hunk ./en/ch03-funcs-types.xml 896 - into the language: it's a normal function! + into the language: it's an ordinary + function. + + The (||) operator short + circuits: if its left operand evaluates to + True, it doesn't evaluate its right operand. In + most languages, short-circuit evaluation requires special + support, but not in Haskell. We'll see why shortly. hunk ./en/ch03-funcs-types.xml 906 - Next, our function calls itself recursively. + Next, our function applies itself recursively. hunk ./en/ch03-funcs-types.xml 911 - several lines. We line the then and - else branches up under the if for - neatness, but this is not mandatory. If we wanted, we could - put all of them on a single line, but we'd end up with a long, - unreadable line. + several lines. We align the then and + else branches under the if for + neatness. This is not mandatory, provided we remember to use + some indentation. If we wanted, we could write the entire + expression on a single line, but it would be unreadably + long. hunk ./en/ch03-funcs-types.xml 926 - In our description of myDrop, we have - so far focused on surface features. We need to go deeper, and - develop a useful mental model of how function application works. - To do this, we'll walk through the evaluation of the expression - myDrop 2 "abcd". + In our description of myDrop, + we have so far focused on surface features. We need to go + deeper, and develop a useful mental model of how function + application works. To do this, we'll first work through a few + simple examples, until we can walk through the evaluation of the + expression myDrop 2 "abcd". + + We've talked several times about substituting an + expression for a variable, and we'll make use of this capability + here. Our procedure will involve rewriting expressions over and + over, substituting expressions for variables until we reach a + final result. This would be a good time to fetch a pencil and + paper, so that you can follow our descriptions by trying them + yourself. + + + Lazy evaluation + + We will begin by looking at the definition of a simple, + nonrecursive function. + + &RoundToEven.hs:odd; + + Here, mod is the standard modulo + function. The first big step to understanding how evaluation + works in Haskell is figuring out what the result of evaluating + the expression odd (1 + 2) is. + + Before we explain how evaluation proceeds in Haskell, let + us recap the sort of evaluation strategy used by more familiar + languages. First, evaluate the subexpression 1 + + 2, to give 3. Then apply the + odd function with n + bound to 3. Finally, evaluate 3 `mod` + 2 to give 1, and 1 == 1 to + give True. + + This way of evaluating an expression is referred to as + strict: the arguments to a function are + evaluated before the function is applied. Haskell chooses + another path: non-strict + evaluation. + + In Haskell, the subexpression 1 + 2 is + not reduced to the value 3. + Instead, we create a promise that when the + value of the expression odd (1 + 2) is needed, + we'll be able to compute it. This promise is referred to as a + thunk. This is all + that happens: we defer the work until it's actually needed. If + the result of this expression is never subsequently needed, we + will not compute it at all. + + Non-strict evaluation is often referred to as + lazy evaluation. + + This example doesn't give us a very complete picture of + how lazy evaluation works. Let's extend it. + + &RoundToEven.hs:demo; + + The demo function uses the + putStrLn function to print a + string. + + &roundToEven.ghci:demo; hunk ./en/ch03-funcs-types.xml 993 - We've talked several times about substituting an expression - for a variable, and we'll make use of this capability here. Our - procedure will involve rewriting expressions over and over, - substituting expressions for variables until we reach a final - result. It's a good idea to transcribe this description using a - paper and pencil, to be sure that you can follow it. + In order to print anything, demo + needs the values of n and + r. How are these computed? Let's walk + through the evaluation of demo (3 + 1), from the + perspective of a Haskell implementation. hunk ./en/ch03-funcs-types.xml 999 - When we start, our first step is to apply the function - myTake. We do this by giving the variable - n the value 2, and - xs the value "abcd". If - we substitute these values into the predicate, we get the - following expression. + We begin with the variable k bound to a thunk + representing 3 + 1, and the &let; bindings create + two more thunks for n and + r. hunk ./en/ch03-funcs-types.xml 1004 - &myDrop.ghci:myDrop1; + Not until we need to print the value of + n are any of these expressions evaluated. + At this point, to evaluate n, we must + evaluate k. This takes place with a twist. + When k is evaluated to the value + 4, the unevaluated expression in the thunk is + replaced with the evaluated result. This + is a form of memoisation: it ensures that + k is evaluated at most + once. hunk ./en/ch03-funcs-types.xml 1015 - We then evaluate enough of the predicate to find out what - its value is. We start by evaluating the - (||) expression. To determine its value, - the (||) operator needs to examine the - value of its left operand first. + Similarly, once we've evaluated n to + the value 9, we replace the unevaluated thunk + with the result 9. Once the time comes for us to + print the value of r, we don't need to + recalculate n: we just evaluate + roundToEven 9. hunk ./en/ch03-funcs-types.xml 1022 - &myDrop.ghci:myDrop2; + By now, we should be able to guess that the result of + roundToEven 9 is not the value 8, it + is a thunk: 9 - 1. We have to evaluate this + immediately in order to render it as a string, but it still + starts life as a thunk. + + + + A more involved example + + Let us now look at the evaluation of the expression + myDrop 2 "abcd", again so that we can print its + result. + + &myDrop.ghci:print; + + When we start, our first step + is to apply the function myDrop. We bind + the variable n to the value + 2, and xs to + "abcd". If we substitute these values into the + predicate, we get the following expression. + + &myDrop.ghci:myDrop1; + + We then evaluate enough of the predicate to find + out what its value is. This requires that we evaluate the + (||) expression. To determine its value, + the (||) operator needs to examine the + value of its left operand first. + + &myDrop.ghci:myDrop2; hunk ./en/ch03-funcs-types.xml 1055 - Substituting that value into the (||) - expression leads to the following expression. + Substituting that value into the + (||) expression leads to the following + expression. hunk ./en/ch03-funcs-types.xml 1059 - &myDrop.ghci:myDrop2a; + &myDrop.ghci:myDrop2a; hunk ./en/ch03-funcs-types.xml 1061 - If the left operand had evaluated to - True, (||) would not - need to evaluate its right operand, since it could not affect - the result of the expression. Since it evaluates to - False, (||) must - evaluate the right operand. + If the left operand had evaluated to + True, (||) would not + need to evaluate its right operand, since it could not affect + the result of the expression. Since it evaluates to + False, (||) must + evaluate the right operand. hunk ./en/ch03-funcs-types.xml 1068 - &myDrop.ghci:myDrop3; + &myDrop.ghci:myDrop3; hunk ./en/ch03-funcs-types.xml 1070 - We now substitute this value back into the - (||) expression. Since both operands - evaluate to False, the - (||) expression does, too, thus the - predicate evaluates to False. + We now substitute this value back into the + (||) expression. Since both operands + evaluate to False, the + (||) expression does too, thus the + predicate evaluates to False. hunk ./en/ch03-funcs-types.xml 1076 - &myDrop.ghci:myDrop4; + &myDrop.ghci:myDrop4; hunk ./en/ch03-funcs-types.xml 1078 - This causes the &if; expression's else branch - to be evaluated. This branch contains a recursive application of - myDrop. + This causes the &if; expression's + else branch to be evaluated. This branch contains + a recursive application of myDrop. + + + Short circuiting for free + + Many languages need to treat the logical-or operator + specially so that it short circuits if its left operand + evaluates to True. We can see from this + example that we don't need any extra support in order for + Haskell's (||) operator to short + circuit: non-strict evaluation builds this capability into + the language. + + hunk ./en/ch03-funcs-types.xml 1098 - When we apply myDrop recursively, we - substitute the values in the caller of n - and xs to get the expressions that we - should now use: n is bound to the - expression 2 - 1, and xs to - the expression tail "abcd". + When we apply myDrop + recursively, n is bound to the thunk + 2 - 1, and xs to tail + "abcd". hunk ./en/ch03-funcs-types.xml 1115 - Notice that we didn't evaluate the expression 2 - - 1 until we needed its value. This is our first step - towards understanding lazy evaluation! We also evaluate the - right operand lazily, deferring tail "abcd" until - we need its value. + As we should now expect, we didn't evaluate the + expression 2 - 1 until we needed its value. We + also evaluate the right operand lazily, deferring tail + "abcd" until we need its value. hunk ./en/ch03-funcs-types.xml 1176 - substituting the result of the second recursive call for + substituting the result of the second recursive application for hunk ./en/ch03-funcs-types.xml 1182 - Finally, we return from our original call, substituting - the result of the first recursive call. + Finally, we return from our original + application, substituting the result of the first recursive + application. hunk ./en/ch03-funcs-types.xml 1189 - call, none of them needs to evaluate the expression tail - "bcd": the final result of applying this function is - an expression. The expression is only + application, none of them needs to evaluate the expression tail + "bcd": the final result of evaluating the original expression is + a thunk. The thunk is only hunk ./en/ch03-funcs-types.xml 1223 - - Understanding a function's type signature - - Let's take a look at a function's type. - - &func.ghci:lines.type; - - We can read the -> above as - to, which loosely translates to - returns. The signature as a whole thus reads as - lines has the type - String to list-of-String. - Let's try applying the function. - - &func.ghci:lines; - - The \n in the input string is an - escaped newline (line ending) character: - lines splits a string on line boundaries. - Notice that its type signature gave us a strong hint as to what - the function might actually do. This is an incredibly valuable - property of types in a functional language. - - A side effect modifies the state of the - system, for example by reading or writing a file. Most Haskell - functions can't cause side effects, so we refer to them as - pure. The result of applying a pure - function can only depend on its arguments. We can often get a - strong hint of what a pure function does by simply reading its - name and understanding its type signature. As an example, let's - look at not. - - &func.ghci:not.type; - - Even if we didn't know the name of this function, its - signature alone limits the possible valid behaviours it could - have. - - - - Ignore its argument, and always return either - True or False. - - - Return its argument unmodified. - - - Negate its argument. - - - - hunk ./en/ch03-funcs-types.xml 1275 - When we want to call last on, say, a + When we want to apply last to, say, a hunk ./examples/ch03/RoundToEven.hs 1 +import Prelude hiding (odd) + +{-- snippet odd --} +odd n = n `mod` 2 == 1 +{-- /snippet odd --} + +{-- snippet demo --} +roundToEven n = if odd n + then if n < 0 + then n + 1 + else n - 1 + else n + +demo k = let n = k + 5 + r = roundToEven n + in putStrLn ("n: " ++ show n ++ ", r: " ++ show r) +{-- /snippet demo --} hunk ./examples/ch03/myDrop.ghci 84 +--# print +print (myDrop2 "abcd") + hunk ./examples/ch03/roundToEven.ghci 1 +--# demo +:load RoundToEven +demo 2 +demo 9 +demo (-8) }