PS6: Resistance is Futile. You Will Be SMLated.
)
 Dueish: Friday, Mar 24. Try to get as much of this pset done as you can before Spring break.
 Notes:
 This pset has 100 total points.
 This pset contains three solo problems worth 50 points. All solo problems use Racket, not SML.
 Do not attempt the solo problems until you have studied the solutions from PS4 and PS5.
 It is recommended that you do the SML problems before the Racket solo problems so that you can ask questions when you get stuck.
 Submission:
 In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS6.
 At the top of your yourFullName CS251 PS6 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
 For all parts of all problems, include all answers (including Racket and SML code) in your PS6 google doc. Format Racket and SML code using a fixedwidth font, like Consolas or Courier New. You can use a small font size if that helps.
 For Problems 1, 2, 3 (the solo problems):
 Include the boxandpointer diagram from 2a and your answers to 2b and 3a in your PS6 google doc.
 Be sure that the function definitions you wrote for these problems
yourAccountNameps6solo.rkt
also appear in your Google Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps6solo.rkt
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 For Problems 4 and 5:
 Include the SML code from
yourAccountNameps6holo.sml
in your Google Doc (so that I can comment on them).  Include the SML code from
yourAccountNameTTTreeFuns.sml
in your Google Doc (so that I can comment on them). 
Drop a copy of your
~wx/cs251/sml/ps6
folder in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
by executing the following (replacinggdome
by your cs server username):scp r ~wx/cs251/sml/ps6 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps06
 Include the SML code from
1. Solo Problem: It’s a Factor (16 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
Begin this problem by downloading this starter file ps6solostarter.rkt, which you should rename to yourAccountNameps6solo.rkt
. This file contains provided definitions for Solo Problems 1, 2, and 3. Add your definitions for Problems 1, 2, and 3 to this file.
The following leastdivisorrec
function correctly returns the least positive integer that evenly divides the given positive integer num
.
(define (leastdivisorrec num) ;; Assume num is a postive integer
(let ((limit (ceiling (sqrt num)))) ;; The largest divisor to be tested
(define (searchfordivisor candidate)
(if (> candidate limit)
num
(if (divisibleby? num candidate)
candidate
(searchfordivisor (+ candidate 2)))))
(if (divisibleby? num 2)
2
(searchfordivisor 3))))
(define (divisibleby? num divisor)
(= (remainder num divisor) 0))
We can use map
with range
to test leastdivisorrec
on many inputs:
> (map (λ (n) (list n (leastdivisorrec n))) (range 45 56))
'((45 3) (46 2) (47 47) (48 2) (49 7) (50 2) (51 3) (52 2) (53 53) (54 2) (55 5))
Using leastdivisorrec
, we can define a function factorsrec
that returns a list of all primes factors of a given positive integer, sorted from low to high:
(define (factorsrec num)
(let ((factor (leastdivisorrec num)))
(if (= factor num)
(list factor)
(cons factor (factorsrec (quotient num factor))))))
> (map (λ (n) (list n (factorsrec n))) (range 60 73))
'((60 (2 2 3 5))
(61 (61))
(62 (2 31))
(63 (3 3 7))
(64 (2 2 2 2 2 2))
(65 (5 13))
(66 (2 3 11))
(67 (67))
(68 (2 2 17))
(69 (3 23))
(70 (2 5 7))
(71 (71))
(72 (2 2 2 3 3)))

