Important note!

click on the triangles to the left to expand sections!

use the text size feature in your browser to make this text larger and more readable!

Information about the exam

The exam will be held on Wednesday 18 March at the usual lecture time (1:50-2:50) in the usual lecture room (Collins 408).

The exam will consist of several kinds of questions; typically:

10-15 True-or-False questions "warm-up" questions at 1-2 points each

8-10 short answer questions at 4-6 points each

3-4 longer answer questions at 8-15 points each

The emphasis is more on conceptual issues than is typical in labs (which emphasize programming practice).

In any case, you won't be asked to write long programs, but perhaps to read or complete medium-length ones (2-4 lines of Haskell).

You might also be asked to find certain kinds of errors in a program you read.

You should review your lecture notes to study, as well as the textbook (chapters and sections as marked below).

You might also want to review the labs and your solutions to them, as well as various samples on the class web page.

Any definitions you need from the Prelude will be supplied for you in an "appendix" to the exam!

Functional programming—background (see Preface and Chapter 1)

programming compared with math

like math, programming involves definition, calculation, abstraction and formal reasoning

in both fields, ideas are in some sense exact, rigorous and objective

both tend to be seen (superficially) as concerned with numbers and operations on them

... but both are actually (more deeply) concerned with larger-scale structures, their properties and relationships

programming contrasted with math

math is communicated between humans, and so may be somewhat informal;

programs are also communicated to computers, and so must be expressed precisely, in formal languages

in math, abstract properties and "values" are considered most important;

in programming, we must consider concrete representations as well, for feasibility and efficiency

some typical topics treated differently in math and programming:

numbers in math are abstract, divorced from their numeral representations: in computing we consider both

sets form the foundation of math: as abstractions they have only logical properties

lists are representations in computing, so they naturally have order and repetition of elements

we also want sets in computing, but must explicitly abstract away from representational issues (e.g., order and repetition)

how does pure functional programming in Haskell compare to other approaches and languages?

most languages express programs as sequences of stepwise instructions which change stored data over time;

Haskell programs are sets of definitions concerning "timeless" values (much like math)

Haskell programs use recursion where most languages "loop" instructions through time

since Haskell values don't change over time, we can write algebraic or equational proofs about them

