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 well-typed in OCAML? +1. Which of the following expressions is well-typed 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 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;Â deï¬neÂ anyÂ auxiliaryÂ functionsÂ youÂ need. + Please provide both the terms and the types for each item. -- 2.11.0