From 90294e766ccb45391a5d5e9909a0720ed92cca60 Mon Sep 17 00:00:00 2001
From: Chris Barker
Date: Tue, 26 Oct 2010 11:23:33 0400
Subject: [PATCH] hw changes

assignment5.mdwn  47 +++++++++++++++++++++++
1 file changed, 23 insertions(+), 24 deletions()
diff git a/assignment5.mdwn b/assignment5.mdwn
index 4a4e06d2..cc714e90 100644
 a/assignment5.mdwn
+++ b/assignment5.mdwn
@@ 1,10 +1,10 @@
Assignment 5
Types and OCAML
+Types and OCaml

0. Recall that the S combinator is given by \x y z. x z (y z).
 Give two different typings for this function in OCAML.
+ Give two different typings for this function in OCaml.
To get you started, here's one typing for K:
# let k (y:'a) (n:'b) = y;;
@@ 13,7 +13,7 @@ Types and OCAML
 : int = 1
1. Which of the following expressions is welltyped in OCAML?
+1. Which of the following expressions is welltyped in OCaml?
For those that are, give the type of the expression as a whole.
For those that are not, why not?
@@ 72,8 +72,8 @@ Types and OCAML
The following expression is an attempt to make explicit the
behavior of `if``then``else` explored in the previous question.
The idea is to define an `if``then``else` expression using
other expression types. So assume that "yes" is any OCAML expression,
and "no" is any other OCAML expression (of the same type as "yes"!),
+other expression types. So assume that "yes" is any OCaml expression,
+and "no" is any other OCaml expression (of the same type as "yes"!),
and that "bool" is any boolean. Then we can try the following:
"if bool then yes else no" should be equivalent to
@@ 143,17 +143,17 @@ Baby monads
match x with None > None  Some n > f n;;
Booleans, Church numbers, and Church lists in OCAML
+Booleans, Church numbers, and Church lists in OCaml

These questions adapted from web materials written by some smart dude named Acar.
The idea is to get booleans, Church numbers, "Church" lists, and
binary trees working in OCAML.
+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:
@@ 180,8 +180,13 @@ binary trees working in OCAML.
encodingÂ above,Â theÂ resultÂ ofÂ thatÂ iterationÂ canÂ beÂ anyÂ typeÂ Î±,Â asÂ longÂ asÂ youÂ haveÂ aÂ baseÂ elementÂ zÂ :Â Î±Â and
aÂ functionÂ sÂ :Â Î±Â âÂ Î±.
 **Excercise**: get booleans and Church numbers working in OCAML,
 including OCAML versions of bool, true, false, zero, succ, add.
+ **Excercise**: get booleans and Church numbers working in OCaml,
+ 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 builtin
+ 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Â inorderÂ traversalÂ ofÂ aÂ binaryÂ tree.Â You
 mayÂ assumeÂ theÂ aboveÂ encodingÂ ofÂ lists;Â deï¬neÂ anyÂ auxiliaryÂ functionsÂ youÂ need.
+ Please provide both the terms and the types for each item.

2.11.0