(in most languages, we can't guarantee that f(x) = f(x) or that 2 * f(x) = f(x) + f(x), since x might change along the way!)

Haskell programs tend to be much shorter than in most languages (hopefully without being too cryptic)

most Haskell implementations allow an interactive, exploratory style of development, using an expression "calculator"

most languages require a longer process of program compilation, and a greater separation of testing from writing phases

The "mechanics" of using the Hugs (or WinHugs) implementations (see Chapter 2)

basic interaction

the Hugs (or WinHugs) program by default evaluates expressions typed in

a basic module (= set of definitions), the Prelude, is loaded by default (others can also be loaded)

the expression $$ always refers to the last expression evaluated (and "up arrow" gives access to the history)

if evaluation of an expression takes too long, it can be interrupted with the "stop button (or control-C)

using commands

a number of different commands to the interpreter can be given by prefixing with a colon (:)

commands can be abbreviated to just their first letter (or a unique prefix)

some samples commands:

:type to determine the type of an expression

:load to a module of definitions

:browse to show the names of defined values available

:info to get information on things other than values (types, type classes, modules, etc.)

:find to look up (in the editor) the definition of a value

:set +s to show statistics about the time and storage used by each evaluation

a number of other system options can be set either by using commands (:set) or through the WinHugs options menu

writing and loading scripts

we leave the interpreter and se an editor to write sets of definitions called modules

inside a module, each definition must be complete (i.e., not interspersed with others)

definitions may optionally include a type assertion (e.g., "f :: a -> [a]")

definitions may involve sub-definition, using "where" clauses or the "let" expresion: "let x = ... in ..."

where clauses must be indented under their main clause

if there is an error in a module, none of the definitions will load (it's all or nothing ...)

Basic types and literals: numbers, characters, and booleans (see Sections 3.1-3.2; and 3.9)

kinds of numbers in Haskell

Int — the type of "small" integers (must be greater than -231 and less than 231 - 1)

examples: 0, 1, -3, 1000

can use base 16 with a "0x" prefix: 0x101 = 257

represented internally using bit fields of with 32 (one bit for the sign)

Integer — may be positive or negative and of any magnitude (but they are less efficient)

Float, Double — approximations to real numbers, in "scientific notation", with size limitations

examples: 2.5, -36.7, 3.141592635, 2.0E25, -37.456e-20 == -3.7456e-19

represented internally using bit fields for mantissa and exponent, plus signs (IEEE standard representation)

Num a — a type class that includes all the numeric types (supports addition, multiplication, etc.)

by default, Haskell will try to defer judgements about what specific Num class type a literal constant is

various other type classes support natural operations on fractions, integral types (Int and Integer), etc.

characters and strings

individual letters, digits, punctuation, symbols are called characters and are written in single quotes

examples: 'a', '%', '2'

their common type is Char

values of Char type are represented internally as bot patterns or numbers, using the ASCII code

longer texts, called strings, are written with double-quote marks

examples: "hello", "a", "123@ $5"

these values are all of type String, which is really just an abbreviation for list of Char (type String = [Char])

when possible, Hugs will write out lists of characters in this notation

... but you can input them as lists: ['a', 'b', 'c', 'd'] == "abcd")

escape characters

some characters are "written" as special sequences, starting with "\"

examples include tabs, newline characters, and some other unprintable ones

when these strings are printed (e.g., using putStr), they will appear as actual tabs, line separators, etc.)

Booleans (= "truth values")

there are only two truth values, True and False, of type Bool

they are computed as the results of relational operators (<, ==, etc.) and can be combined with logical operators (&&, ||, etc.)

booleans can also be used in conditional expressions: if <boolean expression> then ... else ...

in many cases, computing boolean results using conditionals can be re-expressed more concisely

(if E then True else False) is the same as E

(if E then False else True) is the same as not E

Applying functions and operators to their arguments (see Sections 3.5-3.6)

syntax of function application

functions apply by juxtaposition to their arguments (i.e., written to the left)

unlike in math, no parentheses are necessary in general: f x rather than f(x)

but, if the argument is itself a "structured" expression, then parentheses are needed: f (x+y)

several arguments can be supplied one after the other, with parens when structured: g a b (x+y) 3

in fact, application to "several arguments" really is successive application of function results

g a b (x+y) 3  ==  (((g a) b) (x+y)) 3

operators and infix application

operators are names written using non-letter "symbols": + - * # @ <= ==>

operators take two (successive) arguments and are written in between them: x+y , "abc" !! 2

when we want to refer to an operator without using it, we put it in parentheses: foldr (+)

"normal" functions (of two arguments) can be used infix by wrapping them in "back ticks": x `f` y

we can apply an operator to one or the other argument by wrapping the two in parentheses: (+3) (^2) ('a':)

operators have a defined precedence and association, so that we can elide some parentheses from complex expressions

these rules generally follow the usual mathematical ones, so that, e.g., multiplication "precedes" addition

function application always precedes infix operators: f x + g y == (f x) + (g y)

some sample operators

(+) — addition (or plus, or sum)

(*) — multiplication (or product)

(-) — subtraction (minus)

(&&) — logical conjunction ("and")

(||) — logical disjunction ("or")

(<) — "less than" (relational: takes Ord class values, but returns a Bool)

(>=) — "greater than or equal to" (relational)

(==) — comparison for equality (relational over Eq class values)

(/=) — comparison for inequality (negation of above)

(!!) — indexing: selects an element from a list by numbered position, starting at 0

(:) — "cons": builds a list from an element and the rest of the list (asymmetric)

