

CS 154: 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!




also, you can click the triangles to the left to hide or show outline levels




Information about the exam




The exam will be held on Monday 9 December from 25pm 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:




1015 TrueorFalse questions at 12 points each




810 short answer questions at 46 points each




24 longer answer questions at 815 points each




You won't be asked to write long programs, but perhaps to read and/or complete some mediumlength ones (for Haskell, this means 24 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 15 (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 (and especially chapter references there!)




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




Higherorder functions




Defining functions (and other values)




Programming strategies




Recursive definitions




Evaluation, convergence, lazy evaluation and infinite data structures




Types and typechecking




Trees: binary and general (see Section 10.3 of the textbook)




General definitions




a tree is a data structure that holds items, like a list does




… but a tree is not linear, rather it is hierarchical




trees as graphs




a graph is a more general structure with items in nodes and edges connecting them




a tree is a: rooted, directed, connected, acyclic graph without sharing




(rooted: there is a special "starting" node called the root)




(directed: the edges "go" in just one direction (from parent to child))




(connected: all the nodes are connected by some path from the root)




(acyclic: there are no edges that point "back" to a previous node)




(no sharing: no node is "shared" by two parents; every node has a unique parent)




many trees are also ordered, in that children are specifically left or right children




terminology: we use a lot of colloquial words in technical ways to talk about trees




parent & child, sibling, etc. (also ancestor, descendant, etc.) by analogy with family trees




leaves (also external nodes): the nodes at the "bottom" of the tree, with no children




internal nodes: nodes that aren't leaves




height (of a tree) or depth (of a node): integer value measuring length of path from root (to leaf in case of height)




path: sequence of edges from one node (often the root) to another




subtree: a tree that is part of a larger tree, thought of as a unit, "rooted" at its own top node




Types and uses of trees




general trees (also called rose trees; see below) have an arbitrary number of children at every node




binary trees have just zero, one or two children (and usually a node is specifically a left or right child)




binary search trees are binary trees where every item in the left subtree is less than the item in the root (and every item in the right subtree is greater than the item in the root)




search trees are used to store & find items quickly, based on order




a typical search in a (hopefully bushy) BST can be done in time logarithmic in the number of items stored




trees are often used to represent hierarchies (of organizations, parts/whole, etc.)




trees are used to represent families in genealogy (but here there are two parents to a node!)




trees are often used to represent language (hierarchically structured phrases)




… but especially to represent logic, math & computer languages (logical formulae, arithmetic expressions, etc.)




Trees as nonlinear, recursive data types




we have already seen examples of linear recursions in data types: natural numbers and lists




trees use a nonlinear 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 patternmatching and recursion




Some basic operations on trees




"metrics" on trees which return numbers: size and height




traversals on trees returning lists of items: inorder, preorder, postorder, levelorder




transformations returning new trees: map and mirror




Proofs about programs (see Chapter 13 of the textbook)




Theorems about programs are usually in the form of equations




Proofs may involve "lemmas" (useful subtheorems), just as functions do




Proof by induction




in order to prove something about all possible values of a recursive type, we:




prove that the theorem is true for base cases (e.g., empty list, or tree Tip)




prove that truth (of the theorem) is preserved when going from substructures to larger structures




i.e., we assume the truth for substructures, then prove the truth for the whole




e.g., assume true for xs, prove for (x:xs)




A functional approach to graphics (see online references at home page)




Representing pictures as functions




pictures can be understood as functions from space to color




space can be indexed by 2dimensional cartesian coordinates, either discrete or "real"




colors can be represented as natural numbers in a certain range (with implicit RedGreenBlue components)




Combinators (functions) 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 (noncommutative) 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 "characteristic 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) and antialiasing (smoothing by oversampling and then using mixed colors)




polar coordinates: these can be easily supported by supplying a conversion function




animations: these can be seen as functions from time to pictures




Haskore: a functional programming approach to music (see online references at home page)




musical values are abstract (roughly, a “treelike” data structure)




we can represent musical values as treelike structures built from notes




we can manipulate musical values using functions (including higherorder ones)




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 “finegrained” annotations (dynamics, etc.)




music values can be played (or printed)




playing as sound involves conversion to formats for one of several standards for \




primary sound output standard is MIDI, which usually employs highquality instrument samples




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




complex patterns can be captured using (higherorder) functions




rhythms, chords, arpeggiation and other structures can be abstracted as functions




higherorder 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


