Topic
V CS 154: Intro. to Functional Programming—Midterm Review Notes
V Important note!
* click on the triangles to the left to expand sections!
* 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 Monday 25 October at the usual lecture time (1:50-2:50) in the usual lecture room (Ford 204).
V The exam will consist of several kinds of questions; typically:
* 10-15 True-or-False questions "warm-up" questions at 1-2 points each
* 8-10 short answer questions at 4-6 points each
* 3-4 longer answer questions at 8-15 points each
* The emphasis is more on conceptual issues than is typical in labs (which emphasize programming practice).
* In any case, you won't be asked to write long programs, but perhaps to read or complete shorter-length ones (2-4 lines of Haskell).
* You might also be asked to find certain kinds of errors in a program you read.
* You should review your lecture notes to study, as well as the textbook (chapters and sections as marked below).
* You might also want to review the labs and your solutions to them, as well as various samples on the class web page.
* Any definitions you need from the Prelude will be supplied for you in an "appendix" to the exam!
V Functional programming—background (see Preface and Chapter 1)
V programming compared with math
* like math, programming involves definition, calculation, abstraction and formal reasoning
* in both fields, ideas are in some sense exact, rigorous and objective
* both tend to be seen (superficially) as concerned with numbers and operations on them
* ... but both are actually (more deeply) concerned with larger-scale structures, their properties and relationships
V programming contrasted with math
V math is communicated between humans, and so may be somewhat informal;
* in addition, programs are also communicated to computers, and so must be expressed precisely, in formal languages
V in math, abstract properties and "values" are considered most important;
* in programming, we must consider concrete representations as well, for feasibility and efficiency
V some typical topics treated differently in math and programming:
* numbers are usually treated abstractly in math, divorced from their numeral representations: in computing we consider both
* sets form the foundation of math: as abstractions, they have only logical properties (which elements?)
* lists are representations in computing, so they naturally involve order and repetition of elements
* we also want sets in computing, but must explicitly abstract away from representational issues (e.g., the order and repetition)
V how does pure functional programming in Haskell compare to other approaches and languages?
V most languages express programs as sequences of stepwise instructions which change stored data over time;
* Haskell programs are sets of definitions concerning "timeless" values (much like math)
* Haskell programs use recursion where most languages "loop" instructions through time
V since Haskell values don't change over time, we can write algebraic or equational proofs about them
* (in most languages, we can't guarantee that f(x) = f(x) or that 2 * f(x) = f(x) + f(x), since x might change along the way!)
* Haskell programs tend to be much shorter than in most languages (hopefully without being too cryptic)
V most Haskell implementations allow an interactive, exploratory style of development, using an expression "calculator"
* most languages require a longer process of program compilation, and a greater separation of testing from writing phases
V The "mechanics" of using the Hugs (or WinHugs) implementations (see Chapter 2)
V basic interaction
* the Hugs (or WinHugs) program, by default, evaluates expressions that the user types in
* a basic module (i.e., a set of definitions called the Prelude is loaded by default (others can also be loaded)
* the expression $$ always refers to the last expression evaluated (and "up arrow" gives access to the history)
* if evaluation of an expression takes too long, it can be interrupted with the "stop button (or the "control-C" keystrokes)
V using commands
* a number of different commands to the interpreter can be given by prefixing with a colon (:)
* commands can be abbreviated to just their first letter (or to any unique prefix)
V some samples commands:
* :type to determine the type of an expression (short form :t)
* :load to a module of definitions (short form :l)
* :browse to show the names of defined values available
* :info to get information on things other than values (types, type classes, modules, etc.)
* :find to look up (in the editor) the definition of a value
* :set +s to show statistics about the time and storage used by each evaluation
* a number of other system options can be set either by using commands (:set) or through the WinHugs options menu
V writing and loading scripts
* we leave the interpreter and se an editor to write sets of definitions called modules
* inside a module, each definition must be complete (i.e., not interspersed with others)
* definitions may optionally include a type assertion (e.g., "f :: a -> [a]")
* definitions may involve sub-definition, using "where" clauses or the "let" expression: "let x = ... in ..."
* where clauses must be indented under their main clause
* if there is an error in a module, none of the definitions will load (it's all or nothing ...)
V Basic types and literals: numbers, characters, and booleans (see Sections 3.1-3.2; and 3.9)
V kinds of numbers in Haskell
V Int — the type of "small" integers (must be greater than -231 and less than 231 - 1)
* examples: 0, 1, -3, 1000
* can use base 16 with a "0x" prefix: 0x101 = 257
* represented internally using bit fields of with 32 (one bit for the sign)
* Integer — may be positive or negative and of any magnitude (but they are less efficient)
V Float, Double — approximations to real numbers, in "scientific notation", with size limitations
* examples: 2.5, -36.7, 3.141592635, 2.0E25, -37.456e-20 == -3.7456e-19
* represented internally using bit fields for mantissa and exponent, plus signs (IEEE standard representation)
V Num a — a type class that includes all the numeric types (supports addition, multiplication, etc.)
* by default, Haskell will try to defer judgements about what specific Num class type a literal constant is
* various other type classes support natural operations on fractions, integral types (Int and Integer), etc.
V characters and strings
V individual letters, digits, punctuation, symbols are called characters and are written in single quotes
* examples: 'a', '%', '2'
* their common type is Char
* values of Char type are represented internally as bot patterns or numbers, using the ASCII code
V longer texts, called strings, are written with double-quote marks
* examples: "hello", "a", "123@ $5"
* these values are all of type String, which is really just an abbreviation for list of Char (i.e., type String = [Char])
* when possible, Hugs will write out lists of characters in this notation
* ... but you can input them as lists: ['a', 'b', 'c', 'd'] == "abcd")
V escape characters
* some characters are "written" as special sequences, starting with "\"
* examples include tabs, newline characters, and some other unprintable ones
* when these strings are printed (e.g., using putStr), they will appear as actual tabs, line separators, etc.)
V Booleans (= "truth values")
* there are only two truth values, True and False, of type Bool
* they are computed as the results of relational operators (<, ==, etc.) and can be combined with logical operators (&&, ||, etc.)
* booleans can also be used in conditional expressions: if <boolean expression> then ... else ...
V in many cases, computing boolean results using conditionals can be re-expressed more concisely
* (if E then True else False) is the same as E
* (if E then False else True) is the same as not E
V Applying functions and operators to their arguments (see Sections 3.5-3.6)
V syntax of function application
* see also the “chunking exercises” www—chunking.pdf
* functions apply by juxtaposition to their arguments (i.e., written to the left)
* unlike in math, no parentheses are necessary in general: f x rather than f(x)
* but, if the argument is itself a "structured" expression, then parentheses are needed: f (x+y)
* several arguments can be supplied one after the other, with parens when structured: g a b (x+y) 3
V in fact, application to "several arguments" really is successive application of function results
* g a b (x+y) 3 == (((g a) b) (x+y)) 3
V operators and infix application
* operators are names written using non-letter "symbols": + - * # @ <= ==>
* operators take two (successive) arguments and are written in between them: x+y , "abc" !! 2
* when we want to refer to an operator without using it, we put it in parentheses: foldr (+)
* "normal" functions (of two arguments) can be used infix by wrapping them in "back ticks": x `f` y
* we can apply an operator to one or the other argument by wrapping the two in parentheses: (+3) (^2) ('a':)
V operators have a defined precedence and association, so that we can elide (leave out) some parentheses from complex expressions
* these rules generally follow the usual mathematical ones, so that, e.g., multiplication "precedes" addition
* function application always precedes infix operators: f x + g y == (f x) + (g y)
V some sample operators
* (+) — addition (or plus, or sum)
* (*) — multiplication (or product)
* (-) — subtraction (minus)
* (&&) — logical conjunction ("and")
* (||) — logical disjunction ("or")
* (<) — "less than" (relational: takes Ord class values, but returns a Bool)
* (>=) — "greater than or equal to" (relational)
* (==) — comparison for equality (relational over Eq class values)
* (/=) — comparison for inequality (negation of above)
* (!!) — indexing: selects an element from a list by numbered position, starting at 0
* (:) — "cons": builds a list from an element and the rest of the list (asymmetric)
* (++) — append: builds a list from two lists
V Pairs, tuples, Maybe values, etc. (see Sections 2.4 and 3.4)
V pairs and tuples
* pairs and n-tuples are written in parentheses, separated by commas: (2,3) ("abc", True, 5)
* the type of a pair is also written in the same way: (2,'a') :: (Int, Char)
* elements of pairs and tuples may be any type (unlike lists, whose elements must be all the same type)
* the functions fst and snd (first and second) may be used to select out the elements of a pair
V pairs of variables (or other patterns, see below) may be used as parameters in function definitions, or in definition of values
* f (x,y) = x^2 + y^2
* (left, right) = foo x y (here foo is presumed to be a function returning pairs)
V the unit type
* the unit type has just a single value; both are written as "empty" parentheses: () :: ()
* this type is useful when we need a "token" type with just one value (e.g., in the Notches example)
V the Maybe type
* the Maybe type has two kinds of values, Nothing and Just x, where x is some value
* the type "under" the Maybe is the type of the value if it's of the Just form: Just 3 : Maybe Int
V this type is useful when we want to allow, for example, that the result of a function is undefined
* lookup 2 [(1,"foo"), (3,"goo")] = Nothing
V List literals and Prelude functions (see Section 2.2, 3.3, the Appendix and also the labs)
V several different forms for writing lists
* [1,2,3] — this is the usual convenient form
* [] — the empty list (pronounced "nil")
* 1 : 2 : 3 : [] — this form makes the application of constructors explicit
* [1..10] — this form allows ranges of values to be easily specified
* [1..] — an infinite list, starting at 1
* [1,3..21] — an arithmetic progression (every odd number from 1 to 21)
V some handy Prelude functions on lists (see also the Appendix to the exam)
* head — the first element of a list
* tail — the rest of a list, after the first element
* init — all but the last element of a list, as a list
* last — the last element of a list, as a single element
* length — the length of a list (number of elements)
* reverse — a list with elements in the opposite order (last is first, first is last)
* filter — a list with only those elements matching some predicate
* take — the first n elements of a list, as a list (taking "too many" just returns those available)
* drop — the remaining elements, after n are dropped (dropping too many just returns nil)
* map — apply a function to every element of a list, returning a list of results
* remember, when we apply a function to a list, and get another list as a result, the original list does not change
V the wonderful! fold(r) function
* foldr :: (a -> b -> b) -> b -> [a] -> b
* foldr takes a function and a “final value” and folds up a list using the function
* foldr “replaces” all the cons operators (:) with the function and the nil list ( [] ) with the final value
* sum = foldr (+) 0
* product = foldr (*) 1
* foldr (:) [] is just the identity function on lists (replace cons with cons, and nil with nil)
V a picture of the internal structure of lists:
*
list structure
list structure

V Higher-order functions (see Sections 3.5-3.6 and Chapter 7)
* functions which take other functions as arguments, or return other functions as results, are called higher-order
V higher-order functions allow us to generalize many useful patterns of programming
* filter, takeWhile, dropWhile: allow a predicate to choose elements from a list
* map: allows a function to be applied to all elements of a list
* (.): function composition, combines functions in a "pipeline"
* curry, uncurry: convert between successive arguments and arguments-as-pairs
* foldr, foldl: allow functions to be applied "between" list elements
V functions of several "successive" arguments are actually higher-order functions (of their first argument) which return functions (of their second argument)
* f x y z == (((f x) y) z)
V a function which returns a boolean result (a -> Bool) is called a predicate
* filter even [1..10] == [2,4,6,8,10]
* takeWhile (<5) [1..10] == [1,2,3,4]
* see also below regarding the types of higher-order functions
V Defining functions (and other values) in Haskell (see Chapter 4)
V in general, Haskell definitions involve giving a name to a value, by writing the name and an expression describing the value, on the left- and right-hand sides of an 'equals sign', respectively
* x = 10
* foo = "abc" ++ "def"
V functions may de defined outright by using an expression which results in a function on the right-hand side
* h = f . g
* square = (^2)
V functions may also be defined relative to some parameter variable, which may then be used in the expression
* dub x = x * 2
V when a function is applied to an actual argument, the argument is substituted for the parameter in the defining expression
* dub (3*y-7) ==> (3*y-7) * 2
V functions may also be defined by cases, using patterns
* length [] = 0
* length (x:xs) = 1 + length xs
V patterns are matched against the structure of actual arguments in order of the definition, from top to bottom
* be careful: this means that a pattern might be redundant and never used!
V a special parameter or pattern, written with the underscore, matches any value (like a variable), but binds no name
* this can be used to emphasize that a definition is completely independent of the corresponding argument value
V variables in Haskell have a natural scope of definition:
* variables defined at the "top level" of a module (far left side) are available in the whole module (or when loaded)
* variable used in the (patterns of) function parameters are available only in that clause of the function definition
* variables defined in a "where clause" are available only in the dominating or outer definition
* variables defined in a let expression are available only in the expression after the let
V variables from an outer scope may be "shadowed" or over-ridden by an inner cope definition
* x = 3
f x = x + 2
f y = g x y
where x = 18
* here there are three different definitions of the variable x
V Programming strategies (see also Section 6.6)
V try defining a function by using Prelude functions or previously-defined as “helpers”
* count p xs = length (filter p xs)
* while p = until (not . p)
V try defining a function over lists using patterns and recursion; for starters, use a recursive call on the tail of the list
* f [] = ...
V f (x:xs) = ... x ... (f xs) ...
* don’t try to thin about the “how” of the recursive call, only the “what”
* think in terms of a “contract”: what should it give for the recursive result?
V try defining a function you want by translating it into terms you can work in, then translating back
(this will usually involve a function and its inverse)
* title = unwords . map cap . words
*
“round the block” diagram
“round the block” diagram

V Recursive definitions (see Chapter 6)
* definitions are recursive when the name being defined is used in the right-hand side of the definition
V recursive definitions run the risk of being ill-defined
* consider: x = x
* consider: f x = 1 + f x
* consider: f x = f (f x)
* always consider including a "base case" (a non-recursive clause) and ensure that recursive clause(s) make progress
V for lists, we often use nil for a base case and a simple head/tail pattern for the recursive clause
* f [] = ...
* f (x:xs) = ... (f xs) ...
* for natural numbers (non-negative integers), we can use a similar structure with 0 and (n+1)
* for functions of two arguments, consider using all combinations of structural patterns (sometimes this isn't necessary)
V sometimes "deeper" patterns might be necessary, e,g, in order to pick out a pair of values from a list of pairs, or several values at the front of a list
* f ((x,y):ps) = ...
* f (x:y:z:xs) = ...
V Evaluation, convergence, lazy evaluation and infinite data structures
* Haskell evaluation mimics paper-and-pencil algebraic or equational calculation (see the Lab 1 written exercises
* given an expression, we replace defined names with their definitions, being careful to respect rules of scope
* it is possible that the process of evaluation does not converge or terminate
* technically, Haskell implementations alway try to resolve the leftmost/outermost function definition first: this guarantees termination when possible
V Haskell implementations never evaluate more than they absolutely have to in order to, e.g., print results or supply arguments to primitive functions (like addition and multiplication)
* this means that we can define infinite structures, and use them, as long as we don't try to use all of them
* take 7 [1,3..] == [1,3,5,7,9,11,13]
V consider these definitions of the Fibonacci numbers and the factorials as lists:
* fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
* facs = 1 : zipWith (*) facs [1..]
V Types and type-checking (see Chapter 3)
* all Haskell values have a type, and all valid Haskell expressions (and definitions) must be well-typed
V we express the fact that an expression has a certain type by placing a double-colon between them
* 3 :: Int
* 'a' :: Char
* length :: [a] -> Int
* types help "sort out" values and prevent expressions that don't make sense (e.g., applying a number as if it were a function, or multiplying a String by a number)
* if a module contains an expression which cannot be given a valid type, it will not load and you cannot use its definitions (until you correct the error)
* among the rules are, for example, that if a function has type X -> Y, then its argument must have type X, and the result will be of type Y
* Haskell includes type variables (like "a" or "b") when any type is possible; this is called type polymorphism
V as mentioned above, higher-order function types can be read in two ways:
* map :: (a -> b) -> [a] -> [b] read as "map takes two arguments, a function and a list, and returns a list"
* map :: (a -> b) -> ([a] -> [b]) read as "map takes a function and returns, a function from lists to lists"
* these two types are equivalent, but writing the parentheses in explicitly emphasizes the second reading