XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek1_advanced_notes.mdwn;h=2137d114a5afeb4fdb27dcdce05fc194fcc8997b;hp=203a22fcf1adb0a8fbf6726f3926099966599003;hb=a79e0e734113a0d29f064fc8fb2ae7258e246e55;hpb=6906b72ae2c64971056a409aa132a394eef64860
diff git a/topics/week1_advanced_notes.mdwn b/topics/week1_advanced_notes.mdwn
index 203a22fc..2137d114 100644
 a/topics/week1_advanced_notes.mdwn
+++ b/topics/week1_advanced_notes.mdwn
@@ 1,6 +1,8 @@
These are some advanced notes extending the material presented this week. Don't worry about mastering this stuff now if you're already feeling saturated. But you will need to learn these things in the near future, so tackle them as soon as you're ready.
+[[!toc]]
+
### More on multivalues ###
A multivalue is a series of *zero or more* values. They are the result of evaluating expressions that consist of *zero or more* expressions, separated by commas, and enclosed in parentheses. So these expressions evaluate to multivalues:
@@ 46,7 +48,7 @@ In OCaml, there are no untiltheendoftheline comments. The only comments sta
I agree it's annoying that these conventions are so diverse. There are plenty other commenting conventions out there, too.

+
### Matching function values ###
A function value doesn't have any structureat least none that's visible to the patternmatching system. You can only match against simple patterns like `_` or the variable `f`.
@@ 70,6 +72,7 @@ This is one of the few places where I'll indulge in the use of single `=`. Note
This special syntax is only permitted in `let` and `letrec`constructions, not in `case`constructions.
+
### Pattern guards ###
In `case` contructions, it's sometimes useful to check not only whether a certain pattern matches, but also whether a certain boolean expression is true, typically where we want some variables in that expression to be bound by the relevant pattern. Thus, for example, if we wanted to count the number of odd numbers in a sequence, we could do this:
@@ 97,12 +100,13 @@ It's a bit cumbersome, though, to have the doublyembedded `case`constructions.
If we get to the `y & ys` line in the pattern list, and the patternmatch succeeds, then we check the guard expression `odd? y`, with `y` bound to whatever part of `xs` matched the corresponding part of the pattern `y & ys`. If that boolean expression is `'true`, then we continue to the righthand side, after the `then`, just as usual. But if the boolean expression is `'false`, then we treat the whole line as a failed match, and proceed on to the next line in the binding list, if any.
+
### Aspatterns ###
Sometimes it's useful to bind variables against overlapping parts of a structure. For instance, suppose I'm writing a pattern that is to be matched against multivalues like `([10, 20], 'true)`. And suppose I want to end up with `ys` bound to `[10, 20]`, `x` bound to `10`, and `xs` bound to `[20]`. Using the techniques introduced so far, I have two options. First, I could bind `ys` against `[10, 20]`, and then initiate a second patternmatch to break that up into `10` and [20]`. Like this:
+Sometimes it's useful to bind variables against overlapping parts of a structure. For instance, suppose I'm writing a pattern that is to be matched against multivalues like `([10, 20], 'true)`. And suppose I want to end up with `ys` bound to `[10, 20]`, `x` bound to `10`, and `xs` bound to `[20]`. Using the techniques introduced so far, I have two options. First, I could bind `ys` against `[10, 20]`, and then initiate a second patternmatch to break that up into `10` and `[20]`. Like this:
 case [10, 20] of
 [ys, _] then case ys of
+ case ([10, 20], 'true) of
+ (ys, _) then case ys of
x & xs then ...;
...
end;
@@ 111,8 +115,8 @@ Sometimes it's useful to bind variables against overlapping parts of a structure
Alternatively, I could directly bind `x` against `10` and `xs` against `[20]`. But then I would have to recons them together again to get `ys`. Like this:
 case [10, 20] of
 [x & xs, _] then let
+ case ([10, 20], 'true) of
+ (x & xs, _) then let
ys match x & xs
in ...;
...
@@ 120,12 +124,13 @@ Alternatively, I could directly bind `x` against `10` and `xs` against `[20]`. B
Both of these strategies work. But they are a bit inefficient. I said you didn't really need to worry about efficiency in this seminar. But these are also a bit cumbersome to write. There's a special syntax that enables us to bind all three of `ys`, `x`, and `xs` in the desired way, despite the fact that they will be matching against overlapping, rather than discrete, parts of the value `[10, 20]`. The special syntax looks like this:
 case [10, 20] of
 [(x & xs) as ys, _] then ...
+ case ([10, 20], 'true) of
+ ((x & xs) as ys, _) then ...
...
end
+
### $ Syntax ###
Haskell has a useful bit of syntax that we will adopt. They use `$` as an infix operator that has the same kind of effect as Russell & Whitehead's period. It is semantically inert, and only affects grouping. It enables you to avoid some parentheses in lots of situations. For example, if you want to check that a sequence `xs` is not empty, you'd express that like this:
@@ 165,12 +170,51 @@ Function composition, which mathematicians write as `f` ○ `g`, is defined as
We've already come across the `id` function, namely λ `x. x`.
Other common functions are `fst`, which takes two arguments and returns the first of them; `snd`, which takes two arguments and returns the second of them; and `swap`, which takes two arguments and returns them both but with their positions swapped. These functions can be defined like this:
+Other common functions are `fst`, which takes two arguments and returns the first of them; `snd`, which takes two arguments and returns the second of them; and `swap`, which takes two arguments and returns them both but with their positions swapped. A fourth function is `dup`, which takes one argument and returns it twice.
+These functions can be defined like this:
let
fst (x, y) = x;
snd (x, y) = y;
 swap (x, y) = (y, x)
 in (fst, snd, swap)
+ swap (x, y) = (y, x);
+ dup x = (x, x)
+ in (fst, snd, swap, dup)
+
+
+
+### Sections ###
+
+OCaml and Haskell have a convenient bit of syntax for the common case where you want a function like this:
+
+ lambda x. 10  x
+
+or like this:
+
+ lambda x. x & ys
+
+or like this:
+
+ lambda (x, y). x + y
+
+They permit you to appreviate the first λexpression as simply `(10  )`. We know there's an argument missing, because the infix operator `` demands two arguments, but we've only supplied one. So `(10  )` expresses a function that takes an argument `x` and evaluates to `10  x`. In other words, it expresses λ`x. 10  x`. Similarly, `( & ys)` expresses a function that takes an argument `x` and evaluates to `x & ys`.
+
+All of this only works with infix operators like ``, `&` and `+`. You can't write `(1 swap)` or `(swap 1)` to mean λ`x. swap (1, x)`.
+
+Can you guess what our shortcut for the last function will be? It's `( + )`. That
+expresses a function that takes two arguments `(x, y)` and evaluates to `x + y`.
+
+Wait a second, you say. Isn't that just what `+` does *already*? Why am I making a distinction between `+` and `( + )`? The difference is that bare `+` without any parentheses is an *infix* operator that comes between its arguments. Whereas when we wrap it with parentheses, it loses its special infix syntax and then just behaves like a plain variable denoting a function, like `swap`. Thus whereas we write:
+
+ x + y
+
+if we want to use `( + )`, we have to instead write:
+
+ ( + ) (x, y)
+
+It may not be obvious now why this would ever be useful, but sometimes it will be.
+
+All of these shorthands `(10  )`, `( & ys)` and `( + )` are called "sections". I don't know exactly why.
+
+Confession: actually, what I described here diverges *a bit* from how OCaml and Haskell treat `( + )`. They wouldn't really write `( + ) (x, y)` like I did. Instead they'd write `( + ) x y`. We will look at the difference between these next week.