From: Chris Barker <barker@kappa.linguistics.fas.nyu.edu>
Date: Tue, 26 Oct 2010 15:25:13 +0000 (-0400)
Subject: hw5
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=ac6c32595e75ae0d3aa0631be7df6ca758626d56;hp=c45c91f3f0a5e1e1a4098d8fb610d55ea0611977

hw5
---

diff --git a/assignment5.mdwn b/assignment5.mdwn
index 2078c1c0..cc714e90 100644
--- a/assignment5.mdwn
+++ b/assignment5.mdwn
@@ -152,8 +152,8 @@ binary trees working in OCaml.
 
    Recall from class System F, or the polymorphic λ-calculus.
 
-    τ ::= α | τ1 → τ2 | ∀α. τ
-    e ::= x | λx:τ. e | e1 e2 | Λα. e | e [τ ]
+    τ ::= 'α | τ1 → τ2 | ∀'α. τ | c
+    e ::= x | λx:τ. e | e1 e2 | Λ'α. e | e [τ ]
 
    Recall that bool may be encoded as follows:
 
@@ -181,7 +181,12 @@ binary trees working in OCaml.
    a function s : α → α.
 
    **Excercise**: get booleans and Church numbers working in OCaml,
-     including OCaml versions of bool, true, false, zero, succ, add.
+     including OCaml versions of bool, true, false, zero, succ, and pred.
+     It's especially useful to do a version of pred, starting with one
+     of the (untyped) versions available in the lambda library
+     accessible from the main wiki page.  The point of the excercise
+     is to do these things on your own, so avoid using the built-in
+     OCaml booleans and list predicates.
 
    Consider the following list type:
 
@@ -195,21 +200,15 @@ binary trees working in OCaml.
 
    As with nats, recursion is built into the datatype.
 
-   We can write functions like map:
+   We can write functions like head, isNil, and map:
 
     map : (σ → τ ) → σ list → τ list
-      := λf :σ → τ. λl:σ list. l [τ list] nilτ (λx:σ. λy:τ list. consτ (f x) y
 
-   **Excercise** convert this function to OCaml.  Also write an `append` function.
-   Test with simple lists.
+   We've given you the type for map, you only need to give the term.
 
-   Consider the following simple binary tree type:
+   With regard to `head`, think about what value to give back if the
+   argument is the empty list.  Ultimately, we might want to make use
+   of our `'a option` technique, but for this assignment, just pick a
+   strategy, no matter how clunky. 
 
-    type ’a tree = Leaf | Node of ’a tree * ’a * ’a tree
-
-   **Excercise**
-   Write a function `sumLeaves` that computes the sum of all the
-   leaves in an int tree.
-
-   Write a function `inOrder` : τ tree → τ list that computes the in-order traversal of a binary tree. You
-   may assume the above encoding of lists; define any auxiliary functions you need.
+   Please provide both the terms and the types for each item.