PS7: Resistance is Futile. You Will Be SMLated.
)
 PS7 includes both regular problems on SML and two of solo problems in Racket. A third solo problem involving PostFix was cancelled.
 Dueish: Tuesday, Nov. 21. Try to get as much of this pset done as you can before Thanksgiving break.
Do the SML parts first!  Notes:
 This pset has 93 total points:
 It has two solo problems worth 33 points. All solo problems use Racket, not SML.
 It has two regular problems worth 60 points on SML programming, through sumofproduct datatypes.
 It is strongly recommended that you complete the regular SML problems before the Racket solo problems so that you are better prepared for the SML material in class for the rest of the semester.
 Do not attempt the solo problems until you have studied the solutions from PS4 through PS6.
 This pset has 93 total points:
 Submission:
 In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS7.
 At the top of your yourFullName CS251 PS7 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 PS7 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 answer to 2b in your PS7 google doc.
 Be sure that the function definitions you wrote for these problems in
yourAccountNameps7solo.rkt
andyourAccountNameps7solopostfix.rkt
also appear in your Google Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps7solo.rkt
andyourAccountNameps7solopostfix.rkt
in your~/cs251/drop/ps07
drop folder oncs.wellesley.edu
.
 For Problems 4 and 5:
 Include the SML code from
yourAccountNameps7holo.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/ps7
folder in your~/cs251/drop/ps07
drop folder oncs.wellesley.edu
by executing the following (replacinggdome
by your cs server username):scp r ~wx/cs251/sml/ps7 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps07
 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 ps7solostarter.rkt, which you should rename to yourAccountNameps7solo.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