(++) — append: builds a list from two lists

Pairs, tuples, Maybe values, etc. (see Sections 2.4 and 3.4)

pairs and tuples

pairs and n-tuples are written in parentheses, separated by commas: (2,3) ("abc", True, 5)

the type of a pair is also written in the same way: (2,'a') :: (Int, Char)

elements of pairs and tuples may be any type (unlike lists, whose elements must be all the same type)

the functions fst and snd (first and second) may be used to select out the elements of a pair

pairs of variables (or other patterns, see below) may be used as parameters in function definitions, or in definition of values

f (x,y) = x^2 + y^2

(left, right) = foo x y (here foo is presumed to be a function returning pairs)

the unit type

the unit type has just a single value; both are writtn as "empty" parentheses: () :: ()

this type is useful when we need a "token" type with just one value (e.g., in the Notches example)

the Maybe type

the Maybe type has two kinds of values, Nothing and Just x, where x is some value

the type "under" the Maybe is the type of the value if it's of the Just form: Just 3 : Maybe Int

this type is useful when we want to allow, for example, that the result of a function is undefined

lookup 2 [(1,"foo"), (3,"goo")] = Nothing

we also used this type to represent the "background" in functional pictures (really, figures)

the Ordering type

inside the definition of the various Boolean ordering relationals is a type with three values: LT, EQ, GT

these values allow for a three-way possible comparison: less, equal or greater

List literals and Prelude functions (see Section 2.2, 3.3, the Appendix and also the labs)

several different forms for writing lists

[1,2,3] — this is the usual convenient form

[] — the empty list (pronounced "nil")

1 : 2 : 3 : [] — this form makes the application of constructors explicit

[1..10] — this form allows ranges of values to be easily specified

[1..] — an infinite list, starting at 1

[1,3..21] — an arithmetic progression (every odd number from 1 to 21)

some handy Prelude functions on lists (see also the Appendix to the exam)

head — the first element of a list

tail — the rest of a list, after the first element

init — all but the last element of a list, as a list

last — the last element of a list, as a single element

length — the length of a list (number of elements)

reverse — a list with elements in the opposite order (last is first, first is last)

filter — a list with only those elements matching some predicate

take — the first n elements of a list, as a list (taking "too many" just returns those available)

drop — the remaining elements, after n are dropped (dropping too many just returns nil)

map — apply a function to every element of a list, returning a list of results

remember, when we apply a function to a list, and get another list as a result, the original list does not change

Higher-order functions (see Sections 3.5-3.6 and Chapter 7)

functions which take other functions as arguments, or return other functions as results, are called higher-order

higher-order functions allow us to generalize many useful patterns of programming

filter, takeWhile, dropWhile: allow a predicate to choose elements from a list

map: allows a function to be applied to all elements of a list

(.): function composition, combines functions in a "pipeline"

curry, uncurry: convert between successive arguments and arguments-as-pairs

foldr, foldl: allow functions to be applied "between" list elements

functions of several "successive" arguments are actually higher-order functions (of their first argument) which return functions (of their second argument)

f x y z  ==  (((f x) y) z)

see below re the types of higher-order functions

Defining functions (and other values) in Haskell (see Chapter 4)

in general, Haskell definitions involve giving a name to a value, by writing the name and an expression describing the value, on the left- and right-hand sides of an 'equals sign', respectively

x = 10

foo = "abc" ++ "def"

functions may de defined outright by using an expression which results in a function on the right-hand side

h = f . g

square = (^2)

functions may also be defined relative to some parameter variable, which may then be used in the expression

dub x = x * 2

when a function is applied to an actual argument, the argument is substituted for the parameter in the defining expression

dub (3*y-7)  ==>  (3*y-7) * 2

functions may also be defined by cases, using patterns

length [] = 0

length (x:xs) = 1 + length xs

patterns are matched against the structure of actual arguments in order of the definition, from top to bottom

be careful: this means that a pattern might be redundant and never used!

a special parameter or pattern, written with the underscore, matches any value (like a variable), but binds no name

this can be used to emphasize that a definition is completely independent of the corresponding argument value

variables in Haskell have a natural scope of definition:

variables defined at the "top level" of a module (far left side) are available in the whole module (or when loaded)

variable used in the (patterns of) function parameters are available only in that clause of the function definition

variables defined in a "where clause" are available only in the dominating or outer definition

variables defined in a let expression are available only in the expression after the let

variables from an outer scope may be "shadowed" or over-ridden by an inner cope definition

x = 3
f x = x + 2
f y = g x y
      where x = 18

here there are three different definitions of the variable x

Data types, constructors and patterns (see Sections 10.1-10.3)

new data types can be defined with the "data" definition form

data Color = Red | Green | Blue

data Nat = Zero | Succ Nat

data List a = Nil | Cons a (List a)

a data definition defines:

a new type, or type constructor, with an uppercase initial name, on the left-hand side

several alternative value constructors, with uppercase initial names, at the beginning of each right-hand side clause

the type constructor may take a type parameter (e.e., the element type of a list)

the value constructors may take arguments of the type specified (following their names)

once a new data type is defined:

we may refer to the type in type assertions (e.g., plus :: Nat -> Nat -> Nat)

we may use the value constructors to build values of the new type (e.g., two = Succ (Succ Zero))

value constructors are applied like functions, but are just "place-holders" which build structures from their arguments

pattern-matching on constructors is a kind of "destruction" or the inverse of construction

we may use the value constructors in patterns in order to define functions and other values "by example"

cool Red = False
cool Blue = True
cool Green = True

plus Zero m = m
plus (Succ n) m = Succ (plus n m)

a special clause at the end of a data definition may describe certain type classes to be derived automatically

available classes include Eq, Ord, Enum, Bounded, Show, and Read

Recursive definitions (see Chapter 6 and the Natty example file)

definitions are recursive when the name being defined is used in the right-hand side of the definition

recursive definitions run the risk of being ill-defined

consider: x = x

consider: f x = 1 + f x

consider: f x = f (f x)

always consider including a "base case" (a non-recursive clause) and ensure that recursive clauses make progress

for lists, we often use nil for a base case and a simple head/tail pattern for the recursive clause

f [] = ...

f (x:xs) = ... (f xs) ...

for natural numbers (non-negative integers), we can use a similar structure with 0 and (n+1)

