Important note!

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 Tuesday 14 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

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

Lazy evaluation and infinite data structures

Types and type-checking

A functional approach to graphics

Representing pictures as functions

pictures can be understood as functions from space to color

for us, space is indexed by 2-dimensional cartesian coordinates, either discrete or "real"

for us, color was either ASCII characters or natural numbers in a certain range (implicit RGB components)

Combinators 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 "charactertistic 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)

variations: 3-dimensional (or 1-dimensional)

variations: animations as functions from time to pictures

Haskore: a functional programming approach to music

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

we can manipulate them as structures, with functions

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

music values can be printed or played

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

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

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

Trees: binary and general

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 or using folds

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

Applications of trees: binary search trees

basic idea: node values are arranged by an ordering, everything to left is <, everything to right is >

allows finding items by node value in time proportional to height of tree (base 2 log, when bushy)

Folds: a program structuring mechanism

Capturing patterns of recursion

Folds "eliminate" structure using parameter functions

Sample functions written as folds

Unfolds transform a seed value into a structure (such as list or tree)

Proofs about programs

Theorems about programs are usually equations

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

Proof by induction

instantiate goal to several cases

assume goal is true for recursive parts as a local assumption toward proving larger goal