(3 points) Using
factorsrec
in conjunction with the higherorderforall?
function defined in PS4 (it is one of your given helper functions), it is possible to give a very simple definition of thehamming?
function from PS2. Flesh out this skeleton ofhamming?
:(define (hamming? num) (and (integer? num) (> num 0) (or (= num 1) (forall? ; put expression 1 here ; put expression 2 here )) )) > (filter hamming? (range 0 101)) '(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100)
Recall that
forall?
is defined as follows:(define (forall? pred xs) (if (null? xs) #t (and (pred (car xs)) (forall? pred (cdr xs)))))

(4 points) Using the higherorder
find
function defined in PS4 (it is one of your given helper functions), it is possible to define a functionleastdivisorfind
that searches through the same candidates to return the same answer asleastdivisorrec
for every positive integer input. Flesh out this skeleton ofleastdivisorfind
:(define (leastdivisorfind num) (find ; put expression 1 here ; put expression 2 here ; put expresion 3 here )) > (map (λ (n) (list n (leastdivisorfind n))) (range 45 56)) '((45 3) (46 2) (47 47) (48 2) (49 7) (50 2) (51 3) (52 2) (53 53) (54 2) (55 5))
Notes:

Recall that
find
is defined as follows:(define (find pred notfound xs) (if (null? xs) notfound (if (pred (car xs)) (car xs) (find pred notfound (cdr xs)))))

Your definition of
leastdivisorfind
should should perform thedivisibleby?
test on exactly the same candidates asleastdivisorrec
. 
For generating candidate divisors, it is helpful to know that the Racket
range
function (like the Pythonrange
function) takes an optional thirdstep
argument that is added to the current number to determine the next one. (The default step is 1.) For example:> (range 1 20 3) '(1 4 7 10 13 16 19)

(leastdivisorfind n)
may take time proportional to the square root of n, even in cases whereleastdivisorrec
would return after a small number of steps (e.g., when n is an even number.) This is because it will create a list whose length is the square root of n even if it does not examine all the elements of that list. 
You are not allowed to use
factorsrec
in your definition ofleastdivisorrec
.


(4 points) Using the higherorder
genlist
function we defined in class (it is one of your given helper functions), it is possible to define a functionfactorsgenlist
that behaves likefactorsrec
for every positive integer input. Flesh out the following skeleton offactorsgenlist
. You may useleastdivisorrec
in your definition. [2017/05/04] This previously had only 3 expressions to be filled in, but really needs 4. The 3rd expression is forkeepdonevalue?
, which was missing in the previous version.(define (factorsgenlist num) (map second (genlist ; put expression 1 here ; put expression 2 here ; put expression 3 here (list num ; put expression 4 here )))) > (map (λ (n) (list n (factorsgenlist n))) (range 60 73)) '((60 (2 2 3 5)) (61 (61)) (62 (2 31)) (63 (3 3 7)) (64 (2 2 2 2 2 2)) (65 (5 13)) (66 (2 3 11)) (67 (67)) (68 (2 2 17)) (69 (3 23)) (70 (2 5 7)) (71 (71)) (72 (2 2 2 3 3)))
Recall that genlist is defined as:
(define (genlist next done? keepDoneValue? seed) (if (done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlist next done? keepDoneValue? (next seed)))))

(5 points) Using the higherorder
iterateapply
function we defined in class (it is one of your given helper functions), it is possible to define a functionfactorsiterateapply
that behaves likefactorsrec
for every positive integer input. Flesh out the following skeleton offactorsiterateapply
. You may useleastdivisorrec
andreverse
in your definition.(define (factorsiterateapply num) (iterateapply ; put expression 1 here ; put expression 2 here ; put expression 3 here (list num null))) > (map (λ (n) (list n (factorsiterateapply n))) (range 60 73)) '((60 (2 2 3 5)) (61 (61)) (62 (2 31)) (63 (3 3 7)) (64 (2 2 2 2 2 2)) (65 (5 13)) (66 (2 3 11)) (67 (67)) (68 (2 2 17)) (69 (3 23)) (70 (2 5 7)) (71 (71)) (72 (2 2 2 3 3)))
Recall that
iterateapply
is defined as:(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))
2. Solo Problem: Partial Reverses (17 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
In this problem, you will extend the yourAccountNameps6solo.rkt
you created in Problem 1. This problem concerns one of the provided functions in that file:

(5 points) Consider the following
partialreverses
function. Draw a boxandpointer diagram of the list that results from the invocation(partialreverses '(1 2 3 4))
. Use the style of diagram shown in PS3 Problem 2. Study the code carefully and be sure to accurately show all sharing between cons cells in your diagram.(define (partialreverses xs) (partialreversestail xs '() '())) (define (partialreversestail ys rev listrev) (if (null? ys) (cons rev listrev) (partialreversestail (rest ys) (cons (first ys) rev) (cons rev listrev) )))
Note: As an example of sharing in boxandpointer diagrams, consider
(define numList '(7 2 4)) (define listOfNumLists (list (append numList (rest numList)) numList (rest numList)))
The result has 9 cons cells arranged as follows:
However, if we just enter the printed representation
'((7 2 4 2 4) (7 2 4) (2 4))
forlistOfNumLists
, that would create 13 cons cells: 
(2 points) How many cons cells would there be in the result of
(partialreverses (range 1 1001))
? 
(5 points) Complete the following definition of
partialreversesiterate
so that it usesiterateapply
to iteratively calculate the same result (including sharing) aspartialreverses
:(define (partialreversesiterate xs) (iterateapply ; expression1 ; expression2 ; expression3 ; expression4 ))
In your expressions, the only functions you may use are
list
,cons
,first
,rest
,null
, andnull?
.Recall that
iterateapply
is defined as follows:(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))

(5 Points) Complete the following definition of
partialreversesfoldl
so that it usesfoldl
to iteratively calculate the same result (including sharing) aspartialreverses
:(define (partialreversesfoldl xs) (foldl ; expression1 ; expression2 xs))
In your expressions, the only functions you may use are
list
,cons
,first
, andnull
.
3. Solo Problem: Diagonal Pairs (17 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
In this problem, you will extend the yourAccountNameps6solo.rkt
you created in Problem 1. This problem concerns one of the provided functions in that file:
(define (diagonalpairs n) ; Assume is n a nonnegative integer
(foldr append null
(map (λ (sum)
(map (λ (fst) (cons fst ( sum fst)))
(range 0 (+ sum 1))))
(range 0 (+ n 1)))))

(3 points) The
diagonalpairs
function generates a list of pairs of integers related to inputn
, in a very particular order. Carefully describe in English the output list of pairs in terms ofn
. As in PS5 Problem 4a, do not describe the Racket code or algorithm that generates the pairs. Instead, specify (1) exactly what pairs are in the output list (in a general way, not giving examples) and (2) exactly what order the pairs are in. Your description must be precise enough that someone else could implement thediagonalpairs
function correctly based on your description, without seeing the original Racket definition. 
(6 points) Recall the
genlist
function from lecture (which is supplied as a helper function inyourAccountNameps6solo.rkt
).(define (genlist next done? keepDoneValue? seed) (if (done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlist next done? keepDoneValue? (next seed)))))
In the file
yourAccountNameps6solo.rkt
, define a Racket functiondiagonalpairsgenlist
that has the same inputoutput behavior asdiagonalpairs
but is defined usinggenlist
by fleshing out the missing expressions in curly braces in the following skeleton:(define (diagonalpairsgenlist n) ; Assume is n a nonnegative integer (genlist {next function goes here} {done? function goes here} {keepDoneValue? boolean goes here} {seed goes here}))

(8 points) In the file
yourAccountNameps6solo.rkt
, define a tailrecursive Racket functiondiagonalpairsiter
that has the same inputoutput behavior asdiagonalpairs
but is defined iteratively using tailrecursive helper functions. Unlike thediagonalpairsgenlist
function, which add pairs from the front of the list to the end, yourdiagonalpairsiter
implementation should add pairs from the end of the list to the beginning.For full credit, your definition should flesh out this exact skeleton:
(define (diagonalpairsiter n) ; Assume is n a nonnegative integer (define (outertail {outerparameters}) (define (innertail {innerparameters}) {innerbody}) ; call inner_tail and outertail tailrecursively in innerbody {outerbody) ; call inner_tail tailrecursively in outerbody (outertail ...)
Substantial partial credit can be earned for other iterative solutions that use tail recursion, such as solutions that use a single tailrecursive helper function.
Notes:

You should not use
iterate
oriterateapply
in this problem! Instead, you should define one or more tailrecursive functions specialized for this particular problem. 
You should not perform any list reversals in your
diagonalpairsiter
definition. 
The
diagonalpairsiter
function need not itself be recursive; it can call one or more tailrecursive functions. 
As in PS5 Problem 4d, it may be helpful to use iteration tables involving concrete examples to help you define your tail recursive function(s).

4. Higherorder List Operators in SML (25 points)
In this problem, you will revisit several of the higherorder list operators we have studied in Racket in the context of SML. Since you are already familiar with these operators, your focus in this problem is on SML syntax and typechecking, rather than on the operators themselves.
Write all of your SML code in a new file named yourAccountNameps6holo.sml
.

range
,alts
,cartesianProduct
(9 points) Translate the following Racketrange
,alts
, andcartesianproduct
functions into SMLrange
,alts
, andcartesianProduct
functions:(define (range lo hi) (if (<= hi lo) null (cons lo (range (+ 1 lo) hi)))) (define (alts xs) (foldr (λ (x subResult) (list (cons x (second subResult)) (first subresult))) (list '() '()) xs (define (mycartesianproduct xs ys) (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys) subres)) null xs))
For example:
val range = fn : int > int > int list val alts = fn : 'a list > 'a list * 'a list val cartesianProduct = fn : 'a list > 'b list > ('a * 'b) list  range 0 10; val it = [0,1,2,3,4,5,6,7,8,9] : int list  range 3 8; val it = [3,4,5,6,7] : int list  range 5 5; val it = [] : int list  range 1 100; val it = [1,2,3,4,5,6,7,8,9,10,11,12,...] : int list  Control.Print.printLength := 100;  val it = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28, 29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53, 54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78, 79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99] : int list  alts [7, 5, 4, 6, 9, 2, 8, 3]; val it = ([7,4,9,8],[5,6,2,3]) : int list * int list  alts (range 0 20); val it = ([0,2,4,6,8,10,12,14,16,18],[1,3,5,7,9,11,13,15,17,19]) : int list * int list  cartesianProduct [1,2,3,4] ["a", "b", "c"]; val it = [(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c"), (4,"a"),(4,"b"),(4,"c")] : (int * string) list  cartesianProduct ["a", "b", "c"] [1,2,3,4]; val it = [("a",1),("a",2),("a",3),("a",4),("b",1),("b",2),("b",3),("b",4),("c",1), ("c",2),("c",3),("c",4)] : (string * int) list
Notes:

You should do all your SML programming in Emacs within the
wx
virtual machine appliance. 
If you haven’t done so already, read these notes on SML/NJ and Emacs SML Mode and follow the advice there. In particular, it is strongly recommended that you create an SML interpreter within a
*sml*
buffer in Emacs. Then you can useMp
andMn
to avoid retyping your test expressions. 
In all of your SML programming, do not use
#1
,#2
, etc. to extract tuple components orList.hd
,List.tl
, orList.null
to decompose and test lists. Instead, use pattern matching on tuples and lists, as illustrated in examples from lecture. 
Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores or camel case. E.g.,
cartesianproduct
in Racket becomescartesian_product
orcartesianPrduct
in SML. 
Be careful with your explicit parentheses in SML. Many type errors in SML programs come from incorrectly parenthesizing expressions.

foldr
,map
are both built into SML:val foldr = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val map = fn: ('a > 'b) > 'a list > 'b list

Racket’s
append
translates to SML’s infix@
operator, but when you want to pass it as an argument to a firstclass function you write it asop@
. 
In this entire problem (not just this part) some instances of Racket’s
cons
will translate to SML’s infix listprepending operator::
, while others will translate to the tupling notation(<exp1>, <exp2>)
for pair creation. Reason about SML types to figure out which to use when. SML’s type checker will yell at you if you get it wrong. 
In this entire problem (not just this part) some instances of Racket’s
list
will translate to SML’s lists while others will translate to SML’s tuples. Again, reason about SML types to figure out which to use when. 
Control.Print.printLength
controls how many list elements are displayed; after this number, ellipses are used. For example: Control.Print.printLength := 5; val it = () : unit  range 0 20; val it = [0,1,2,3,4,...] : int list  Control.Print.printLength := 20; val it = () : unit  range 0 20; val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] : int list
Another such control is
Control.Print.printDepth
, which controls printing in nested lists. You won’t need that here, but will in Problem 5.


allContainMultiple
andisSorted
(8 points) Translate the following Racketallcontainmultiple?
andsorted?
functions into SMLdoAllContainMultple
andisSorted
functions:(define (allcontainmultiple? m nss) (forall? (lambda (ns) (exists? (lambda (n) (divisibleby? n m)) ns)) nss)) (define (sorted? ns) (if (null ns) #t ; special case to avoid (rest ns) below (forall? (λ (pair) (<= (car pair) (cdr pair))) (zip ns (rest ns)))))
For example:
 allContainMultiple 5 [[17,10,2],[25],[3,8,5]]; val it = true : bool  allContainMultiple 2 [[17,10,2],[25],[3,8,5]]; val it = false : bool  allContainMultiple 3 []; val it = true : bool  isSorted [7,4,2,5,4,6]; val it = false : bool  isSorted [2,3,3,5,6,7]; val it = true : bool  isSorted [2]; val it = true : bool  isSorted []; val it = true : bool  isSorted (range 0 1000); val it = true : bool  isSorted ((range 0 1000) @ [1001,1000]); val it = false : bool
Notes:

SML includes the following analogs of
forall?
,exists?
, andzip
that you should use in your definitions: List.all; val it = fn : ('a > bool) > 'a list > bool  List.exists; val it = fn : ('a > bool) > 'a list > bool  ListPair.zip; val it = fn : 'a list * 'b list > ('a * 'b) list

Because SML does not allow
?
in identifiers, Racket names containing?
need to be be transformed, as insorted?
toisSorted

The
List.
andListPair.
indicate that these functions come from modules. Here is documentation on theList
module, and here is documentation on theListPair
module.


genlist
(8 points) Translate the following Racketgenlist
andpartialsumstable
functions into SMLgenlist
andpartialSumsTable
functions:(define (genlist next done? keepDoneValue? seed) (if (done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlist next done? keepDoneValue? (next seed))))) (define (partialsumstable ns) (genlist (λ (nums&ans) (list (rest (first nums&ans)) (+ (first (first nums&ans)) (second nums&ans)))) (λ (nums&ans) (null? (first nums&ans))) #t (list ns 0)))
For example:
val genlist = fn : ('a > 'a) > ('a > bool) > bool > 'a > 'a list val pairs_genlist = fn : int > (int * int) list  genlist (fn n => n * 2) (fn n => n > 1000) true 1; val it = [1,2,4,8,16,32,64,128,256,512,1024] : int list  genlist (fn n => n * 2) (fn n => n > 1000) false 1; val it = [1,2,4,8,16,32,64,128,256,512] : int list  partialSumsTable [7, 2, 5, 8, 4]; val it = [([7,2,5,8,4],0),([2,5,8,4],7),([5,8,4],9),([8,4],14),([4],22),([],26)] : (int list * int) list  partialSumsTable (range 1 11); val it = [([1,2,3,4,5,6,7,8,9,10],0),([2,3,4,5,6,7,8,9,10],1),([3,4,5,6,7,8,9,10],3), ([4,5,6,7,8,9,10],6),([5,6,7,8,9,10],10),([6,7,8,9,10],15),([7,8,9,10],21), ([8,9,10],28),([9,10],36),([10],45),([],55)] : (int list * int) list
Notes:

SML does not allow
?
in identifiers, so translatedone?
tois_done
orisDone
and similarly withkeepDoneValue?

An earlier version of this pset had an incorrect type for genlist that was missing the type for the bool argument::
val genlist = fn : ('a > 'a) > ('a > bool) > 'a > 'a list
The correct type for genlist is:
val genlist = fn : ('a > 'a) > ('a > bool) > bool > 'a > 'a list
Thanks to Naomi Day for catching this bug.

Use pattern matching on tuples when translating the
(λ (nums&ans) ...)
functions. Translate these to(fn (nums,ans) => ...)
. Because of SML’s builtin pattern matching, in SML it is unnecessary to have a separate function like Racket’siterateapply
in SML since the function arguments in SML’sgenlist
can already do pattern matching.

5. 23 Trees (25 points)
In this problem you will use SML to implement aspects of 23 trees, a particular search tree data structure that is guaranteed to be balanced.
Begin by skimming pages 1 through 7 of this handout on 23 trees. (I create this handout for CS230 in Fall, 2004, but we no longer teach 23 trees in that course).
In a 23 tree, there are three kinds of nodes: leaves, 2nodes, and 3nodes. Together, these can be expressed in SML as follows:
datatype TTTree = (* 23 tree of ints *)
L (* Leaf *)
 W of TTTree * int * TTTree (* tWo node *)
 H of TTTree * int * TTTree * int * TTTree (* tHree node *)
For simplicity, we will only consider 23 trees of integers, though they can be generalized to handle any type of value.
For conciseness in constructing and displaying large trees, the three constructors have singleletter names. For example, below are the pictures of four sample 23 trees from the handout and how they would be expressed with these constructors:
val t1 = W( W(W(L,1,L), 2, W(L,3,L)), 4, W(W(L,5,L), 6, W(L,7,L)))
val t2 = H( W(L,1,L), 2, H(L,3,L,4,L), 5, H(L,6,L,7,L))
val t3 = H( H(L,1,L,2,L), 3, W(L,4,L), 5, H(L,6,L,7,L))
val t4 = H( H(L,1,L,2,L), 3, H(L,4,L,5,L), 6, W(L,7,L))
As explained in the handout on 23 trees, a 23 tree is only valid it it satisfies two additional properties:
 The ordering property:
 In a 2node with left subtree l, value X, and right subtree r, (all values in l) ≤ X ≤ (all values in r).
 In a 3node with left subtree l, left value X, middle subtree l, right value Y, and right subtree r, (all values in l) ≤ X ≤ (all values in m) ≤ Y ≤ (all values in r).
 The height property (called path length invariant in the handout): in a 2node or 3node, the height of all subtrees must be exactly the same.
The height property guarantees that a valid 23 tree is balanced. Together, these two properties guarantee that a 23 tree is efficiently searchable.
Your ~wx/cs251/sml/ps6
folder includes the file TTTree.sml, which contains the TTTree
dataytype defined above as well as numerous examples of valid and invalid 23 trees that are instances of this datatype. Note that t
and vt
are used for valid trees, io
is used for invalidly ordered trees, and ih
is used for invalid height trees.
tree name  elements  ordered?  satisfies the height property? 

t1  [1,…,7]  Yes  Yes, with height 3 
t2  [1,…,7]  Yes  Yes, with height 2 
t3  [1,…,7]  Yes  Yes, with height 2 
t4  [1,…,7]  Yes  Yes, with height 2 
vt0  []  Yes  Yes, with height 0 
vt2  [1,2]  Yes  Yes, with height 1 
vt17  [1,…,17]  Yes  Yes, with height 3 
vt20  [1,…,20]  Yes  Yes, with height 4 
vt44  [1,…,44]  Yes  Yes, with height 5 
vt92  [1,…,92]  Yes  Yes, with height 6 
io2  [1,2]  No  Yes, with height 1 
io7  [1,…,7]  No  Yes, with height 2 
io17  [1,…,17]  No  Yes, with height 3 
io20  [1,…,20]  No  Yes, with height 4 
io44  [1,…,44]  No  Yes, with height 5 
io92  [1,…,92]  No  Yes, with height 6 
ih2  [1,2]  Yes  No 
ih7  [1,…,7]  Yes  No 
ih17  [1,…,17]  Yes  No 
ih20  [1,…,20]  Yes  No 
ih44  [1,…,44]  Yes  No 
ih92  [1,…,92]  Yes  No 
These trees are used to define two lists:
val validTrees = [vt0, vt2, t2, t3, t4, t1, vt17, vt20, vt44, vt92]
val invalidTrees = [io2, io7, io17, io20, io44, io92,
ih2, ih9, ih17, ih20, ih44, ih92]
In this problem you will (1) implement a validity test for 23 trees and (2) implement the effcient 23 insertion algorithm from the handout on 23 trees.
Your ~wx/cs251/sml/ps6
folder also includes the starter file TTTreeFuns.sml. In this file, flesh out the missing definitions as specified below. When you finish this problem, rename the file to yourAccountNameTTTreeFuns.sml
before you submit it.
Be sure to perform execute the following in a shell in your wx
appliance to get the ~wx/cs251/sml/ps6
folder:
cd ~/cs251/sml
git pull origin master

satisfiesOrderingProperty
(7 points)In this part, you will implement a function
satisfiesOrderingProperty: TTTree > bool
that takes an instance of theTTTree
datatype and returnstrue
if it satisfies the 23 tree ordering property andfalse
if it does not. An easy way to do this is to define two helper functions:elts: TTTree > int list
returns a list of all the elements of the tree in inorder — i.e., In a 2node with left subtree l, value X, and right subtree r, all values in l are listed before X, which is listed before all elements in r.
 In a 3node with left subtree l, left value X, middle subtree l, right value Y, and right subtree r, all values in l are listed before X, which is listed before all values in m, which are listed before Y , which is listed before all values in r.
isSorted: int list > bool
returnstrue
if the list of integers is in sorted order andfalse
otherwise.
For example:
 elts vt17; val it = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] : int list  elts io17; val it = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,16] : int list  isSorted(elts vt17); val it = true : bool  isSorted(elts io17); val it = false : bool
Using these two helper functions,
satisfiesOrderingProperty
can be implemented as:fun satisfiesOrderingProperty t = isSorted(elts t)
For example:
 map satisfiesOrderingProperty validTrees; val it = [true,true,true,true,true,true,true,true,true,true] : bool list  map satisfiesOrderingProperty invalidTrees; val it = [false,false,false,false,false,false,true,true,true,true,true,true] : bool list
Notes:

Once (and only once) execute
use "TTTree.sml";
to load the
TTTree
datatype and example trees. Then every time you change the fileTTTreeFuns.sml
, executeuse "TTTreeFuns.sml"

If you haven’t done so already, read these notes on SML/NJ and Emacs SML Mode and follow the advice there. In particular, it is strongly recommended that you create an SML interpreter within a
*sml*
buffer in Emacs. Then you can useMp
andMn
to avoid retyping your test expressions. 
You may need to execute
Control.Print.printLength := 100;
in order to see all the list elements. 
Implement
isSorted
using the same zipping approach you used in PS3. You do zipping in SML viaListPair.zip
from the ListPair module.List.all
from the List module is also helpful.

satisfiesHeightProperty
(6 points)In this part, you will implement a function
satisfiesHeightProperty: TTTree > bool
that takes an instance of theTTTree
datatype and returnstrue
if it satisfies the 23 tree height property andfalse
if it does not. An easy way to do this is to definesatisfiesHeightProperty
asfun satisfiesHeightProperty t = Option.isSome (height t)
where
Option.isSome
is a function from the Option module that determines if anoption
value is aSOME
(vs. aNONE
) andheight
is a function with typeTTTree > option int
such thatheight t
returnsSOME h
ift
satisfies the height property with heighth
and otherwise returnsNONE
.Implement the
height
function by fleshing out this skeleton:(* height: TTTree > int option *) fun height L = (* return an appropriate option value here *)  height (W(l, _, r)) = (case (height(l), height(r)) of (* put appropriate pattern clauses here *))  (* handle the H case here, similarly to the W case *)
For example:
 map height validTrees; val it = [SOME 0,SOME 1,SOME 2,SOME 2,SOME 2,SOME 3,SOME 3,SOME 4,SOME 5,SOME 6] : int option list  map height invalidTrees; val it = [SOME 1,SOME 2,SOME 3,SOME 4,SOME 5,SOME 6,NONE,NONE,NONE,NONE,NONE,NONE] : int option list
Notes:

It’s important to enclose the
case
expressions withinheight
in parens to distinguish the pattern clauses of thecase
expression from those of theheight
function definition. 
Once
height
is defined,satisfiesHeightProperty
is defined: map satisfiesHeightProperty validTrees; val it = [true,true,true,true,true,true,true,true,true,true] : bool list  map satisfiesHeightProperty invalidTrees; val it = [true,true,true,true,true,true, false,false,false,false,false,false] : bool list

Once both
satisfiesOrderingProperty
andsatisfiesHeightProperty
are defined, it is trivial to define a functionisValid: TTTree > bool
that returnstrue
if a given 23 tree is valid andfalse
otherwise.fun isValid t = satisfiesOrderingProperty t andalso satisfiesHeightProperty t  map isValid validTrees; val it = [true,true,true,true,true,true,true,true,true,true] : bool list  map isValid invalidTrees; val it = [false,false,false,false,false,false, false,false,false,false,false,false] : bool list


insert
(12 points) In this part, you will implement the insertion algorithm for 23 trees as described on pages 3 to 5 of the handout on 23 trees. You will not implement the special cases described on page 6 .The insertion algorithm is a recursive algorithm that uses the notion of a pseudo 2node that is “kicked up” in certain cases and handled specially in the upward phase of the recursion. To distinguish an insertion result that is a regular 23 tree from a pseudo 2node that is “kicked up”, we use the following datatype:
datatype InsResult = Tree of TTTree  KickedUp of TTTree * int * TTTree (* pseudo 2node "kicked up" from below *)
You will implement 23 tree insertion via a pair of functions:

(insert v t)
returns the newTTTree
that results from inserting a given intv
into a given treet
.insert
has typeint > TTTree > TTTree
. 
(ins v t)
is a helper function that returns the instance ofInsResult
that results from inserting a given intv
into a given treet
.ins
has typeint > TTTree > InsResult
.
Your implementation should flesh out the following code skeleton by turning the pictures on pages 3 to 5 from the handout on 23 trees into SML code.
(* insert: int > TTTree > TTTree *) fun insert v t = case ins v t of Tree t => t  KickedUp(l, w, r) => W(l, w, r) and (* "and" glues together mutually recursive functions *) (* ins: int > TTTree > InsResult *) ins v L = KickedUp (L, v, L)  ins v (W(l, X, r)) = if v <= X then (case ins v l of Tree l' => Tree(W(l', X, r))  KickedUp (l', w, m) => Tree(H(l', w, m, X, r))) else (* flesh this out *)  (* handle an H node similarly to the W node based on rules from the handout *)
Notes:

The
ins
function should only callins
recursively and should not callinsert
. 
An easy way to test
insert
is to call the followinglistToTTTree
function on a list of numbers generated byrange
. (These are already defined in your starter file.) Note that you may need to increase the print depth (viaControl.Print.printDepth := 100
) in order to see all the details of the printed trees:fun listToTTTree xs = foldl (fn (x,t) => insert x t) L xs fun range lo hi = if lo >= hi then [] else lo :: (range (lo + 1) hi)  listToTTTree (range 1 8); val it = W (W (W #,2,W #),4,W (W #,6,W #)) : TTTree  listToTTTree (range 1 17); val it = W (W (W #,4,W #),8,W (W #,12,W #)) : TTTree  Control.Print.printDepth := 100; val it = () : unit  listToTTTree (range 1 7); val it = H (W (L,1,L),2,W (L,3,L),4,H (L,5,L,6,L)) : TTTree  listToTTTree (range 1 18); val it = W (W (W (W (L,1,L),2,W (L,3,L)),4,W (W (L,5,L),6,W (L,7,L))),8, W (W (W (L,9,L),10,W (L,11,L)),12, H (W (L,13,L),14,W (L,15,L),16,W (L,17,L)))) : TTTree  listToTTTree (range 1 45); val it = W (W (W (W (W (L,1,L),2,W (L,3,L)),4,W (W (L,5,L),6,W (L,7,L))),8, W (W (W (L,9,L),10,W (L,11,L)),12,W (W (L,13,L),14,W (L,15,L)))),16, H (W (W (W (L,17,L),18,W (L,19,L)),20,W (W (L,21,L),22,W (L,23,L))),24, W (W (W (L,25,L),26,W (L,27,L)),28,W (W (L,29,L),30,W (L,31,L))),32, H (W (W (L,33,L),34,W (L,35,L)),36,W (W (L,37,L),38,W (L,39,L)),40, W (W (L,41,L),42,H (L,43,L,44,L))))) : TTTree

Unfortunately, inserting elements in sequential order as above tends to create 23 trees with almost all 2nodes and very few 3nodes. It turns out a better way is to mix up the order of insertion as is done in the following code for
makeTTTree
. This results in trees that have a good mix of 2nodes and 3nodes:(* Return list that has all ints in nums, but those not divisible by 3 come before those divisible by three *) fun arrangeMod3 nums = let val (zeroMod3, notZeroMod3) = List.partition (fn n => (n mod 3) = 0) nums in notZeroMod3 @ zeroMod3 end (* Make a 23 tree with elements from 1 up to and including size. Use arrangeMod3 to mix up numbers and lead to more 3nodes than we'd get with sorted integers lists *) fun makeTTTree size = listToTTTree (arrangeMod3 (range 1 (size + 1)))  makeTTTree 17; val it = H (W (W (L,1,L),2,H (L,3,L,4,L)),5,W (H (L,6,L,7,L),8,H (L,9,L,10,L)),11, H (H (L,12,L,13,L),14,W (L,15,L),16,W (L,17,L))) : TTTree  makeTTTree 44; val it = W (W (W (W (W (L,1,L),2,H (L,3,L,4,L)),5,W (H (L,6,L,7,L),8,H (L,9,L,10,L))), 11, W (W (H (L,12,L,13,L),14,H (L,15,L,16,L)),17, W (H (L,18,L,19,L),20,H (L,21,L,22,L)))),23, W (W (W (H (L,24,L,25,L),26,H (L,27,L,28,L)),29, W (H (L,30,L,31,L),32,H (L,33,L,34,L))),35, W (W (H (L,36,L,37,L),38,H (L,39,L,40,L)),41, W (W (L,42,L),43,W (L,44,L))))) : TTTree

Finally, to test your insertion implementation more extensively, try
(testInsert 1000)
with the following function, which will usemakeTTTree
to create 23 trees containing 0 elements to 1000 elements and warn you of any invalid trees.fun testInsert upToSize = let val pairs = map (fn n => (n, makeTTTree n)) (range 0 (upToSize + 1)) val (validPairs, invalidPairs) = List.partition (fn (_,t) => isValid t) pairs val wrongElts = List.filter (fn (n,t) => (elts t) <> (range 1 (n + 1))) validPairs in if (null invalidPairs) andalso (null wrongElts) then (print "Passed all test cases\n"; []) else if (not (null invalidPairs)) then (print "There are invalid trees in the following cases\n"; invalidPairs) else (print "The elements or element order is wrong in the following cases\n"; wrongElts) end  testInsert 1000; Passed all test cases val it = [] : (int * TTTree) list

Extra Credit: 23 Tree Deletion (20 points)
In SML, implement and test the 23 tree deletion algorithm presented in pages 8 through 11 of the handout on 23 trees.
Extra Credit: 23 Trees in Java (35 points)
Implement and test 23 tree insertion and deletion in Java. Compare the SML and Java implementations. Which features of which languages make the implementation easier and why?