TOPICS FOR THE COP 4020 EXAM on Advanced Functional Programming $Date: 2019/10/23 20:00:23 $ This exam covers topics from homework 3 (which assumes material from homework 2 and the first two problems of homework 1). It is thus especially about recursion over interesting grammars, and using higher-order functions to abstract from programming patterns and to model infinite data. It is related to all the course objectives but especially to [Concepts] and [UseModels]. REMINDERS The exam will be open book, open notes, but no electronics. If you need electronic material, print it and bring the printout. (Warning: don't expect to learn the material during the exam. A good idea for studying is to condense your notes to a few pages of ready reference materials. We suggest that you memorize the Haskell syntax you'll need.) If you need more space, use the back of a page. Note when you do that on the front. Before you begin, please take a moment to look over the entire test so that you can budget your time. Clarity is important; if your programs are sloppy and hard to read, you may lose some points. Correct syntax also makes a difference for programming questions. Take special care with indentation and capitalization in Haskell. When you write Haskell code on this test, you may use anything we have mentioned in class that is built-in to Haskell. But unless specifically directed, you should not use imperative features (such as the IO type) or the monadic syntax. You are encouraged to define helping functions whenever you wish. Note that if you use functions that are not in the standard Haskell Prelude, then you must write them into your test. (That is, your code may not import modules other than the Prelude.) HINTS If you use functions like filter, map, and foldr whenever possible, then you will have to write less code on the test, which will mean fewer chances for making mistakes and will leave you more time to be careful. In some problems the examples may be very extensive and take a long time to read if you read every detail. But the basic idea of the recursion is usually clear from the description, simple examples, and the "follow the grammar" idea of recursing everywhere possible. So you may want to look to the examples to confirm your understanding and not spend too much time reading examples after you understand the problem. READINGS We recommend reading the "Following the Grammar in Haskell" handout and chapters 10-14, and 16 of Simon Thompson's book "Haskell: the craft of functional programming." But you may wish to read a tutorial on Haskell or another online book instead of Thompson's book. You may also want to read a tutorial on Haskell or the Haskell Language Specification. If you have time, see the course web site, especially the code examples page, and also the course syllabus for other readings. TOPICS In the following, I use + to denote relatively more important topics, and - to denote relatively less important topics. Topics marked with ++ are almost certain to be on the exam. All of these are fair game, but if you have limited time, concentrate on the ones that are more important first (and in those, the ones you are most uncertain about). SKILLS [UseModels] + write functions that work on recursive grammars and that follow the grammar [HW3: height, split, simplify, freeQBExp] (Spring'13: iconify, freeQBExp; Fall13: preOrderNWay, scaleNWay) ++ write functions that work nested, recursive lists, tuples, or records [HW3: rate, filterInside] (Spring13: filterInside; Fall13: joinNames on lists of Address lists Fall13: joinNames; Spring15: sumLL) ++ use higher-order functions to implement other functions [HW3: use foldr to implement concatMap, use foldWindowPlan to implement height and split] (Spring13: use foldr to implement union, use map to implement applyList) (Fall13: use foldr to implement sumSquares and filter; Spring15: use foldr to implement frMap2) + write higher-order functions [HW3: toCharFun, fromCharFun, filterInside, composeFilters, foldWindowPlan] ++ use functions as data [HW3: composeFilters, FVector problems, InfSet] (Spring15: Mat problems (maxMat, scaleMat, mapMat, foldMat)) ++ implement an ADT with functions as part of its representation [HW3: FVector problems, InfSet] (Spring13: implement operations on data Shape = Blob (Point -> Bool); Fall13: implement Drawing type with operations; Spring15: implement DecFrac type (decimal fractions)) ++ implement functions over an ADT [HW3: FVector problems, InfSet] - give an instance declaration to make an ADT an instance of a type class [HW3: rate tests uses an instance declaration] ++ abstract a programming pattern as a function [HW3: concatMap, foldWindowPlan] (Spring13: write foldBTree as an abstraction of functions on binary trees; Fall13: select proper foldNWayTree code) TERMS AND CONCEPTS [Concepts] [MapToLanguages] You should be able to explain and use (in problems or essays) the following concepts (with appropriate comparisons to related concepts). You should be able to give examples of these concepts. - Scoping: - Find the free and bound identifiers in an expression [HW3: freeBQexp] (Spring13: free and bound variables in (\x -> (\y -> map (f x) lst)) Fall13: free and bound variable identifiers in (g (\g -> (\a -> (\b -> (length (g b)))))) ) - Why is static scoping useful? - How do closures aid in static scoping? + Haskell and declarative model concepts: ++ Be able to read a data definition in Haskell. ++ Be able to read and understand type declarations in Haskell. - What is a closure? + What is a curried function? + How does type checking work in Haskell? What do types mean? + Syntactic sugars: + What is a syntactic sugar? Give examples from Haskell. + Abstract Data Types (ADTs): + How are modules used to implement information hiding for ADTs? - How does information hiding interact with printing and comparing values? + Type classes and instances: - Be able to write an instance for a given type class - Infinite Streams (infinite lazy lists) - What is an infinite stream? - What is an infinite stream good for? - Lazy evaluation in Haskell - What causes expressions to be needed in Haskell?