topics/week3_lists.mdwn

   1 # More on Lists #
   2
   3 ## Comprehensions ##
   4
   5 We know you are already familiar with the following kind of notation for designating sets:
   6
   7 { <em>x</em> + 1 | <em>x</em> &isin; Primes and &phi;<em>x</em> }
   8
   9 This kind of notation is called a **set comprehension.**
  10 Here Primes is assumed to be some, presumably larger set. &phi; expresses some condition that members of Primes might conceivably fail to satisfy.
  11
  12
  13 Some of the functional programming languages permit you to specify data structures in this same way. Kapulet comes closest, in that it also has set comprehension notation. In Kaupulet one writes:
  14
  15 <code>{ x + 1 | x from Primes, &phi; x }</code>
  16
  17 The changes are only that we write `x from Primes`, with `Primes` being an expression that evaluates to a set, and we separate that clause from the test clause with a comma. <code>&phi; x</code> can be any expression that evaluates to a boolean. Moreover, such clauses can come in any order, and there can be any number of them, though the above is the most useful pattern. But you can also write:
  18
  19     { 1 | 'true }
  20
  21 which evaluates to `{ 1 }`, or:
  22
  23     { 1 | 'false }
  24
  25 which evaluates to the empty set `{ }`. What if you have multiple `from` clauses? This is possible, and iterates over the *cross-product* of the two sets you're drawing from. So:
  26
  27     { 10*x + y | x from {1, 2, 3}, y from {4, 5} }
  28
  29 evaluates to the set `{ 14, 15, 24, 25, 34, 35 }`.
  30
  31 Haskell doesn't have set literals like Kapulet does, but it also allows this kind of notation with lists, that is, it has **list comprehensions**. (And so does Kapulet.) Thus in Haskell you can write:
  32
  33     [ 10*x + y | x <- [1, 2, 3], y <- [4, 5] ]
  34
  35 and that evaluates to `[14, 15, 24, 25, 34, 35]`. Notice that Haskell's syntax differs slightly. Changing the order of the `from`/`<-` clauses changes the order in which the elements will be added to the result list:
  36
  37     [ 10*x + y | y <- [4, 5], x <- [1, 2, 3] ]
  38
  39 That evaluates to `[14, 24, 34, 15, 25, 35]`.
  40
  41 You can also mix in test clauses:
  42
  43     [ 10*x + y | y <- [4, 5], odd y, x <- [1, 2, 3] ]
  44
  45 evaluates to `[15, 25, 35]`.
  46
  47 Haskell also has an extension that permits you to iterate over multiple lists *in parallel* rather than to iterate over their cross-product. If you type `:set -XParallelListComp` in the ghci interpreter, that will enable this extension, and then:
  48
  49     [ 10*x + y | y <- [4, 5, 6] | x <- [1, 2, 3] ]
  50
  51 will evaluate to `[14, 25, 36]`. If the lists are of unequal length, Haskell stops when it exhausts the shortest. These behaviors are similar to the `map2` function you defined in the week 1 homework. That also took an argument from each of several sequences in parallel. (The corresponding functions in Haskell are called `zip` and `zipWith`.)
  52
  53 OCaml [permits lists comprehensions as an extension](http://stackoverflow.com/questions/27652428/list-comprehension-in-ocaml), and [so too does Scheme](http://srfi.schemers.org/srfi-42/srfi-42.html), but these are a bit harder to use.
  54
  55 All of these things can also be expressed in these languages without using the comprehension syntax. For example, this list comprehension (in Kapulet syntax):
  56
  57     [ 10*x | x from [1, 2, 3, 4, 5] ]
  58
  59 can be expressed as:
  60
  61     map (lambda x. 10*x) [1, 2, 3, 4, 5]
  62
  63 and this:
  64
  65     [ 10*x | x from [1, 2, 3, 4, 5], odd? x ]
  66
  67 can be expressed as:
  68
  69     map (lambda x. 10*x) $ filter odd? [1, 2, 3, 4, 5]
  70
  71 (We explained the `$` notation in [[week 1's advanced notes|week1_kapulet_advanced/#dollar]]. This is equivalent to `map (lambda x. 10*x) (filter odd? [1, 2, 3, 4, 5])`.)
  72
  73 Iterating over the cross-product of several lists is a bit harder. Consider:
  74
  75     [ 10*x + y | y from [4, 5, 6], y < 6, x from [1, 2, 3] ]
  76
  77 To translate that, first let's handle the iteration over the final list, that `x` is drawn from:
  78
  79     map (lambda x. 10*x + y) [1, 2, 3]
  80
  81 This looks like what we had before, except that now we have this free variable `y` in our lambda expression. Perhaps we can bind that variable inside a *larger* lambda expression, and then map (and filter) *that* larger lambda expression over the list that `y` is drawn from:
  82
  83     let
  84       f match lambda y. map (lambda x. 10*x + y) [1, 2, 3]
  85     in map f $ filter (lambda y. y < 6) [4, 5, 6]
  86
  87 This gives us nearly what we want. It evaluates to:
  88
  89     [[14, 24, 34], [15, 25, 35]]
  90
  91 Why? Because the `filter` expression at the end is restricting the domain that `y` ranges over to `[4, 5]`. Over this domain we are selecting a value to bind `y` to, and then evaluating the `map` expression inside `f` with `y` so bound. With `y` bound to `4`, we get the result `[14, 24, 34]`. With `y` bound to `5`, we get the result `[15, 25, 35]`. These two results, in order, are the elements that make up the sequence which is the result of the outermost `map` expression.
  92
  93 One final twist is that our original list comprehension gives us a "flatter" result. In both Kapulet (and Haskell, modulo a few syntax adjustments), the list comprehension:
  94
  95     [ 10*x + y | y from [4, 5, 6], y < 6, x from [1, 2, 3] ]
  96
  97 evaluates to:
  98
  99     [14, 24, 34, 15, 25, 35]
 100
 101 We can turn the preceding result into this result with the Kapulet function `join` (Haskell calls it `concat` or `Control.Monad.join`):
 102
 103     join [[14, 24, 34], [15, 25, 35]]
 104
 105 evaluates to the "flatter" list displayed above.
 106
 107 By the way, this `join` operation only affects a single layer of `[ ]`s. This:
 108
 109     join [ [[10,20], [30], []],  [[40], [50,60]] ]
 110
 111 evaluates to:
 112
 113     [[10,20], [30], [], [40], [50,60]]
 114
 115 not to:
 116
 117     [10, 20, 30, 40, 50, 60]
 118
 119 To get the latter, you'd need to apply `join` twice.
 120
 121
 122 ## Tails ##
 123
 124 For the Lambda Calculus, we've proposed to encode lists in terms of higher-order functions that perform right-folds on (what we intuitively regard as) the real list. Thus, the list we'd write in Kapulet or Haskell as:
 125
 126     [a, b, c]
 127
 128 for some expressions `a`, `b`, and `c`, would be encoded in the Lambda Calculus as:
 129
 130     \f z. f a (f b (f c z))
 131
 132 With that choice of encoding, it's not difficult to write a `head` function. You did this for one of the week 2 homeworks. However, it is more challenging to write a `tail` function. Here is the intuitive idea behind one way we could do this. Our "starting value" --- what gets bound to `z` in the above lambda expression --- will be *a pair* of two values. I'll write it as `([], err)` for the moment, while we fix our intuitions, rather than using the more verbose Lambda Calculus representation of pairs and `[]`. The `err` will be whatever we decide should be the `tail` of an empty list. Perhaps it should be `[]`, but I'll just leave it as `err` for this exercise. Now, when we combine the rightmost element of the list with this, by evaluating `f c ([], err)`, we want the result to be `([c], [])`. That is, we throw away the second member of the pair, copy the first member over into the second slot, and `cons` the `c` onto the first member in the first slot. At the next stage, the result will be `([b, c], [c])`. And at the final stage, the result will be `([a, b, c], [b, c])`. Now we just have to extract the second member of this pair, and that will be the tail of our list.
 133
 134 If you've followed that intuitive presentation, then here is how you can write it in the lambda evaluator:
 135
 136     let empty = \f z. z in                   ; as before
 137     let cons = \d ds. \f z. f d (ds f z) in  ; as before
 138     let pair = \x y. \f. f x y in
 139     let snd = \x y. y in
 140     let shift = \h p. p (\x y. pair (cons h x) x) in
 141     let tail = \xs. (xs shift (pair empty err)) snd in
 142     ...
 143
 144 Here `shift` is our fold-function, and takes two arguments, the current list element `h` and the pair `p` that we've built up from the starting value by folding over the more rightward portion of the list, if any. The `shift` function binds the two members of the pair to `x` and `y`, disregarding the second. It returns a new pair whose first member is `cons h x` and whose second member is `x`. Our starting value is `pair empty err`. And at the end of our fold we're left with a pair, and want to extract its second member; that's why `tail` is of the form `\xs. (xs shift ...) snd`.
 145
 146 Try it out in the lambda evaluator. After the code above, you can write:
 147
 148     ...
 149     let abc = cons a (cons b (cons c empty)) in  ; encoding of [a, b, c]
 150     tail abc
 151
 152 and the result will be `\f z. f b (f c z)`, our encoding of `[b, c]`.
 153