Important notes!

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 Friday 12 October at the usual lecture time (1:50-2:50) in the usual lecture room (Ford 204).

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 shorter-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;

in addition, 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 are usually treated abstractly in math, divorced from their numeral representations: in computing we consider both

sets form the foundation of math: as abstractions, they have only logical properties (which elements?)

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

we also want sets in computing, but must explicitly abstract away from representational issues (e.g., the 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 that the user types in

a basic module (i.e., a set of definitions called 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 the "control-C" keystrokes)

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 to any unique prefix)

some samples commands:

:type to determine the type of an expression (short form :t)

:load to a module of definitions (short form :l)

: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" expression: "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 (i.e., 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

see also the “chunking exercises” www—chunking.pdf

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 (leave out) 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 written 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

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

the wonderful! fold(r) function

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr takes a function and a “final value” and folds up a list using the function

foldr “replaces” all the cons operators (:) with the function and the nil list ( [] ) with the final value

sum = foldr (+) 0

product = foldr (*) 1

foldr (:) [] is just the identity function on lists (replace cons with cons, and nil with nil)

a picture of the internal structure of lists:

list structure

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)

a function which returns a boolean result (a -> Bool) is called a predicate

filter even [1..10] == [2,4,6,8,10]

takeWhile (<5) [1..10] == [1,2,3,4]

see also below regarding 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

Programming strategies (see also Section 6.6)

try defining a function by using Prelude functions or previously-defined as “helpers”

count p xs = length (filter p xs)

while p = until (not . p)

try defining a function over lists using patterns and recursion; for starters, use a recursive call on the tail of the list

f [] = ...

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

don’t try to think about the “how” of the recursive call, only the “what”

think in terms of a “contract”: what should it give for the recursive result?

try defining a function you want by translating it into terms you can work in, then translating back
(this will usually involve a function and its inverse)

title = unwords . map cap . words

 “round the block” diagram

try working with a specific, concrete example and abstracting from that

(abstract code: includes variables which might ultimately be function parameters)

concrete examples are in general easier to grasp than abstract code

concrete examples can be easily manipulated in a Haskell interpreter in order to explore possible solutions

you can use the “double triangle”  strategy & layout format to help develop code this way

Recursive definitions (see Chapter 6)

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 clause(s) 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 at the front of a list

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

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

Evaluation, convergence, lazy evaluation and infinite data structures

Haskell evaluation mimics paper-and-pencil algebraic or equational calculation (see the Lab 1 written exercises)

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]

consider these definitions of the Fibonacci numbers and the factorials as lists:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

facs = 1 : zipWith (*) facs [1..]

Types and type-checking (see Chapter 3)

see the sample typing diagram on the course home page

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