

CS 154: Intro. to Functional Programming—Midterm Review Notes




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!




Information about the exam




The exam will be held on Monday 25 October at the usual lecture time (1:502:50) in the usual lecture room (Ford 204).




The exam will consist of several kinds of questions; typically:




1015 TrueorFalse questions "warmup" questions at 12 points each




810 short answer questions at 46 points each




34 longer answer questions at 815 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 shorterlength ones (24 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!




Functional programming—background (see Preface and Chapter 1)




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 largerscale structures, their properties and relationships




programming contrasted with math




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




in math, abstract properties and "values" are considered most important;




in programming, we must consider concrete representations as well, for feasibility and efficiency




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)




how does pure functional programming in Haskell compare to other approaches and languages?




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




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)




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




The "mechanics" of using the Hugs (or WinHugs) implementations (see Chapter 2)




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 "controlC" keystrokes)




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)




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




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 subdefinition, 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 ...)




Basic types and literals: numbers, characters, and booleans (see Sections 3.13.2; and 3.9)




kinds of numbers in Haskell




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)




Float, Double — approximations to real numbers, in "scientific notation", with size limitations




examples: 2.5, 36.7, 3.141592635, 2.0E25, 37.456e20 == 3.7456e19




represented internally using bit fields for mantissa and exponent, plus signs (IEEE standard representation)




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.




characters and strings




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




longer texts, called strings, are written with doublequote 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")




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.)




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 ...




in many cases, computing boolean results using conditionals can be reexpressed 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




Applying functions and operators to their arguments (see Sections 3.53.6)




syntax of function application




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




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




operators and infix application




operators are names written using nonletter "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':)




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)




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




Pairs, tuples, Maybe values, etc. (see Sections 2.4 and 3.4)




pairs and tuples




pairs and ntuples 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




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)




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)




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




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




List literals and Prelude functions (see Section 2.2, 3.3, the Appendix and also the labs)




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)




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




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)




a picture of the internal structure of lists:




list structure





Higherorder functions (see Sections 3.53.6 and Chapter 7)




functions which take other functions as arguments, or return other functions as results, are called higherorder




higherorder 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 argumentsaspairs




foldr, foldl: allow functions to be applied "between" list elements




functions of several "successive" arguments are actually higherorder functions (of their first argument) which return functions (of their second argument)




f x y z == (((f x) y) z)




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 higherorder functions




Defining functions (and other values) in Haskell (see Chapter 4)




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 righthand sides of an 'equals sign', respectively




x = 10




foo = "abc" ++ "def"




functions may de defined outright by using an expression which results in a function on the righthand side




h = f . g




square = (^2)




functions may also be defined relative to some parameter variable, which may then be used in the expression




dub x = x * 2




when a function is applied to an actual argument, the argument is substituted for the parameter in the defining expression




dub (3*y7) ==> (3*y7) * 2




functions may also be defined by cases, using patterns




length [] = 0




length (x:xs) = 1 + length xs




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!




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




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




variables from an outer scope may be "shadowed" or overridden 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




Programming strategies (see also Section 6.6)




try defining a function by using Prelude functions or previouslydefined as “helpers”




count p xs = length (filter p xs)




while p = until (not . p)




try defining a function over lists using patterns and recursion; for starters, use a recursive call on the tail of the list




f [] = ...




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?




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)




Recursive definitions (see Chapter 6)




definitions are recursive when the name being defined is used in the righthand side of the definition




recursive definitions run the risk of being illdefined




consider: x = x




consider: f x = 1 + f x




consider: f x = f (f x)




always consider including a "base case" (a nonrecursive clause) and ensure that recursive clause(s) make progress




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 (nonnegative 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)




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) = ...




Evaluation, convergence, lazy evaluation and infinite data structures




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




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]




consider these definitions of the Fibonacci numbers and the factorials as lists:




fibs = 0 : 1 : zipWith (+) fibs (tail fibs)




facs = 1 : zipWith (*) facs [1..]




Types and typechecking (see Chapter 3)




all Haskell values have a type, and all valid Haskell expressions (and definitions) must be welltyped




we express the fact that an expression has a certain type by placing a doublecolon 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




as mentioned above, higherorder 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


