|
|
CS 254: Intro. to Functional Programming—Final Exam Review Notes
|
|
|
|
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
|
|
|
|
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
|
|
|