V CS 254: Intro. to Functional Programming—Final Exam Review Notes
V Important note!
* use the text size feature in your browser to make this text larger and more readable!
V 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
V 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.
V 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
V Haskore: a functional programming approach to music
V 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
V 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
V 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
V Trees: binary and general
V Trees as non-linear, recursive data types
* we have already seen examples of linear recursions in data types: natural numbers and lists
V 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
V 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
V 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
> Proofs about programs