Transcript Chapter 11 - Functional Programming, Part II: ML, Delayed

Chapter 11 - Functional
Programming, Part II: ML,
Delayed Evaluation, and Haskell
Programming Languages:
Principles and Practice, 2nd Ed.
Kenneth C. Louden
© Kenneth C. Louden, 2003
1
Beyond Scheme




Static typing: Scheme does strong type checking
of values -- but only at execution time. Thus,
programs must be almost entirely debugged
during execution.
Delayed evaluation: Scheme's evaluation rule is
standard, which Scheme's built-in functions often
deviate from. To get other evaluation orders,
there is a significant programming overhead.
ML has strong static Hindley-Milner type
checking (Chapter 6).
Haskell is purely functional and has delayed
evaluation, which takes advantage of purity.
Haskell also has overloading, which Scheme &
ML do not.
Chapter 11 - Part II
K. Louden, Programming Languages
2
ML ("MetaLanguage")

Dates from 1978, with a new standard in
1997. Invented by Robin Milner (UK). Very
popular in Europe.
 Standard translator is Standard ML of New
Jersey (Princeton & BellLabs). A popular
variant is CAML ("Categorical Abstract
Machine Language").
 All definitions and expressions are type
checked prior to execution.
 Otherwise very similar to Scheme, but
with a more C-like (or Ada-like) syntax.
Chapter 11 - Part II
K. Louden, Programming Languages
3
Sample ML Code
> fun fact n =
if n = 0 then 1 else n * fact(n-1);
val fact = fn: int -> int
> val Pi = 3.14159;
NOT multiplication
val Pi = 3.14159 : real
(see slide 13)
> 2 :: [3,4];
val it = [2,3,4] : int list
> (1,2,3.1);
val it = (1,2,3.1) : int * int * real
> fun append([],L) = L
| append(h::t,L) = h::append(t,L);
val append = fn : 'a list * 'a list -> 'a
list
Chapter 11 - Part II
K. Louden, Programming Languages
4
Notes about Sample ML Code

Each piece of code is followed by the interpreter
response as if entered directly (SML-NJ).

Arithmetic is infix, not prefix as in Scheme.

All expressions are statically typed (next slide).
There are two basic kinds of declarations, fun and
val (like the two kinds of defines in Scheme).


Lists are written using square brackets and
commas, with :: as the cons operator.

ML also has built-in tuples (Cartesian products),
written with commas and parentheses.

Functions can be defined using patterns (slide 11).
Chapter 11 - Part II
K. Louden, Programming Languages
5
Overview of static typing in ML

For more, see Chapter 6.

Historically, functional programmers resisted static
typing because they hated having to define the type
of every variable and function.

But static typing is clearly a good thing from a
software engineering perspective.

Hindley (a mathematician) showed already in 1969
how a translator could infer most types, but
computer scientists mostly ignored him.

Milner rediscovered Hindley's algorithm in 1978 and
applied it to ML ("MetaLanguage").
Chapter 11 - Part II
K. Louden, Programming Languages
6
Type checking in ML

Say we have a function definition in ML (slide 4):
fun fact n =
if n = 0 then 1 else n * fact(n-1);

ML has an easy time inferring its type:
val fact = fn : int -> int
It does so by assigning type variables 'a, 'b, etc. to
the identifiers and then uses the definition to infer
special information about those types: n = 0 shows
that n must have int type (comparison to an int).


The inferred types are as general as possible, so can
themselves contain type variables (i.e. are
polymorphic):
> fun id x = x;
val id = fn : 'a -> 'a
Chapter 11 - Part II
K. Louden, Programming Languages
7
Type checking in ML (2)

Type checking places some strong restrictions on
data, as noted in the following points.
 Lists have to be all of the same type (like arrays):
> [1,2,3.1];
Error: operator and operand don't agree
[literal]
operator domain: int * int list
operand:
int * real list
in expression:
2 :: 3.1 :: nil
 Lists and tuples cannot model recursive structures,
so user-defined types that can be recursive must be
introduced.
Chapter 11 - Part II
K. Louden, Programming Languages
8
Type checking in ML (3)

Hindley-Milner type checking usually requires no
type information, but sometimes it needs a type to
resolve an ambiguity:
> []@[]; (* @ is the append operation *)
stdIn:20.1-20.8 Warning: type vars not
generalized because of
value restriction are instantiated to
dummy types (X1,X2,...)
val it = [] : ?.X1 list
> ([]:int list)@[];
val it = [] : int list
Chapter 11 - Part II
K. Louden, Programming Languages
9
Type checking in ML (4)

ML also has a built-in prejudice towards integer
types in ambiguous arithmetic cases:
> fun square x = x * x;
val square = fn : int -> int

Thus, if we want a square function, say, on floating
point values, we must include a type:
> fun squaref (x:real) = x * x;
val squaref = fn : real -> real

Nevertheless, in most cases, Hindley-Milner type
checking removes the burden of specifying types.
Note also that ML's type system does not accept
overloading: if we want a square function for both
ints and reals we must use two different names.

Chapter 11 - Part II
K. Louden, Programming Languages
10
Equality types in ML


ML makes a strong distinction between ordinary
types and types for which the equality test (the =
operator) can be applied to values.
The = operator, unlike Scheme, is a general
equality test; however, it cannot be used on
functions or even real numbers:
> 2 = 2;
val it = true : bool
> map = map;
... Error: operator and operand don't
agree [equality type required]
> 2.0 = 2.0;
... Error: operator and operand don't
agree [equality type required]
Chapter 11 - Part II
K. Louden, Programming Languages
11
Equality types in ML (2)



Polymorphic type variables that must range over
equality types use two quotes instead of a single
quote:
> op =;
val it = fn : ''a * ''a -> bool
Anytime the = operator is used in code, the types
get restricted to the equality types:
> fun funny x = if x = x then x else x;
val funny = fn : ''a -> ''a
Make sure when writing code that you avoid using
= unless you really need it:
> fun empty L = if L = [] (* wrong! *)
then true else false;
val empty = fn : ''a list -> bool
Chapter 11 - Part II
K. Louden, Programming Languages
12
Pattern matching in ML

Hindley-Milner type checking relies on pattern
matching to infer types.
 Pattern matching is also available to programmers,
so we can define functions on lists by using the
patterns [] (empty) and h::t (a list with head h
and tail t) -- the definition of append on slide 4 is
an example (equivalent to built-in @ function).
 Patterns can also be used for numbers and tuples,
and the underscore _ can be used to match
anything anonymously:
fun fact 0 = 1 | fact n = n*fact(n-1);
fun first (x,_) = x;
 Because of patterns, head and tail functions (hd &
tl in ML) are used much less than in Scheme.
Chapter 11 - Part II
K. Louden, Programming Languages
13
Pattern matching in ML (cont.)

The use of pattern matching and the vertical bar
in a function definition is just syntactic sugar for
a case expression:
fun fact 0 = 1 | fact n = n*fact(n-1);
is the same as
fun fact n =
case n of
0 => 1 |
_ => n * fact(n-1);

Non-exhaustive patterns result in a warning:
> fun hd (h::_) = h;
... Warning: match nonexhaustive
h :: _ => ...
val hd = fn : 'a list -> 'a
Chapter 11 - Part II
K. Louden, Programming Languages
14
Data structures in ML

ML has user-defined types, of two kinds.
 Type synonyms -- just another name for an
existing type:
Asterisk means
> type Coords = real * real; "tuple" in a type
type Coords = real * real
> (2.1,3.2):Coords;
val it = (2.1,3.2) : Coords
Constructors - create
 New types:
values of the type
datatype Direction
= North | East | South | West;

Either kind can be polymorphic:
type 'a Pair = 'a * 'a;
Chapter 11 - Part II
K. Louden, Programming Languages
15
Data structures in ML (cont.)

Constructor parameter
A polymorphic binary search tree:
(only one in ML)
datatype 'a BST = Nil
| Node of 'a  'a BST  'a BST;

A traversal function that uses pattern matching:
fun tree_to_list Nil = []
| tree_to_list(Node(d,l,r)) =
(tree_to_list l)@[d]@(tree_to_list r);

The type of this function is fn:'a BST -> 'a list

Here is a use:
val t =
Node("dog",Node("cat",Nil,Nil),Nil);
> tree_to_list t;
val it = ["cat","dog"] : string list
Chapter 11 - Part II
K. Louden, Programming Languages
16
Higher-order functions in ML

Like Scheme, ML has function-valued
expressions (lambdas in Scheme), but with a
somewhat different syntax:
> fn x => x * x;
val it = fn : int -> int
> (fn x => x * x) 4;
val it = 16 : int
> map (fn x => x * x) [2,3,4];
val it = [4,9,16] : int list

A fun declaration is really just a val declaration:
> val square = fn x => x * x;
val square = fn : int -> int
Chapter 11 - Part II
K. Louden, Programming Languages
17
Higher-order functions (cont.)


Unlike Scheme, top-level val declarations are not
automatically recursive in ML:
> val fact = fn n => if n = 0 then 1
else n * fact (n-1);
stdIn:20.45-20.49 Error: unbound
variable or constructor: fact
> val rec fact = fn n => if n = 0 then
1 else n * fact (n-1);
val fact = fn : int -> int
Another example of a higher-order function:
> fun twice f x = f (f x);
val twice = fn : ('a -> 'a) -> 'a -> 'a
> twice square 3;
val it = 81 : int
Chapter 11 - Part II
K. Louden, Programming Languages
18
Curried Functions

Notice the ML type of the twice function:
('a -> 'a) -> 'a -> 'a
-- a function taking a function from 'a to 'a as a
parameter and returning a function from 'a to 'a
as a result. Or: a function taking two parameters,
one of type 'a -> 'a and a second of type 'a,
and returning a value of type 'a as a result.

So we could also write
> twice square;
val it = fn : int -> int

Moral: the twice function can take either one or
two parameters; if you give it one, it returns a
function of the (missing) 2nd parameter
Chapter 11 - Part II
K. Louden, Programming Languages
19
Curried Functions (2)

Contrast the previous definition of twice with a
definition using a tuple:
> fun twice2 (f,x) = f (f x);
val twice2 = fn : ('a -> 'a) * 'a -> 'a

Now we must always supply both parameters at
every call:
> twice2 square;
Error: operator and operand don't agree
[tycon mismatch] ...
> twice2 (square,3);
val it = 81 : int

The twice function is Curried (named after
Haskell B. Curry), the twice2 function is not.
Chapter 11 - Part II
K. Louden, Programming Languages
20
Curried Functions (3)

Definition: A function taking multiple parameters is
Curried if it can be viewed as a (higher-order)
function of a single parameter.

Currying is good, since all functions can be viewed
as having just a single parameter, and higher-order
functions can be obtained automatically.

In ML, all function definitions not using tuples
explicitly are automatically Curried. (In Scheme the
opposite is true.)

However, in ML all infix functions are implicitly not
Curried:
> op +;
val it = fn : int * int -> int
Chapter 11 - Part II
K. Louden, Programming Languages
21
Variables in ML

Like Scheme, ML is not purely functional, and ML
functions need not be referentially transparent.
 Unlike Scheme, variables in ML must be handled
differently from ordinary names; thus, nonfunctional constructs are more obvious.
 A variable has type t ref, where t is the type of
the value stored in it.
 ML uses := for assignment (like Ada), except that
the lhs must have type t ref and the rhs must
have type t.

To get the value out of a variable, you must
dereference it using the exclamation mark as a
(prefix) dereferencing operator.
Chapter 11 - Part II
K. Louden, Programming Languages
22
Variables in ML (cont.)

Here is sample code in ML, showing the use of a
variable, and a function inc that increments an
integer variable:
> val n = ref 2; (*must be initialized*)
val n = ref 2 : int ref
> fun inc x = x := !x + 1;
val inc = fn : int ref -> unit
> inc n;
Unit type is like void:
val it = () : unit
return value contains
> n;
val it = ref 3 : int ref no information.
> !n;
val it = 3 : int
Chapter 11 - Part II
K. Louden, Programming Languages
23
Sequencing and I/O in ML


Any group of expressions can be evaluated in
sequence by putting them inside a set of
parentheses and separating them by semicolons:
> (print "Hello ";print "World\n");
Hello World
val it = () : unit
Besides the print function there are many I/O
functions in the TextIO structure (like a Java
package):
> open TextIO; (* like Java import *)
... (* ML lists imports here *)
> fun echo () = let val s = inputLine
stdIn in output(TextIO.stdOut,s) end;
val echo = fn : unit -> unit
Chapter 11 - Part II
K. Louden, Programming Languages
24
Sequencing and I/O in ML (2)


We call the echo function by giving it the unit value:
> echo ();
now is the time
now is the time
val it = () : unit
String input can be converted to numbers using
various "fromString" functions, similar to "parse"
methods in Java:
> Real.fromString;
val it = fn : string -> real option
> Int.fromString "123";
val it = SOME 123 : int option
> Int.fromString "abc";
val it = NONE : int option
Chapter 11 - Part II
K. Louden, Programming Languages
25
Sequencing and I/O in ML (3)


Note in the fromString functions the use of an
option type to indicate that a conversion may fail:
> datatype 'a option = SOME of 'a | NONE;
Failure can also be represented in ML using
exceptions:
> exception SyntaxError;
exception SyntaxError;
> fun f x = if x <> 0 then x
else raise SyntaxError;
val f = fn : Int -> Int
> f 0 handle SyntaxError
=> (print "oops!\n";42);
oops!
val it = 42 : int
Chapter 11 - Part II
K. Louden, Programming Languages
26
Last example - a gcd test driver:
fun euclid () = (* from pages 501-502 of text *)
( output(stdOut, "Enter two integers:\n");
flushOut(stdOut);
let val u = Int.fromString(inputLine(stdIn));
val v = Int.fromString(inputLine(stdIn))
in
case (u,v) of
(SOME x, SOME y) =>
( output(stdOut,"The gcd of ");
output(stdOut,Int.toString(x));
output(stdOut," and ");
output(stdOut,Int.toString(y));
output(stdOut," is ");
output(stdOut,Int.toString(gcd(x,y)));
output(stdOut,"\n")
) |
_ => output(stdOut, "Bad input.\n")
end
)
Chapter 11 - Part II
K. Louden, Programming Languages
27
Delayed evaluation



ML and Scheme obey the standard "applicativeorder" evaluation rule (as do C and Java): all
parameters (arguments) are evaluated prior to the
execution of a call.
It is surprising how often we need a different rule:
(define (my-if a b c) (if a b c))
This definition can't work because both b and c
are evaluated before the call.
Scheme has manual facilities for delaying
evaluation of parameters:
(define (my-if a b c)
(if a (force b) (force c))
;; now the following code works:
(my-if #T (delay 1) (delay (/ 1 0)))
Chapter 11 - Part II
K. Louden, Programming Languages
28
Delay and force in Scheme

Delay creates a "promise" to evaluate an
expression, but doesn't evaluate it:
(delay (+ 3 4))
#<promise>

Force causes the "promise" to be fulfilled: the
expression is evaluated and the result returned
(but the promise is not turned into the value -- it
stays a promise):
> (define E (delay (+ 3 4)))
> (force E)
7
> E
#<promise>
Chapter 11 - Part II
K. Louden, Programming Languages
29
Uses of delayed evaluation

We can write "special forms" (functions not
obeying standard evaluation) directly in the
language.

Potentially unbounded data can be manipulated
without worrying about infinite loops:
(define (intlist m n)
(if (> m n) '()
(cons m (intlist (+ 1 m) n))))
But:
(define (ints-from m)
(cons m (delay (ints-from (+ m 1)))))
Chapter 11 - Part II
K. Louden, Programming Languages
30
Uses of delayed evaluation (cont.)

Now we can take as many integers from this
potentially infinite list as we want:
(define (take n L)
(if (= n 0) '()
(cons (car (force L))
(take (- n 1) (cdr (force L))))))
Then:
> (take 10 (delay (ints-from 1)))
(1 2 3 4 5 6 7 8 9 10)

Delayed lists are called streams, and they promote a
very effective programming technique called
generator-filter programming (see next slide).
Chapter 11 - Part II
K. Louden, Programming Languages
31
Generator-filter programming

A delayed filter function (see Chapter 11, Part I,
slide 30):
(define (d-filter p L)
Filters
(cond
((null? L) L)
Generator
((p (car (force L)))
(delay (cons (car (force L))
(d-filter p (cdr (force L))))))
(else (d-filter p (cdr (force L))))))

Now we can combine generators and filters:
> (take 20 (d-filter odd?
(delay (ints-from 1)))
(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
31 33 35 37 39)
Chapter 11 - Part II
K. Louden, Programming Languages
32
Memoization


Promises would be extremely inefficient, if they
evaluated their contained expressions every time
they are forced.
In fact, promises are memoized: the contained
expression is evaluated at most once, on the first
force; the value is then stored and used for all
subsequent forces, as shown in Scheme by
using take with the following rewrite of the
ints-from function of slide 24 (it only prints
each number once):
(define (ints-from n)
(display "computing ")
(display n)(newline)
(cons n (delay (ints-from (+ n 1)))))
Chapter 11 - Part II
K. Louden, Programming Languages
33
Lazy Evaluation

Built-in delayed evaluation with
memoization is called lazy evaluation
 It works well only with pure functional
programs, since the order of evaluation is
unpredictable (so all functions must be
referentially transparent).
Chapter 11 - Part II
K. Louden, Programming Languages
34
Properties of lazy evaluation

All arguments to user-defined functions are delayed.
 All bindings of local names in let and letrec
expressions are delayed.
 All arguments to constructor functions (such as
cons) are delayed.
 All arguments to other predefined functions, such
as the arithmetic functions "+," "*," and so on are
forced.
 All function-valued arguments are forced.
 All conditions in selection functions such as if and
cond are forced.
Chapter 11 - Part II
K. Louden, Programming Languages
35
Haskell

A fully-Curried lazy purely functional language
with Hindley-Milner static typing. (Fully-Curried
means all functions, including built-in arithmetic,
are implicitly Curried.)

Has many other features that make it perhaps the
most advanced functional language available
today.

Includes overloading and a built-in mechanism
for generator-filter programming (called list
comprensions -- see slide 36).
Chapter 11 - Part II
K. Louden, Programming Languages
36
Sample Haskell code:
fact n =
if n == 0 then 1 else n * fact (n-1)
square x = x * x
pi1 = 3.14159
gcd1 u v =
if v == 0 then u else gcd1 v (mod u v)
squarelist lis =
if (null lis) then lis
else square (head lis):
squarelist (tail lis)
Chapter 11 - Part II
K. Louden, Programming Languages
37
Haskell properties

Parentheses are only necessary for grouping.
 Semicolons are usually unnecessary (see slide 34).
 Definitions have no special syntax, so they must be
loaded from a file—they cannot be entered directly
into an interpreter.
 Operators are infix.
 Lists are written using square brackets and commas
(e.g. [1,2,3]), with ++ as the list append operation,
and : (colon) as the list constructor operation.


All value and function names must start with a
lowercase letter, and all types are uppercase: Int.
Names cannot be redefined, hence the use of pi1 &
gcd1 in the previous slide (pi & gcd are predefined).
Chapter 11 - Part II
K. Louden, Programming Languages
38
Haskell properties (2)

Haskell is purely functional, so there are no
variables or assignments, and I/O and sequencing
cannot be done except using special tools, called
monads (which we do not study here).

Of course, there are still local definitions:
let x = 2; y = 3 in x + y
or: let x = 2
y = 3 in x + y

Note indentation in the previous code to get rid of
the semicolon: Haskell uses a two-dimensional
Layout Rule to remove extra syntax. Leading white
space matters!
Chapter 11 - Part II
K. Louden, Programming Languages
39
Haskell properties (3)


Note lambda
syntax
All local definitions are recursive:
f x =
let z = x-1
g = \y->if y==0 then z else g(y-1)
in g x + 2
Comment
All expressions are delayed in Haskell:
ones = 1:ones -- can also write [1,1..]
ints_from n = n : ints_from (n+1)
ints = ints_from 1 -- also: [1..]

Infix operators can be made prefix by putting
parentheses around them:
double lis = map ((*) 2) lis
Chapter 11 - Part II
K. Louden, Programming Languages
40
Haskell properties (4)



Hindley-Milner type checking is performed on all
definitions and expressions. Type variables use the
names a, b, c, etc. (in contrast to ML, which uses
single quotes before the name).
Types are not automatically displayed as in ML, but
can be viewed by using the :t command in the
interpreter.
Small sample interpreter session:
> [1]++[2]
[1,2]
> :t (++)
(++) :: [a] -> [a] -> [a]
> [1]++['a']
ERROR - ...
Chapter 11 - Part II
K. Louden, Programming Languages
41
Patterns in Haskell




Patterns can be used in function definitions as in
ML, except that no vertical bar needs to separate
different patterns in a function definition (all
patterns must, however, be written together).
Typical patterns are 0 for zero, [] for the empty list,
and (x:xs) for a nonempty list.
fact and squarelist from slide 31 using patterns:
fact 0 = 1
fact n = n * fact (n-1)
squarelist [] = []
squarelist (x:xs) =
(square x) : squarelist xs
Of course, it would be better to use map:
squarelist lis = map square lis
Chapter 11 - Part II
K. Louden, Programming Languages
42
Patterns in Haskell (cont.)

Because of patterns, it is unusual in Haskell to use
head, tail, and null.

The anonymous wildcard pattern (matches
anything) is the underscore in Haskell as in ML.
Overlapping patterns are ok (see fact on previous
slide). Non-exhaustive patterns can also be used,
and do not generate a warning as in ML:
head1 (h:_) = h -- no warning message!
(Of course, the call head [] will still result in an
error.)
Patterns are syntactic sugar for case expressions:
fact n = case n of
0 -> 1
_ -> n * fact (n-1)


Chapter 11 - Part II
K. Louden, Programming Languages
43
Haskell List Comprehensions

Generators and filters can be expressed together in
Haskell in a quasi-list notation called a list
comprehension:
odds = [n | n <- ints, mod n 2 /= 0]
-- can also write [1,3..]

Multiple generators and filters can be combined in a
single list comprehension:
mystery =
[n+m|n <-ints, m <-ints, mod n m /= 0]

List comprehensions allow many snappy programs
to be written:
sieve (h:t)
= h:sieve [n|n <- t, mod n h /= 0]
primes = sieve [2..]
Chapter 11 - Part II
K. Louden, Programming Languages
44
Haskell Data Structures


So far we have only seen lists in Haskell,
although we know that static typing does not
allow lists to imitate structs or classes as in
Scheme.
Haskell has built-in tuple types (like ML), which
are Cartesian products (like structs but with no
field names):
intWithRoot:: Int -> (Int,Double)
intWithRoot x = (x , sqrt (fromInt x))

Use patterns to get the components out:
rootOf x = let (_,r)=intWithRoot x in r

Tuple types are written the same way values are,
(not like ML, which uses asterisks).
Chapter 11 - Part II
K. Louden, Programming Languages
45
Haskell Data Structures (2)




Lists and tuples do not go far enough, since unions
cannot be expressed.
User-defined types can be introduced using data
definitions:
data Direction = North|East|South|West
Very similar to ML datatype definition: the name on
the left of a data definition is the type name; the
names on the right are constructors representing
values.
Haskell can have polymorphic types and
constructors with more than one parameter (and
type variables are written after the type name, not
before as in ML):
data Either1 a b = Left1 a | Right1 b
Chapter 11 - Part II
K. Louden, Programming Languages
46
Haskell Data Structures (3)


Note how the previous definition expresses a
tagged union of two polymorphic types.
Binary search tree example (recursive type):
data BST a = Nil | Node a (BST a) (BST a)
simpleBST = Node "horse" Nil Nil -- value

Constructors can be used as patterns:
tree_to_list Nil = []
tree_to_list (Node val left right) =
(tree_to_list left) ++ [val]
++ (tree_to_list right)

Type synonyms can also be defined:
type IntDouble = (Int,Double)

Note: all type and constructor names must be
uppercase.
Chapter 11 - Part II
K. Louden, Programming Languages
47
Overloading in Haskell

Many functions in Haskell are overloaded, in that
they can take values from a (finite) number of
different types. An easy example is the square
function, defined by square x = x * x.
 The type of square in Haskell is:
square :: Num a => a -> a
 This says basically that square is defined for any
Num a type (such types all have a * function).
 The type Num a => a is called a qualified type,
and Num is called a type class.

Type classes are a bit like Java interfaces: they
require that a certain function be defined, and
each associated type must then implement it.
Chapter 11 - Part II
K. Louden, Programming Languages
48
Overloading in Haskell (2)

Here is an example of how to define a Sizeable
type class that provides a measure of the size of
a piece of data:
class Sizeable a where
size:: a -> Int

Now any type that you want to implement
Sizeable must be declared an instance of the
Sizeable class: (i.e., belongs to that class):
instance Sizeable [a] where
size = length
instance Sizeable (BST a) where
size Nil = 0
size (Node d l r) =
(size l)+(size r) + 1
Chapter 11 - Part II
K. Louden, Programming Languages
49
Overloading in Haskell (3)


Now any use of the size function automatically
adds the Sizeable qualification to a type:
trivial x = size x == 0
This function has type:
Sizeable a => a -> Bool
Type classes usually require multiple functions:
class Num a where
(+), (-), (*) :: a -> a -> a
negate
:: a -> a
abs
:: a -> a ...etc.
Built-in "hidden"
instance Num Int where
definitions
(+)
= primPlusInt
(-)
= primMinusInt
negate
= primNegInt ...etc.
Chapter 11 - Part II
K. Louden, Programming Languages
50
Overloading in Haskell (4)

Type classes may need to "inherit" functions
from other type classes (similar to interface
inheritance in Java):
class Eq a where
(==), (/=) :: a -> a -> Bool
x == y
= not (x/=y)
Note default
definitions
x /= y
= not (x==y)
class (Eq a) => Ord a where
(<),(<=),(>=),(>) :: a -> a -> Bool
max, min
:: a -> a -> a
instance Eq Int where …
instance Ord Int where ...
Chapter 11 - Part II
K. Louden, Programming Languages
51
Numeric Type Class Hierarchy
Eq
(==)
Ord
(<)
Num
(+,-,*)
Real
Integral
(div, mod)
Show
(show )
Fractional
(/)
RealFrac
(round, trunc)
Floating
(sin, cos)
RealFloat
Chapter 11 - Part II
K. Louden, Programming Languages
52
Overloading in Haskell (5)

The Show class allows a data type to be displayed
as a String (e.g. by the interpreter):
class Show a where
show
:: a -> String

So many data types need to be made instances of
Show and Eq that Haskell can do it automatically:
data BST a =
Nil | Node a (BST a) (BST a)
deriving (Show,Eq)

Overloading presents challenges for Hindley-Milner
type checking that result in some surprises:
squarelist = map square (compare to slide 36)
gives squarelist the type
[Integer] -> [Integer] (no overloading!)
Chapter 11 - Part II
K. Louden, Programming Languages
53