Important note!

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

also, you can click the triangles to the left to hide or show outline levels

Information about the exam

The exam will be held on Saturday 15 December from 2-5pm in the usual lecture room (Ford 204).

The exam is scheduled for three hours, but you may well find that you finish early ...

The exam will be comprehensive (i.e., cover topics from the whole semester), but topics since the midterm will be covered more heavily

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

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

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

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

You won't be asked to write long programs, but perhaps to read and/or complete some medium-length ones (for Haskell, this means 2-4 lines).

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

The emphasis is more on conceptual issues than the labs usually are (labs emphasize practice programming).

You should review your lecture notes to study, as well as the textbook Chapters 1-5 (and parts of 6, 8 and 9).

Any definitions you need from the Prelude will be supplied and described for you.

See the midterm review for a summary of topics from the last exam (and especially chapter references there!)

Top-level topics repeated below; also see this link to the midterm review notes

Functional programming—background

The "mechanics" of using the Hugs

Basic types and literals (numbers, characters, and booleans)

Applying functions and operators to their arguments

Pairs, tuples, Maybe values, etc.

List literals and Prelude functions

Higher-order functions

Defining functions (and other values)

Programming strategies

Recursive definitions

Evaluation, convergence, lazy evaluation and infinite data structures

Types and type-checking

Trees: binary and general (see Section 10.3 of the textbook)

General definitions

a tree is a data structure that holds items, like a list does

… but a tree is not linear, rather it is hierarchical

trees as graphs

a graph is a more general structure with items in nodes and edges connecting them

a tree is a: rooted, directed, connected, acyclic graph without sharing

(rooted: there is a special "starting" node called the root)

(directed: the edges "go" in just one direction (from parent to child))

(connected: all the nodes are connected by some path from the root)

(acyclic: there are no edges that point "back" to a previous node)

(no sharing: no node is "shared" by two parents; every node has a unique parent)

many trees are also ordered, in that children are specifically left or right children

terminology: we use a lot of colloquial words in technical ways to talk about trees

parent & child, sibling, etc. (also ancestor, descendant, etc.) by analogy with family trees

leaves (also external nodes): the nodes at the "bottom" of the tree, with no children

internal nodes: nodes that aren't leaves

height (of a tree) or depth (of a node): integer value measuring length of path from root (to leaf in case of height)

path: sequence of edges from one node (often the root) to another

sub-tree: a tree that is part of a larger tree, thought of as a unit, "rooted" at its own top node

Types and uses of trees

general trees (also called rose trees; see below) have an arbitrary number of children at every node

binary trees have just zero, one or two children (and usually a node is specifically a left or right child)

binary search trees are binary trees where every item in the left sub-tree is less than the item in the root
(and every item in the right sub-tree is greater than the item in the root)

search trees are used to store & find items quickly, based on order

a typical search in a (hopefully bushy) BST can be done in time logarithmic in the number of items stored

trees are often used to represent hierarchies (of organizations, parts/whole, etc.)

trees are used to represent families in genealogy (but here there are two parents to a node!)

trees are often used to represent language (hierarchically structured phrases)

… but especially to represent logic, math & computer languages (logical formulae, arithmetic expressions, etc.)

Trees as non-linear, recursive data types

we have already seen examples of linear recursions in data types: natural numbers and lists

trees use a non-linear form of recursion: each "node" may have a pair (or a list) of children

data BTree a = Tip | BNode a (BTree a) (BTree a)

data Rose a = Branch a [Rose a]

functions on trees are usually defined by pattern-matching and recursion

See Lab 6 for examples!

Some basic operations on trees

"metrics" on trees which return numbers: size and height

traversals on trees returning lists of items: inorder, preorder, postorder, level-order

transformations returning new trees: map and mirror

Proofs about programs (see Chapter 13 of the textbook)

Theorems about programs are usually in the form of equations

for examples, see the on-line proof exercises and the sample proofs

Proofs may involve "lemmas" (useful sub-theorems), just as functions do

Proof by induction

in order to prove something about all possible values of a recursive type, we:

prove that the theorem is true for base cases (e.g., empty list, or tree Tip)

prove that truth (of the theorem) is preserved when going from sub-structures to larger structures

i.e., we assume the truth for sub-structures, then prove the truth for the whole

e.g., assume true for xs, prove for (x:xs)

A functional approach to graphics (see on-line references at home page)

Representing pictures as functions

pictures can be understood as functions from space to color

space can be indexed by 2-dimensional cartesian coordinates, either discrete or "real"

colors can be represented as natural numbers in a certain range (with implicit Red-Green-Blue components)

Combinators (functions) for picture composition

figures like circles and rectangles are not naturally functions on the whole space to colors

we represent them as functions to Maybe Color: the Nothing case allows for a "transparent background"

figures can then be composited together, like overlaying transparency slides

we can use a fold to extend pairwise overlays (non-commutative) to lists

a final background color (for the whole space) can be added at the end, to make a picture

Basic shapes and transformations

basic shapes like circles or rectangles can be defined via their "characteristic functions"
(i.e., where an equation about them is True or False)

transformations like shifting scaling are easy (add or multiply) but you must remember to invert them!!

more complex transformations just require more math (algebraic geometry); e.g., skewing, twisting, etc.

Other issues

aliasing (jaggies) and anti-aliasing (smoothing by over-sampling and then using mixed colors)

polar coordinates: these can be easily supported by supplying a conversion function

animations: these can be seen as functions from time to pictures

Haskore: a functional programming approach to music (see on-line references at home page)

musical values are abstract (roughly, a “tree-like” data structure)

we can represent musical values as tree-like structures built from notes

we can manipulate musical values using functions (including higher-order ones)

notes are basically combinations of pitch and duration (other atomic values include rests)

music values can be combined in series (i.e., one after the other in time) :+:

music values can be combined in parallel (i.e., at the same time, like a chord of notes) :=:

other features include instrumentation, tempo and various “fine-grained” annotations (dynamics, etc.)

music values can be played (or printed)

playing as sound involves conversion to formats for one of several standards for \

primary sound output standard is MIDI, which usually employs high-quality instrument samples

printing to musical scores is a (rather more complex) form of conversion to a String

complex patterns can be captured using (higher-order) functions

rhythms, chords, arpeggiation and other structures can be abstracted as functions

higher-order functions can be used to combine the basic “pattern functions” for even more complex structures

one might analyze patterns in pieces of music to infer and compare notions of musical style