\n -> n + 1 -- the successor function succ = \n -> n + 1 -- bind "succ" to the successor function succ n = n + 1 -- sugar for above; similar to Self \a -> \b -> a + b -- the make-adder function (\a -> \b -> a + b) 1 -- another version of the successor function
(5, 'a', succ)
[1, 2, 3] 1:2:3: -- same thing, using explicit "cons" operator ':' and nil '' [1..3] -- also the same thing (Haskell is heavily sugared)
True :: Bool 'a' :: Char 5 :: Int succ :: Int -> Int [1,2,3] :: [Int] (5, 'a', succ) :: (Int, Char, Int -> Int)The arrow operator is used for functions. The
make_adderfunction would have type
Int -> Int -> Int, i.e. it takes an integer and returns a function from integer to integer. This is also the type of
add, a function that takes two integers and produces an integer. The reason is that multiple-argument functions are curried, to be explained below.
fact n = if (n == 0) then 1 else n * fact (n-1)We can ask what type this function has, and Haskell will reply
Int -> Int:
factsometimes returns 1, so its return type must be
duplicate x = (x, x)What is the type of
duplicate? Haskell says
a -> (a, a), where a is a universal quantifier. This is a type-function, just like Sather's parameterized types. The difference is that Haskell automatically fills in the type-argument by inspecting the argument to
duplicate. For example, these calls are both legal:
duplicate 1 duplicate ['a','b','c']
class Eq a where (==) :: a -> a -> Booldefines a type-class where every instance supports the equality operator '=='. The operator takes two arguments of the same type and returns a boolean. Type-classes can inherit from each other.
Instantiating a type-class means labeling an existing type,
Int, as belonging to that class, and providing
implementations of the class methods, e.g.
instance Eq Int where x == y = intEq x yWhere
intEqis a primitive for integer equality. Each instance can provide its own implementation of '=='; this is how we overload it.
Now we can declare polymorphic functions only over types which support equality:
duplicate :: (Eq a) => a -> (a, a) duplicate x = (x, x)Note that the type of
duplicatemust now be declared. Type classes are not inferred automatically.
a -> (a, a) was an untyped
type-function, that could take any type as argument,
(Eq a) => a
-> (a, a) is a typed type-function, whose arguments
are themselves typed (by type classes). Haskell's '=>' corresponds
using the '<' operator in Sather for restricting the parameters of
Haskell thus supports object-orientation based on traits. The data held by a value is defined by its type, but the operations on the value are defined by functions in an instance declaration (the traits). Furthermore, traits are themselves typed, by type-classes.
moduleconstruct for building a closed namespace, and an
interfaceconstruct for typing modules. No connection is drawn between this mechanism and type-classes, which are viewed as an overloading, not a naming, mechanism.
(define (make-linear-xform a) (lambda (b) (lambda (x) (+ (* a x) b)))) (((make-linear-xform 2) 3) 3) ; prints 9In Haskell, it looks normal:
linear-xform a b x = (a * x) + b linear-xform 2 3 3 -- prints 9 f = linear-xform 2 3 -- currying f 3 -- prints 9
Even operators, which are just infix functions, can be curried:
succ = (+1) succ 2 -- prints 3 double = (*2) double 3 -- prints 6
Currying prevents awkward Scheme constructions like
(f x y)) when you really just want to say
This is known as eta reduction (a term from the lambda
delayform in Scheme wraps an expression into a function (with no arguments) which is evaluated when needed by calling
force. As described in SICP, delayed evaluation is instrumental for streams and data-flow programming, and is a good alternative to explicit mutation in many programs. Here are some examples.
Like currying, delayed evaluation in Haskell is implicit. All
functions in Haskell execute before their arguments are fully
evaluated. This is known as non-strictness. In particular,
Haskell is lazy, meaning that it postpones argument
evaluation to the last possible moment: when the argument is used in
the function. This mirrors the semantics of
force. (In contrast, the Id language is non-strict but
eager: arguments evaluate in parallel with the function.)
const1 x = 1 -- function which always returns 1 const1 (1/0) -- prints 1; the division never happens ones = 1:ones -- infinite list of 1s -- ':' is just an infix function; it is lazy, too take 10 ones -- prints [1,1,1,1,1,1,1,1,1,1] -- "take n list" returns the first n elts of list
Thus non-strict languages use names in the style of commands, not tags
(as defined in the linguistics
lecture). A name is bound to an arbitrary computation, which is
executed when the name's value is needed (lazy evaluation) or
concurrently (eager evaluation). A name cannot be rebound to
something else; it "means" the result of that computation. For
example, in English we use the noun phrase "the list containing 1
followed by the contents of the same list" to denote what in Haskell
ones. Just as this noun phrase only means the
infinite list of ones (it makes no sense to "rebind" it), the
ones variable also cannot be rebound.
x, y = 1, 2 def sum_pair((a,b)): return a + b sum_pair((1,2)) # prints 3We can do the same in Haskell:
(x, y) = (1, 2) sum_pair (a,b) = a + b sum_pair (1,2) -- prints 3Haskell allows pattern matching with arbitrary nesting of tuples, lists, and user-defined data structures.
For example, by using argument patterns we can define several versions of a function, as long as they have the same type. Here are two implementations of list length:
len1 x = if (x == ) then 0 else (1 + len1 (tail x)) len2  = 0 len2 (h:t) = 1 + len2 tBoth have type
[a] -> Int. Which do you find more readable?
sign1 x = if (x < 0) then -1 else if (x == 0) then 0 else 1 sign2 x | x < 0 = -1 sign2 x | x == 0 = 0 sign2 x | x > 0 = 1 fact n | n == 0 = 1 fact n | n > 0 = n * fact (n-1)
Haskell even lets us make definitions like
fact 0 = 1 fact (n+1) = (n+1) * fact nwhich is just sugar for our original definition of
Computers can do a lot of things; sometimes what they do is well described as solving equations. However, traditional mathematics has no representations for I/O, naming environments, sequentiality, and time, which are all important in programming. No wonder languages based on math, such as Haskell, have poor support for these, much less any capability for reflection, i.e. representing how the language itself operates.
When evaluation has no side-effects, the evaluation process becomes easier to understand. Conceptually, the evaluator is just applying rewrite rules to the syntactical form of the expression. For example:
(fact n), textually replace it with
if (n == 0) then 1 else n * fact (n-1).
a == b, where a and b are values, replace it with
if True then x else y, replace it with
One advantage of functionalism, then, is that it is easier to reason about programs, and therefore make them more efficient. Remember, compilation is like decryption: it's not the possibility that counts, it's the work factor. Functional languages promise to have a smaller work factor for the most difficult optimizations. A good example is parallelism: when expressions cannot have side-effects then it is always safe to run them in parallel. In 6.847, you will learn about a (mostly) functional language called Id where programs run well on both sequential and massively parallel hardware. Declarative programming in general tends to make more things implicit, which puts a burden on the compiler but allows programs to automagically become more efficient as the compiler improves. Hence functional programs can have a longer life span.
Another possible advantage is the new programming style born by the restriction. Functional programming goes even further than static typing in making it hard to make errors. However, this is not strictly a linguistic issue; it is a matter of style. It's just that functional languages happen to be best at functional style, by supporting pattern matching and non-strictness, because they're forced to.