Topic
 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!
 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
 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