

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 about the exam




The exam will be held on Tuesday 14 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




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




Lazy evaluation and infinite data structures




Types and typechecking




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 2dimensional 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 (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 "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: 3dimensional (or 1dimensional)




variations: animations as functions from time to pictures




Haskore: a functional programming approach to music




musical values are abstract (roughly, a “treelike” 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 “finegrained” 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 highquality instrument samples




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




Trees: binary and general




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 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, levelorder




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 equations




Proofs may involve lemmas (useful subtheorems), 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


