Important note!

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

Information on the exam

The exam will be held on Monday 11 May from 2-5pm in the usual lecture room (Collins 408). 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

link to the midterm review notes

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

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 (universally-quantified) equations

Equations should be between well-typed terms of the same type

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

Algebraic languages: syntax and semantics

Abstract syntax of terms is like a tree (with binary operators for nodes)

Concrete syntax can be parsed from a string to a tree

Semantics is a fold over the tree, replacing operator symbols with functions

Monads: an abstract notion of sequencing

Monads are a type (constructor) class providing return and bind (>>=)

Monads provide for an abstract notion of sequencing operations

Some monads are containers (e.g., lists): sequencing involves flattening

Monad for state involves sequencing of access to a changing "background"

Games and interaction

Turn-based games are naturally programmed as interactive dialogues

Define data types capturing information implicit in a turn (player's choices)

Capture the "state of the game" as a Haskell value (e.g., matrix for waffle)

Print intermediate states for user to contemplate

Other uses: analyze boards, compute statistics, program computer to play

Web programming with Haskell

About HTML and web pages

Combinators for tagged markup

Structure of a sample web app

When to use Haskell for the web