genlistapply
function we defined in class (it is one of your given helper functions), it is possible to define a functionfactorsgenlistapply
that behaves likefactorsrec
for every positive integer input. Flesh out the following skeleton offactorsgenlistapply
. You may useleastdivisorrec
in your definition.(define (factorsgenlistapply num) (map second (genlistapply ; 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 (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply 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 yourAccountNameps7solo.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: PostFix Tuples (17 points)
 This problem was cancelled.
4. Higherorder List Operators in SML (30 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.

range
,digitsToDecimal
,cartesianProduct
,partition
(10 points). Translate the following Racket functionsrange
,digits>decimal
,cartesianproduct
, andpartition
into corresponding SML functions namedrange
,digitsToDecimal
,cartesianProduct
, andpartition
functions:(define (range lo hi) (if (<= hi lo) null (cons lo (range (+ 1 lo) hi)))) (define (digits>decimal digits) (foldl (λ (digit sum) (+ (* 10 sum) digit)) 0 digits)) (define (cartesianproduct xs ys) (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys) subres)) null xs)) (define (partition pred xs) (foldr (λ (x twolists) (if (pred x) (list (cons x (first twolists)) (second twolists)) (list (first twolists) (cons x (second twolists))))) (list '() '()) xs))
For example:
val range = fn : int > int > int list val digitsToDecimal = fn : int list > int val cartesianProduct = fn : 'a list > 'b list > ('a * 'b) list val partition = fn : ('a > bool) > 'a list > 'a list * 'a 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  digitsToDecimal '(2 5 1)  digitsToDecimal '(1 7 2 9)  digitsToDecimal (range 0 10); val it = 123456789 : int  digitsToDecimal [] val it = 0 : int  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  partition (fn x => x mod 2 = 0) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([4,2,8,6],[7,5,1,9,3]) : int list * int list  partition (fn x => x < 4) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([2,1,3],[4,7,8,5,9,6]) : int list * int list  partition (fn x => x > 0) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([4,2,7,8,5,1,9,3,6],[]) : int list * int list
Notes:

In this and the following parts of this problem, write all of your SML code in a new file named
yourAccountNameps7holo.sml
that is within the~wx/cs251/sml/ps7
folder on your wx virtual machine. 
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 the SML lectures. 
Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores (socalled ``snake case’’) or camel case. E.g.,
cartesianproduct
in Racket becomescartesian_product
orcartesianPrduct
in SML. Here and below, other name changes are also required due to limitations in SML identifiers; e.g.,>
indigits>decimal
is converted toTo
. 
Be careful with your explicit parentheses in SML. Many type errors in SML programs come from incorrectly parenthesizing expressions.

foldr
,foldl
,map
, andList.filter
are all built into SML:val foldr = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val foldl = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val map = fn: ('a > 'b) > 'a list > 'b list  List.filter; val it = fn : ('a > bool) > 'a list > 'a list
Note that
List.filter
requires the explicit module prefixList.
, while the other functions do not. Go figure! 
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
,keepBiggerThanNext
,foldrTernop
, andkeepBiggerThanSomeFollowing
(10 points) Translate the following Racket functionsallcontainmultiple?
,keepbiggerthannext
,foldrternop
, andkeepbiggerthansomefollowing
into corresponding SML functions nameddoAllContainMultple
,keepBiggerThanNext
,foldrTernop
, andkeepBiggerThanSomeFollowing
:(define (allcontainmultiple? m nss) (forall? (lambda (ns) (exists? (lambda (n) (divisibleby? n m)) ns)) nss)) (define (keepbiggerthannext nums) (if (null? nums) '() (map car (filter (λ (pair) (> (car pair) (cdr pair))) (zip nums (rest nums)))))) (define (foldrternop ternop nullval xs) (if (null? xs) nullval (ternop (first xs) (rest xs) (foldrternop ternop nullval (rest xs))))) (define (keepbiggerthansomefollowing nums) (foldrternop (λ (fstNum rstNums bigs) (if (exists? (λ (n) (> fstNum n)) rstNums) (cons fstNum bigs) bigs)) '() nums))
For example:
val doAllContainMultiple = fn : int > int list list > bool val keepBiggerThanNext = fn : int list > int list val foldrTernop = fn : ('a * 'a list * 'b > 'b) > 'b > 'a list > 'b val keepBiggerThanSomeFollowing = fn : int list > int list  doAllContainMultiple 5 [[17,10,2],[25],[3,8,5]]; val it = true : bool  doAllContainMultiple 2 [[17,10,2],[25],[3,8,5]]; val it = false : bool  doAllContainMultiple 3 []; val it = true : bool  keepBiggerThanNext [6, 1, 4, 7, 2, 5, 9, 8, 3]; val it = [6,7,9,8] : int list  keepBiggerThanNext [9,7,8,6,4,5,3,1,2]; val it = [9,8,6,5,3] : int list  keepBiggerThanNext (range 0 20); val it = [] : int list  keepBiggerThanSomeFollowing [6, 1, 4, 7, 2, 5, 9, 8, 3]; val it = [6,4,7,5,9,8] : int list  keepBiggerThanSomeFollowing [9,7,8,6,4,5,3,1,2]; val it = [9,7,8,6,4,5,3] : int list  keepBiggerThanSomeFollowing (range 0 20); val it = [] : int list
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 inallcontainmultiple?
todoAllContainMultiple
. 
The
List.
andListPair.
indicate that these functions come from modules. Here is documentation on theList
module, and here is documentation on theListPair
module. 
In
keepBiggerThanNext
andfoldrTernop
, rather than usingList.null nums
ornums = []
to check for an empty list andList.hd
andList.tl
to extract the parts of a list, you should instead use pattern patching to to distinguish empty and nonempty lists and find the parts of a nonempty list. Here’s a simple example that illustrates such pattern matching:fun mapScale factor [] = []  mapScale factor (num::nums) = (factor * num) :: (mapScale factor nums)


genlist
,partialSumsTable
,iterate
, andfibPairs
(10 points). Translate the following Racket functionsgenlistapply
,partialsumstable
,iterateapply
, andfibpairs
functions into SML functions namdedgenlist
,partialSumsTable
,iterate
, andfibPairs
:(define (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply next seed))))) (define (partialsumstable ns) (genlistapply (λ (nums ans) (list (rest nums) (+ (first nums) ans))) (λ (nums ans) (null? nums)) #t (list ns 0))) (define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state)))) (define (fibpairs threshold) ;; returns a list of pairs (a, b) used to calculate Fibonacci iteratively ;; until b is greater than or equal to the given threshold (iterateapply (λ (a b pairs) (list b (+ a b) (cons (cons a b) pairs))) (λ (a b pairs) (>= b threshold)) (λ (a b pairs) (reverse (cons (cons a b) pairs))) '(0 1 ())))
For example:
val genlist = fn : ('a > 'a) > ('a > bool) > bool > 'a > 'a list val pairs_genlist = fn : int > (int * int) list val iterate = fn : ('a > 'a) > ('a > bool) > ('a > 'b) > 'a > 'b val fibPairs = 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 (* Return the first sum of powers of 3 that's greater than 100 *)  iterate (fn (power, sum) => (3*power, power+sum)) = (fn (power, sum) => sum > 100) = (fn (power, sum) => sum) = (1, 0); val it = 121 : int (* = 1 + 3 + 9 + 27 + 81 *)  fibPairs 10; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13)] : (int * int) list  fibPairs 50; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55)] : (int * int) list  fibPairs 100; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55),(55,89), (89,144)] : (int * int) list
Notes:

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

Use pattern matching on tuples when translating the
(λ (nums ans) ...)
and(λ (a b pairs) ...)
functions. Translate these to(fn (nums,ans) => ...)
and (fn (a,b,pairs) => …). Because of SML’s builtin pattern matching, in SML it is unnecessary to have a separate function like Racket’sgenlistapply
anditerateapply
(as distinct fromgenlist
anditerate
) in SML since the function arguments in SML’sgenlist
anditerate
can already do pattern matching.

5. 23 Trees (30 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/ps7
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/ps7
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/ps7
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
(5 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
(18 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?