******************* Chapter 9 Outline ******************* -- Chapter 9 spans from pages 299 to 346, for a total of 47 pages. * 9.1 Lists * p1. What lists are used to represent. * p2. Learning objectives. * 9.2 The list datatype * p1. "The list datatype is defined like this:" * f1. Definition of the list datatype. * p2. The type and data constructors of list. * p3. Arity of constructors. (tycon) ``[] a`` unary, ``a : [a]`` binary, (datacon) ``[]`` unary. * p4. "In English, one can read this as:" * f2. Anatomy of the list datatype declaration. * p5. The cons ``(:)`` data constructor is binary, takes a recursively defined argument, and represents a product relationship. * p6. Lists in Haskell are similar to singly-linked lists. * 9.3 Pattern matching on lists * p1. We can match on the ``(:)`` and ``[]`` data constructors. Here we match on the first argument of ``(:)``. * f1. Definition, type query, and sample use of ``myHead`` in GHCi. * p2. We'll match on the second argument of ``(:)`` in ``myTail``. * f2. Definition, type query, and sample use of ``myTail`` in GHCi. * p3. Both ``myHead`` and ``myTail`` don't handle the case of an empty list, ``[]``. * f3. GHCi session showing that exceptions are thrown when ``myHead`` and ``myTail`` are applied to ``[]``. * p4. * f4. Definition of ``myTail`` as source code, with a base case for ``[]`` added. * p5. "With that addition, our function now evaluates like this:" * f5. GHCi session showing ``myTail`` applied to a finite list and the empty list. * p6. Using ``Maybe``. * p7. Let's try an example using ``Maybe`` with ``myTail``. * f6. ``:info Maybe`` * p8. "Rewriting ``myTail`` to use ``Maybe`` is fairly straightforward:" * f7. Definition of ``safeTail``. * p9. Description of ``safeTail``. **See if you can rewrite the myHead function using Maybe.** * p10. Later the book will cover ``NonEmpty``, which avoids the empty list problem. * 9.4 List's syntactic sugar * p1. * f1. GHCi session demonstrating equivalence of ``[1,2,3]++[4]`` and ``(1:2:3:[])++(4:[])``. * p2. ``[x,y]`` syntax saves typing. * p3. Cons cells and spines. * p4. The spine is the connective structure between nested cons cells. * 9.5 Using ranges to construct lists * 9.5.1 Exercise: ``EnumFromTo`` * 9.6 Extracting portions of lists * p1. Let's first look at ``take``, ``drop``, and ``splitAt``. * f1. Type signatures of ``take``, ``drop``, and ``splitAt``. * p2. * p3. * f2. ``take`` applied to finite lists * p4. * f3. ``take`` applied to an infinite list * p5. * f4. ``drop`` applied to finite lists * p6. * f5. ``splitAt`` applied to finite lists * p7. Next we'll look at ``takeWhile`` and ``dropWhile`` * f6. Type signatures of ``takeWhile`` and ``dropWhile``. * p8. These functions will take or drop elements that meet the condition and then stop when it meets the first element that doesn't satisfy the predicate function. * p9. * f7. Take while the elements are less than 3 * p10. * f8. Take while the elements are less than 8 * p11. * f9. ``takeWhile`` produces an empty list when the first element does not meet the predicate. * p12. **"In the final example below, why does it only return a single a?"** * f10. ``takeWhile (=='a') "abracadabra"`` -- (The second element evaluates to ``False`` in our predicate function, so ``takeWhile`` stops taking elements after the first element.) * p13. Now we'll look at ``dropWhile``. * f11. Examples of ``dropWhlie`` applied to finite lists * 9.6.1 Exercises: Thy Fearful Symmetry * 1 * p1. * f1. * 2 * p1. * f1. The ``PoemLines`` module. * p2. * f2. The result that ``putStrLn sentences`` should print. * p3. * f3. Stub for the ``myLines`` function. * p4. * f4. A list named ``shouldEqual`` that ``myLines sentences`` should produce. * p5. * f5. A small test implemented as a ``main`` function. * 3 * p1. * 9.7 List comprehensions * p1. List comprehensions are a language construct inspired by set builder notation in mathematics. You use them to create new lists from an existing generator list, which may be filtered along the way by a guard. * p2. * f1. A simple comprehension, ``[ x^2 | x <- [1..10]]``, followed by a lot of explanatory text. * p3. * f2. ``[ x^2 | x <- [1..10]`` * 9.7.1 Adding predicates * p1. * p2. * f1. * p3. * p4. * p5. * p6. * f2. * p7. * p8. * f3. A list comprehension with a predicate, evaluated in GHCi. * p9. We can use multiple generators to zip two lists. * f4. Two list comprehensions that performs a cross product on two lists into a list of pairs, evaluated in GHCi. * p10. * p11. * f5. ``mySqr``, a comprehension of square numbers from n..10, evaluated in GHCi. * p12. We can use that list as a generator for another list comprehension. * f6. * 9.7.2 Exercises: Comprehend thy lists * p1. * f1. * 9.7.3 List comprehensions with strings * p1. * f1. * p2. * f2. * p3. * f3. An acronym generator. * p4. * p5. "All right, so we have our acro function with which we can generate acronyms from any string:" * f4. ``acro`` applied to different arguments in GHCi. * p6. **"Given the above, what do you think this function would do:"** * f5. * 9.7.4 Exercises: Square Cube * p1. * f1. * 1 * 2 * 3 * 9.8 Spines and non-strict evaluation * p1. The structure that connects elements together in composite datatypes is known as the spine. * f1. An ASCII art representation of the list ``[1,2]`` as a tree of data constructors and their term-level arguments. * p2. * p3. Evaluation proceeds down the spine (left to right), but construction proceeds up the spine (right to left). * p4. * f2. ASCII art pointing out the spine of a list. * p5. * 9.8.1 Using GHCi's :sprint command * p1. * p2. * p3. * p4. * f1. * p5. * p6. "Next, we'll take one value..." * f2. * p7. * p8. * f3. * p9. * p10. * f4. * p11. * f5. * p12. * 9.8.2 Spines are evaluated independently of values -- page 320 * p1. All expressions are evaluated to WHNF by default. * p2. WHNF vs NF. * p3. Examples of expressions, and whether they are WHNF or NF. * f1. ``(1, 2)`` -- page 321 * p4. * f2. ``(1, 1+1)`` * p5. * f3. ``\x -> x*10`` * p6. * f4. ``"Papu" ++ "chon"`` * p7. * f5. ``(1, "Papu" ++ "chon")`` * p8. * f6. Showing a fully evaluated list in GHCi. -- p9 is split between pages 321 and 322 * p9. -- page 322 * f7. A demonstration of WHNF evaluation in GHCi. * p10. * p11. * f8. The spine of a list that isn't spine strict and is awaiting something to force the evaluation. (The first cons cells, no arguments evaluated.) * p12. * p13. -- page 323 * p14. * f9. Tree representation of the spine of an unevaluated list with two elements. * p15. * f10. GHCi ``x = [1,undefined]; length x`` returns ``2``. * p16. * f11. Source code for a ``length`` function. * p17. -- page 324 * p18. * f12. A complicated tree representation showing forced cons constructors, with unevaluated arguments. * p19. * f13. Demonstration of applying ``length`` to a list with ``undefined`` in the spine. * p20. Printing the list fails, but it gets as far as printing the first ``[1***``. * p21. It's possible to write functions that will force both the spine and the values. * p22. We'll write our own sum function for the sake of demonstration: * f14. Source code for ``mySum``. * p23. -- page 325 * f15. The evaluation steps of ``mySum [1..5]`` * p24. * 9.8.3 Exercises: Bottom madness * 9.8.3.1 Will it blow up? * 9.8.3.2 Intermission: Is it in normal form? * 9.9 Transforming lists of values -- page 326 * p1. HOFs are use more often than primitive recursion to transform data. * p2. The ``map`` function applies a function to every element of a list. ``fmap`` does the same, but for any type that implements ``Foldable``. -- page 327 * f1. Examples of using ``map`` and ``fmap`` in GHCi. * p3. The types of ``map`` and ``fmap`` respectively are: * f2. * p4. * f3. * p5. * f4. ``:t map (+1)`` * p6. * p7. * f5. -- page 328 * p8. * f6. ``:t fmap (+1)`` * p9. * f7. The definition of ``map`` from the ``base`` package, heavily annotated. Spans pages 328 and 329. -- page 329 * p10. "How do we write out what ``map f`` does?" * f8. ``map (+1) [1, 2, 3]`` * p11. * f9. ``map (+1) (1 : (2 : (3 : [])))`` * p12. * f10. Shows one step of the evaluation process for ``map (+1) [1,2,3]``. * p13. * f11. * p14. * f12. -- page 330 * p15. * f13. * p16. "Finishing the reduction of the expression:" * f14. * p17. "Using the syntactic sugar of list, here's an approximation of what map is doing for us:" * f15. * p18. * f16. * p19. * f17. -- page 331 * p20. Map is not applied to every element at once. Each element is mapped if and when its evaluation is forced. * f18. * p21. * f19. * p22. * p23. -- page 332 * p24. * f20. * p25. * f21. * p26. * f22. ``Prelude> map (\x -> if x == 3 then (-x) else (x)) [1..10]`` * p27. -- page 332 * 9.9.1 Exercises: More bottoms * 1 * 2 * 3 -- page 333 * 4 * 5 * a * b * c * 6 * 9.10 Filtering lists of values * p1. We showed a few examples of ``filter`` earlier. * f1. ``filter even [1..10]`` * p2. Filter has the following definition: -- page 334 * f2. The definition of filter. * p3. Filter takes a predicate function and a list and returns a list containing only the elements that satisfy the predicate. * p4. Examples of ``filter`` that we've already seen. * f3. ``filter (== 'a') "abracadabra"`` * p5. The following examples does the same thing as filter even, but with a lambda as input. * f4. * p6. We covered list comprehensions as a way of filtering lists, as well. Compare the following: * f5. Example of filter vs a guarded list comprehension. * p7. * p8. **We recommend at this point that you try writing some filter functions of your own to get comfortable with the pattern.** -- page 335 * 9.10.1 Exercises: Filtering * 1 * 2 * 3 * 9.11 Zipping lists * p1. * p2. * f1. * p3. * f2. * p4. * f3. * p5. * f4. * p6. "We can use unzip to recover the lists as they were before they were zipped:" * f5. * p7. "Be aware that information can be list in this process, because zip must stop on the shortest list:" * f6. * p8. "We can also use zipWith to apply a function to the values of two lists in parallel:" * f7. zipWith * p9. "A brief demonstration of how ``zipWith`` works:" * f8. * 9.11.1 Zipping exercises * 9.12 Chapter exercises * p1. * 9.12.1 Data.Char * p1. * 1 * 2 * 3 * 4 * 5 * 6 * 9.12.2 Ciphers * p1. Save these exercises in a module named ``Cipher``, since we'll be coming back to them later. * p2. The Caesar cipher shift by :math:`n` numbers forward in the alphabet. * p3. Write a basic Caesar cipher. * p4. Try to implement the cipher before googling a solution. * p5. The first lines should look like: * f1. A module header and import statement for ``Cipher``. * p6. ``ord`` and ``chr`` may be useful to you. * f2. A GHCi session where the types of ``chr`` and ``ord`` are queried. * p7. You want your shift to wrap back around the alphabet. * p8. Also, write an ``unCeasar`` cipher. * 9.12.3 Writing your own standard functions * p1. * p2. -- page 341 * f1. myAnd * p3. "And now the fun begins:" * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 9.13 Definitions * Product type * Sum type * Cons * Cons cell * Spine * 9.14 Follow-up resources * Data.List documentation for the base library. http://hackage.haskell.org/package/base/docs/Data-List.html * Haskell Wiki. Ninety-Nine Haskell problems. https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems