X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2F_assignment5.mdwn;h=8a60b511c507de0f30dc47c84a9a28c517f9d6b8;hp=d3646d71af979b8687a6a4dca5fc44e85b0b29d1;hb=9ce4de98643f88eba5865aeededc4b9ad9c8bbfc;hpb=a40713fd2a60a6591529b7f8a13419527a645c7c diff --git a/exercises/_assignment5.mdwn b/exercises/_assignment5.mdwn index d3646d71..8a60b511 100644 --- a/exercises/_assignment5.mdwn +++ b/exercises/_assignment5.mdwn @@ -1,14 +1,4 @@ -Assignment 5 - -Ï -Ω -λ -Î -â¡ -α -β - - +Ï Î© λ Π⡠α β ## Option / Maybe Types ## @@ -20,11 +10,11 @@ and Haskell defines like this: data Maybe a = Nothing | Just a -That is, instances of this type are either some `'a` (this can be any type), wrapped up in a `Some` or `Just` box, or they are a separate value representing a failure. This is sort of like working with a list guaranteed to have a length ≤ 1. +That is, instances of this type are either an instance of `'a` (this can be any type), wrapped up in a `Some` or `Just` box, or they are a separate value representing a failure. This is sort of like working with a set or a list guaranteed to be either singleton or empty. -In one of the homework sessions, Chris posed the challenge: you know those dividers they use in checkout lines to separate your purchases from the next person's? What if you wanted to buy one of those dividers? How could they tell whether it belonged to your purchases or was separating them from others? +In one of the homework meetings, Chris posed the challenge: you know those dividers they use in checkout lines to separate your purchases from the next person's? What if you wanted to buy one of those dividers? How could they tell whether it belonged to your purchases or was separating them from others? -The OCaml and Haskell solution is to use not supermarket dividers but instead those gray bins from airport security. If you want to buy something, it goes into a bin. (OCaml's `Some`, Haskell's `Just`). If you want to separate your stuff from the next person, you send an empty bin (OCaml's `None`, Haskell's `Nothing`). If you happen to be buying a bin, OK, you put that into a bin. In OCaml it'd be `Some None` (or `Some (Some stuff)` if the bin you're buying itself contains some stuff); in Haskell `Just Nothing`. We won't confuse a bin that contains a bin with an empty bin. (Not even if the contained bin is itself empty.) +The OCaml and Haskell solution is to use not supermarket dividers but instead those gray bins from airport security. If you want to buy something, it goes into a bin. (OCaml's `Some`, Haskell's `Just`). If you want to separate your stuff from the next person, you send an empty bin (OCaml's `None`, Haskell's `Nothing`). If you happen to be buying a bin, OK, you put that into a bin. In OCaml it'd be `Some None` (or `Some (Some stuff)` if the bin you're buying itself contains some stuff); in Haskell `Just Nothing`. This way, we can't confuse a bin that contains a bin with an empty bin. (Not even if the contained bin is itself empty.) 1. Your first problem is to write a `maybe_map` function for these types. Here is the type of the function you should write: @@ -34,17 +24,17 @@ The OCaml and Haskell solution is to use not supermarket dividers but instead th -- Haskell maybe_map :: (a -> b) -> Maybe a -> Maybe b - If your `maybe_map` function is given a `None` or `Nothing` as its second argument, that should be what it returns. Otherwise, it should apply the function it got as its first argument to the contents of the `Some` or `Just` bin that it got as its second, and return the result, wrapped back up in a `Some` or `Just`. + If your `maybe_map` function is given a `None` or `Nothing` as its second argument, that should be what it returns. Otherwise, it should apply the function it got as its first argument to the contents of the `Some` or `Just` bin that it got as its second, and return the result, wrapped back up in a `Some` or `Just`. (Yes, we know that the `fmap` function in Haskell already implements this functionality. Your job is to write it yourself.) - One way to extract the contents of a option or Maybe value is to pattern match on that value, as you did with lists. In OCaml: + One way to extract the contents of an `option`/`Maybe` value is to pattern match on that value, as you did with lists. In OCaml: - match x with + match m with | None -> ... | Some y -> ... In Haskell: - case x of { + case m of { Nothing -> ...; Just y -> ... } @@ -55,7 +45,7 @@ The OCaml and Haskell solution is to use not supermarket dividers but instead th 2. Next write a `maybe_map2` function. Its type should be: (* OCaml *) - maybe_map2 ('a -> 'b -> 'c) -> ('a) option -> ('b) option -> ('c) option + maybe_map2 : ('a -> 'b -> 'c) -> ('a) option -> ('b) option -> ('c) option -- Haskell maybe_map2 :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c @@ -104,17 +94,17 @@ These expressions query whether `t` is a branching `color_tree` (not a leaf) who Choose one of these languages and write the following functions. -3. Define a function `tree_map` whose type is (as shown by OCaml): `('a -> 'b) -> ('a) color_tree -> ('b) color_tree`. It expects a function `f` and an `('a) color_tree`, and returns a new tree with the same structure and inner branch labels as the original, but with all of its leaves now having had `f` applied to their original value. So for example, `map (2*) t1` would return `t1` with all of its leaf values doubled. +3. Define a function `tree_map` whose type is (as shown by OCaml): `('a -> 'b) -> ('a) color_tree -> ('b) color_tree`. It expects a function `f` and an `('a) color_tree`, and returns a new tree with the same structure and inner branch colors as the original, but with all of its leaves now having had `f` applied to their original value. So for example, `map (2*) t1` would return `t1` with all of its leaf values doubled. -4. Define a function `tree_foldleft` that accepts an argument `g : 'z -> 'a -> 'z` and a seed value `z : 'z` and a tree `t : ('a) color_tree`, and returns the result of applying `g` first to `z` and `t`'s leftmost leaf, and then applying `g` to *that result* and `t`'s second-leftmost leaf, and so on, all the way across `t`'s fringe. +4. Define a function `tree_foldleft` that accepts an argument `g : 'z -> 'a -> 'z` and a seed value `z : 'z` and a tree `t : ('a) color_tree`, and returns the result of applying `g` first to `z` and `t`'s leftmost leaf, and then applying `g` to *that result* and `t`'s second-leftmost leaf, and so on, all the way across `t`'s fringe. Only the leaf values affect the result; the inner branch colors are ignored. 5. How would you use the function defined in problem 4 (the previous problem) to sum up the values labeling the leaves of an `(int) color_tree`? 6. How would you use the function defined in problem 4 to enumerate a tree's fringe? (Don't worry about whether it comes out left-to-right or right-to-left.) -7. How would you use the function defined in problem 4 to make a copy of a tree with the same structure and inner node labels, but where the leftmost leaf is now labeled `0`, the second-leftmost leaf is now labeled `1`, and so on. +7. Write a recursive function to make a copy of a `color_tree` with the same structure and inner branch colors, but where the leftmost leaf is now labeled `0`, the second-leftmost leaf is now labeled `1`, and so on. -8. (More challenging.) Write a recursive function that makes a copy of a tree with the same structure and inner node labels, but replaces each leaf label with the int that reports how many of that leaf's ancestors are labeled `Red`. For example, if we give your function a tree: +8. (More challenging.) Write a recursive function that makes a copy of a `color_tree` with the same structure and inner branch colors, but replaces each leaf label with the `int` that reports how many of that leaf's ancestors are labeled `Red`. For example, if we give your function a tree:
Red @@ -140,10 +130,10 @@ Choose one of these languages and write the following functions. 2 2-9. (More challenging.) Assume you have a `color_tree` whose leaves are labeled with `int`s (which might be negative). For this problem, assume also that the the same color never labels multiple inner nodes. Write a recursive function that reports which color has the greatest score when you sum up all the values of its descendent leaves. Since some leaves may have negative values, the answer won't always be the color at the tree root. In the case of ties, you can return whichever of the highest scoring colors you like. +9. (More challenging.) Assume you have a `color_tree` whose leaves are labeled with `int`s (which may be negative). For this problem, assume also that the the same color never labels multiple inner branches. Write a recursive function that reports which color has the greatest "score" when you sum up all the values of its descendent leaves. Since some leaves may have negative values, the answer won't always be the color at the tree root. In the case of ties, you can return whichever of the highest scoring colors you like. -## Search Tree ## +## Search Trees ## (More challenging.) For the next problem, assume the following type definition: @@ -153,7 +143,7 @@ Choose one of these languages and write the following functions. -- Haskell data Search_tree = Nil | Inner Search_tree Int Search_tree deriving (Show) -That is, its leaves have no labels and its inner nodes are labeled with `int`s. Additionally, assume that all the `int`s in nodes descending to the left from a given node will be less than the `int` of that parent node, and all the `int`s in nodes descending to the right will be greater. We can't straightforwardly specify this constraint in OCaml's or Haskell's type definitions. We just have to be sure to maintain it by hand. +That is, its leaves have no labels and its inner nodes are labeled with `int`s. Additionally, assume that all the `int`s in branches descending to the left from a given node will be less than the `int` of that parent node, and all the `int`s in branches descending to the right will be greater. We can't straightforwardly specify this constraint in OCaml's or Haskell's type definitions. We just have to be sure to maintain it by hand. 10. Write a function `search_for` with the following type, as displayed by OCaml: @@ -165,7 +155,7 @@ That is, its leaves have no labels and its inner nodes are labeled with `int`s. data Direction = Left | Right deriving (Eq, Show) search_for :: Int -> Search_tree -> Maybe [Direction] - Your function should search through the tree for the specified `int`. If it's never found, it should return the value OCaml calls `None` and Haskell calls `Nothing`. If it finds the `int` right at the root of the search_tree, it should return the value OCaml calls `Some []` and Haskell calls `Just []`. If it finds the `int` by first going down the left branch from the tree root, and then going right twice, it should return `Some [Left; Right; Right]` or `Just [Left, Right, Right]`. + Your function should search through the tree for the specified `int`. If it's never found, it should return the value OCaml calls `None` and Haskell calls `Nothing`. If it finds the `int` right at the root of the `search_tree`, it should return the value OCaml calls `Some []` and Haskell calls `Just []`. If it finds the `int` by first going down the left branch from the tree root, and then going right twice, it should return `Some [Left; Right; Right]` or `Just [Left, Right, Right]`. ## More Map2s ## @@ -177,21 +167,23 @@ Above, you defined `maybe_map2` [WHERE]. Before we encountered `map2` for lists. (* OCaml *) map2_zip : ('a -> 'b -> 'c) -> ('a) list -> ('b) list -> ('c) list - Write a recursive function that implements this, in Haskell or OCaml. Let's say you can stop when the shorter list runs out, if they're of different lengths. (OCaml and Haskell each already have functions in their standard libraries that do this. This also corresponds to what you can write as a list comprehension in Haskell like this: + Write a recursive function that implements this, in Haskell or OCaml. Let's say you can stop when the shorter list runs out, if they're of different lengths. (OCaml and Haskell each already have functions in their standard libraries --- `map2` or `zipWith` -- that do this. And it also corresponds to a list comprehension you can write in Haskell like this: :set -XParallelListComp [ f x y | x <- xs | y <- ys ] + But we want you to write this function from scratch.) -12. What is the relation between the function you just wrote, and the `maybe_map2` function you wrote for an earlier problem? +12. What is the relation between the function you just wrote, and the `maybe_map2` function you wrote for problem 2, above? 13. Another strategy is to take the *cross product* of the two lists. If the function: (* OCaml *) - map2_cross : ('a -> 'b -> 'c) -> ('a) list -> ('b) list -> ('c) list list + map2_cross : ('a -> 'b -> 'c) -> ('a) list -> ('b) list -> ('c) list - is applied to the arguments `f`, `[x0, x1, x2]`, and `[y0, y1]`, then the result should be: `[[f x0 y0, f x0 y1], [f x1 y0, f x1 y1], [f x2 y0, f x2 y1]]`. Write this function. + is applied to the arguments `f`, `[x0, x1, x2]`, and `[y0, y1]`, then the result should be: `[f x0 y0, f x0 y1, f x1 y0, f x1 y1, f x2 y0, f x2 y1]`. Write this function. + A similar choice between "zipping" and "crossing" could be made when `map2`-ing two trees. For example, the trees: @@ -215,15 +207,14 @@ f 1 6 f 2 7 "Crossing" the trees would instead add copies of the second tree as subtrees replacing each leaf of the original tree, with the leaves of that larger tree labeled with `f` applied to `3` and `6`, then `f` applied to `3` and `8`, and so on across the fringe of the second tree; then beginning again (in the subtree that replaces the `4` leaf) with `f` applied to `4` and `6`, and so on. -* In all the plain `map` functions, whether for lists, or for option/Maybes, or for trees, the structure of the result exactly matched the structure of the argument. - -[LOOKUP in APPLICATIVE] +* In all the plain `map` functions, whether for lists, or for `option`/`Maybe`s, or for trees, the structure of the result exactly matched the structure of the argument. -* In the `map2` functions, whether for lists or for option/Maybes or for trees, and whether done in the "zipping" style or in the "crossing" style, the structure of the result may be a bit different from the structure of the arguments. But the *structure* of the arguments is enough to determine the structure of the result; you don't have to look at the specific list elements or labels on a tree's leaves or nodes to know what the *structure* of the result will be. +* In the `map2` functions, whether for lists or for `option`/`Maybe`s or for trees, and whether done in the "zipping" style or in the "crossing" style, the structure of the result may be a bit different from the structure of the arguments. But the *structure* of the arguments is enough to determine the structure of the result; you don't have to look at the specific list elements or labels on a tree's leaves or nodes to know what the *structure* of the result will be. -* We can imagine more radical transformations, where the structure of the result *does* depend on what specific elements the original structure(s) had. For example, what if we had to transform a tree by turning every leaf into a subtree that contained all of those leaf's prime factors. Or consider our problem from last week [WHERE] where you converted `[3, 2, 0, 1]` not into `[[3,3,3], [2,2], [], [1]]` --- which still has the same structure, that is length, as the original --- but rather into `[3, 3, 3, 2, 2, 1]` --- which doesn't. +* We can imagine more radical transformations, where the structure of the result *does* depend on what specific elements the original structure(s) had. For example, what if we had to transform a tree by turning every leaf into a subtree that contained all of those leaf's prime factors? Or consider our problem from last week [WHERE] where you converted `[3, 2, 0, 1]` not into `[[3,3,3], [2,2], [], [1]]` --- which still has the same structure, that is length, as the original --- but rather into `[3, 3, 3, 2, 2, 1]` --- which doesn't. + (Some of you had the idea last week to define this last transformation in Haskell as `[x | x <- [3,2,0,1], y <- [0..(x-1)]]`, which just looks like a cross product, that we counted under the *previous* bullet point. However, in that expression, the second list's structure depends upon the specific values of the elements in the first list. So it's still true, as I said, that you can't specify the structure of the output list without looking at those elements.) -These three levels of how radical a transformation you are making to a structure, and the parallels between the transformations to lists, to option/Maybes, and to trees, will be ideas we build on in coming weeks. +These three levels of how radical a transformation you are making to a structure, and the parallels between the transformations to lists, to `option`/`Maybe`s, and to trees, will be ideas we build on in coming weeks. @@ -234,7 +225,7 @@ These three levels of how radical a transformation you are making to a structure In OCaml, you can define some datatypes that represent terms in the untyped Lambda Calculus like this: type identifier = string - type lambda_term = Var of identifier | Abstract of identifier * _____ | App of _____ ;; + type lambda_term = Var of identifier | Abstract of identifier * _____ | App of _____ We've left some gaps. @@ -247,37 +238,34 @@ In Haskell, you'd define it instead like this: 16. Write a function `occurs_free` that has the following type: - occurs_free : identifier -> lambda_term -> bool + occurs_free : identifier -> lambda_term -> bool -That's how OCaml would show it. Haskell would use double colons `::` instead, and would also capitalize all the type names. Your function should tell us whether the supplied identifier ever occurs free in the supplied `lambda_term`. + That's how OCaml would show it. Haskell would use double colons `::` instead, and would also capitalize all the type names. Your function should tell us whether the supplied identifier ever occurs free in the supplied `lambda_term`. ## Encoding Booleans, Church numerals, and Right-Fold Lists in System F ## -(These questions are adapted from web materials by Umut Acar. See -