for functions of two arguments, consider using all combinations of structural patterns (sometimes this isn't necessary)

sometimes "deeper" patterns might be necessary, e,g, in order to pick out a pair of values from a list of pairs, or several values att the front of a list

f ((x,y):ps) = ...

f (x:y:z:_) = ...

Evaluation, convergence, lazy evaluation and infinite data structures (see Sections 12.1-12.5)

Haskell evaluation mimics paper-and-pencil algebraic or equational calculation

given an expression, we replace defined names with their definitions, being careful to respect rules of scope

it is possible that the process of evaluation does not converge or terminate

technically, Haskell implementations alway try to resolve the leftmost/outermost function definition first: this guarantees termination when possible

Haskell implementations never evaluate more than they absolutely have to in order to, e.g., print results or supply arguments to primitive functions (like addition and multiplication)

this means that we can define infinite structures, and use them, as long as we don't try to use all of them

take 7 [1,3..] ==  [1,3,5,7,9,11,13]

Types and type-checking (see Chapter 3)

all Haskell values have a type, and all valid Haskell expressions (and definitions) must be well-typed

we express the fact that an expression has a certain type by placing a double-colon between them

3 :: Int

'a' :: Char

length :: [a] -> Int

types help "sort out" values and prevent expressions that don't make sense (e.g., applying a number as if it were a function, or multiplying a String by a number)

if a module contains an expression which cannot be given a valid type, it will not load and you cannot use its definitions (until you correct the error)

among the rules are, for example, that if a function has type X -> Y, then its argument must have type X, and the result will be of type Y

Haskell includes type variables (like "a" or "b") when any type is possible; this is called type polymorphism

as mentioned above, higher-order function types can be read in two ways:

map :: (a -> b) -> [a] -> [b] read as "map takes two arguments, a function and a list, and returns a list"

map :: (a -> b) -> ([a] -> [b]) read as "map takes a function and returns, a function from lists to lists"

these two types are equivalent, but writing the parentheses in explicitly emphasizes the second reading

List comprehensions (see Chapter 5 and the illustrated web page)

illustrated web page

list comprehension notation looks like the similar set notation from math: { x | P(x) } = the set of all x such that P(x) is true

in Haskell, list comprehension produces a list, not a set (order and repetition matter!)

the results all have the form of the first clause, on the left-hand-side of the vertical bar ("such that")

on the right-hand side of the bar are several clauses, of two possible kinds (separated by commas):

generators of the form pattern <- expression, where the expression results in a list of values to be matched against the pattern

guards of the form of boolean expressions

the rules are complex (see the illustrated web page), but basically:

candidate values are generated from left to right, as long as they "pass" the guards

for each generator, we match generated values against the pattern to bind variables

when a full set of candidates is available (all the way to the right-hand extreme), we evaluate the expression before the bar to generate one more result

therefore the values are generated in a way that runs like an odometer, with the right-hand generators cycling fastest

Defining and using type classes (see Section 10.6)

type classes allow us to generalize or abstract over a number of different types

a type class consists of a set of function (or value) names and their types

class Foo a where
  f :: a -> [a] -> (a,Int)
  g :: [a] -> a

any instance type must provide some actual functions (or values) that have the right types

instance Foo Char where
  f x xs = (...,...)
  g xs = ...

given a class definition, we can define functions and values using the names from the class

blah :: Foo a => a -> (a,Int)
blah x = f x (g [x,x])

any actual computation involving such class names must be in terms of some specific type (one which is an instance of the class)

type classes thus allow us to describe abstract "situations" involving types, and to work in terms of them

another way to think of type classes is that they allow us to overload names of common operators (such as (+) and (*), or (==))

the overloaded names can be used at several different types

the definitions of the corresponding functions may be completely different, and dependent on the type of values involved

Lambda notation (see Section 4.5)

lambda notation allows us to "define" functions anonymously, i.e., to express them without giving them an overt name

a lambda abstraction (or expression) includes:

a lambda (actually a backslash in Haskell): htis is just punctuation

one or more variables, as parameters to the function

an arrow (->), more punctuation

a "body" expression

the function expressed is one which when applied to an argument, has the same value as the body, when the parameter is given the argument's value

we can evaluate lambda expressions applied to their argument by substituting the actual argument into the body, eliminating the lambda (and parameter) as we go

(\x -> x+2) 7  ==  7+2

Sample application: a functional approach to graphics (see the RasterGraphics sample file)

we can represent pictures as functions from space to color

space can then be represented as, e.g., the real coordinate plane, or as a portion of an ASCII print screen

color can be represented in terms of integers (interpreted as color by a display) or as ASCII characters (trés retro!)

a picture is then "rendered" by applying it to all points in some space and displaying the results

we can identify several kinds of "picture functions":

simple, finite shapes, defined by describing them as functions (e.g., a circle or disc includes all points within the radius from the center)

generic patterns (e.g., stripes or checkerboard) which are infinite (e.g., colored red when sum of coordinates is even)

picture transformations (e.g., scaling or skewing), higher-order functions from pictures to pictures which effect some transform

there are some odd/non-intuitive things about transformations: to scale or translate (in space or time) we must invert the function!

e.g., to shift a picture up and to the left we actually add to the coordinates of the argument function (rather than subtract)