Tuesday, October 21, 2014

Haskell Evaluation

Conditional evaluation

-- file: ch02/myDrop.hs
myDrop n xs = if n <= 0 || null xs
              then xs
              else myDrop (n - 1) (tail xs)  
The if keyword introduces an expression that has three components.
  • An expression of type Bool, immediately following the if. We refer to this as a predicate.
  • A then keyword, followed by another expression. This expression will be used as the value of the if expression if the predicate evaluates to True.
  • An else keyword, followed by another expression. This expression will be used as the value of the if expression if the predicate evaluates to False.
  • The null function indicates whether a list is empty, while the (||) operator performs a logical “or” of its Bool-typed arguments. 
ghci> :type null
null :: [a] -> Bool
ghci> :type (||)
(||) :: Bool -> Bool -> Bool

Operators are not special.Notice that we were able to find the type of (||) by wrapping it in parentheses. The (||) operator isn't “built into” the language: it's an ordinary function.

The following are equivalent

True || False
(||) True False

We'll refer to the expressions after the then  and else keywords as “branches”. The branches must have the same types; the if expression will also have this type. An expression such as if True then 1 else "foo" has different types for its branches, so it is ill typed and will be rejected by a compiler or interpreter.

In an imperative language, it can make sense to omit the else branch from an if, because we're working with statements, not expressions. However, when we're working with expressions, an if that was missing an else wouldn't have a result or type if the predicate evaluated to False, so it would be nonsensical.

It is an if *expression* rather than an if *statement*. This is an important distinction and worth stressing. An if expression must evaluate to a value, whereas an if statement can leave off the else clause as a shorthand for the 'do nothing' action. It still would not make sense to leave off the 'else' clause from an if-expression in a dynamically typed language.
Our procedure will involve rewriting expressions over and over, substituting expressions for variables until we reach a final result.

Lazy evaluation

In a language that uses strict evaluation, 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 isOdd (1 + 2) is needed, we'll be able to compute it. The record that we use to track an unevaluated expression is referred to as a thunk --  A thunk is a function which takes no arguments. -- a delayed computation -- This is all that happens: we create a thunk, and defer the actual evaluation until it's really needed. If the result of this expression is never subsequently used, we will not compute its value at all.

Non-strict evaluation is often referred to as lazy evaluation

  • It makes sense to use substitution and rewriting to understand the evaluation of a Haskell expression.
  • Laziness leads us to defer evaluation until we need a value, and to evaluate just enough of an expression to establish its value.
  • The result of applying a function may be a thunk (a deferred expression)

No comments:

Post a Comment