Homework 08
Principles of Functional Programming代写 This homework will focus on the SML module system. By working with modules and writing them from scratch
Principles of Functional Programming Spring 2019
Out: Thursday, 28 March 2019
Due: Tuesday, 2 April 2019 at 23:59 EDT
0 Introduction Principles of Functional Programming代写
This homework will focus on the SML module system. By working with modules and writing them from scratch, you will hopefully better understand the relation- ship between signatures, structures, and functors, and the ways in which they can be meaningfully used.
0.1 Getting The Assignment
The starter files for the homework assignment have been distributed through our
git repository, as usual. To learn how to use it, read the documentation.
0.2 Collaboration
We have a homework collaboration policy.Principles of Functional Programming代写
In keeping with this policy, in the handout is a collab.txt file. In this file, please document your collaboration (in the manner specified in the course policy).
It is very important that you do this. If you appear to have collaborated with anyone not listed in your collab.txt file, this could be considered an academic integrity violation, and may result in disciplinary action.
0.3 Submission
Code submissions will be handled through Autolab and Gradescope.
To submit your code asignment, SSH into the unix andrew servers, and navigate to the hw/08 directory of the git repo. You can then run make submit and follow the prompts. It should make a .tar file containing your code, and submit it to Autolab. Please go to the Autolab webpage (linked above) and review the results of the checkscript (described below) and make sure your work was submitted properly. Please get help from the course staff immediately if this does not work for you.Principles of Functional Programming代写
When you upload your code submission to Autolab, the Autolab handin script will do some basic checks on your submission: making sure that the file names are correct, making sure that no files are missing, making sure that your code compiles cleanly. You can view the results of the handin script by clicking the number (usually either 41297.0 or 0.0) corresponding to the “check” section of your latest handin on the “Handin History” page. If this number is 41297.0, your submission failed the check script; if it is 0.0, it passed. Note that the handin script is not a grading script. If you passed the handin script, then your code will be graded, but will not necessarily receive full credit.
Your Autolab submission must contain all the code that you want to have graded for this assignment,
and must compile cleanly in Autolab. We reserve the right to penalize or not grade any submission which does not pass the handin script, which does not compile on Autolab, or which does not obey the instructions in the handout.
Please submit your written solutions to Gradescope. Note that we only accept submissions in typed PDF form. We reserve the right to not grade your submission if you submit handwritten work or other formats besides PDF (e.g. MS Word files, images, etc.). When you submit, you will be asked to indicate which page of your submission each problem occurs on. Please put each problem on its own page, and use Gradescope to indicate which page the problem occurs on. If we cannot find your problem quickly, we reserve the right to not grade it.
Please contact course staff if you have any questions. If you attempt to contact us close to the deadline, please be aware that we may not be able to respond before the deadline.Principles of Functional Programming代写
0.4 Due Date
This assignment is due on Tuesday, 2 April 2019 at 23:59 EDT. Remember that you have a total of three late days this semester.
1 Hype for Types Principles of Functional Programming代写
Task 1.1 (1 pts).
What is the type of x in the following code? If it is not well-typed, explain why not.
Task 1.2 (8 pts).
State whether the following declarations/definitions belong in a structure, belong in a signature, or could be found in both.
- val x :int
- val x =10
- typet
- type t =int
- exceptionE
- exception I ofint
- datatype t = Foo of int | Bar of bool
- fun f x = x +10
Task 1.3 (2 pts).
Does this piece of code typecheck? If so, give the type of y. If not, explain why not.
2 Filesystems
A filesystem is a data structure that keeps track of and controls access and navi- gation to files stored on a disk. The filesystem keeps track of the nesting structure of directories and the files inside them. Though there are many low level details involved in the implementation of all practical file systems, at a high level, a file system is just a tree. At the nodes of this tree are directories, and at the leaves are ordinary files. For example, if there are two directories in my home directory, 15150 and memes, and the 15150 directory contains homeworks and labs, and the memes directory contains surprised-pikachu.jpg, then this can be represented as a tree:
More often, these trees are written in “filesystem tree” format as
In this assignment, you’ll be creating a filesystem that can store, create, and delete files and directories, edit files, and navigate up and down between directories. At all times, the filesystem will keep track of a “current” node in its file tree: the current working directory of its user. It will allow fast (constant-time) access to the child and parent directories of that directory. For simplicity, it will only allow up to two files per directory.
In order to implement such a filesystem, you will need to create a tree-like data structure that is capable of keeping track of a “current” node in the tree, finding that node’s parent and children in O(1) time, and creating or deleting children in O(1) time. The simple tree definition that we’ve seen in this class so far
will not suffice, since, even if the tree is balanced, finding an arbitrary node can only be done in O(log(n)) time in the worst case. You’ll be implementing some- thing much better.
2.1 Zippers Principles of Functional Programming代写
A zipper is a classic functional data structure. A functional data structure is one that doesn’t require any destructive modification or state in its implementation. In other courses, you may have seen arrays, hash tables, and other data structures that involved modifying cells inside of them, removing elements, or keeping track of pointers. Functional data structures don’t need any of that. They can be defined using simple datatype declarations and clever implementations. Despite not using all the features that imperative data structures have, functional data structures are never more than O(log(n)) slower than their imperative counterparts, and are sometimes just as fast. In particular, zippers are just as efficient asymptotically as their imperative counterparts.
Zippers are augmentations of ordinary data structures (lists, trees, etc)
that allow them to keep track of an element that is “in-focus” and easily access elements that are adjacent to that element. For this reason, they’re great for filesystems, which need to keep track of a current directory and navigate to and from it easily.Principles of Functional Programming代写
The zipper you’ll be implementing in this assignment is a tree zipper. It keeps track of the current “in-focus” node in the tree and allows easy access to the parent and children of that node. It does this by keeping track of a tuple whose first element is the subtree rooted at the in-focus node, and whose second element is a list whose elements are subtrees rooted at each of that node’s ancestors, in order from closest to furthest, all the way up to the root. Each ancestor has a placeholder, a “hole,” at its subtree where the previous tree in the list would have been. Let’s see an example using the following tree:
Here, we use stars (i.e., *labs*) to mean that labs is the current working directory
– this is the in-focus node. The tree zipper that represents this would be
The first tree in the tuple is the tree in focus: labs.
The first tree in the list is the subtree rooted at labs’s parent, but with a hole (o) where labs was. The second one is the parent of the second tree, with a hole where the second tree would go. Make sure you understand how you could reassemble this list into the original tree.
To navigate from a child to a parent in a tree zipper, cons off the first element in the list. If there isn’t one, you’re at the root of the tree and so can’t navigate to a parent. Replace the o in that first element with the first element of the tuple, and make that the new first element of the tuple. Make the tail of the list the new second element of the tuple. For example, this moves the focus from labs to 15150:
To navigate from a parent to a child, take the first element in the tuple and pick the child of it that you want to move to.
Place a o where the child was and cons the resulting tree to the list in the tuple. Make the child the new first element of the tuple. If home were in focus, this would move the focus from home to memes:
2.2 Implementation Principles of Functional Programming代写
The datatype for a tree zipper involves two declarations: one for the tree structure and one for the tuple. Our particular tree zipper will be a named tree zipper with leaves, in which every node is labeled with a string, but only the leaves of the tree contain values. This is so that we can have directories, which contain either leaves (files) or nodes (other directories), and both directories and files will have names.
Associated with this type are invariants,
facts about the structure that must always hold for it to be a valid treezipper. As you implement functions on treezippers, you may assume that the invariants hold for any input treezipper and you must maintain the invariants for any output treezipper. The invariants are:
- Thereare no Holes in the first element of the treezipper
- Thefirst element of the treezipper tuple is either a Leaf or a Node. Principles of Functional Programming代写
- All elements in the second element of the treezipper tuple are Nodes that containexactly one Hole. This Hole is the left or right child of their
You will be implementing part of the TREEZIPPER signature, which describes the operations that can be done on a treezipper. The full signature is reproduced on the next page. A partial implementation of this signature can be found in TreeZipper.sml. You’ll be implementing the remaining three functions: the nav- igation functions.
An explanation of what the functions in TREEZIPPER do can be found at the end of this homework PDF.
You’ll need this explanation for later parts of the assignment.
Task 2.1 (5 pts). Implement the parent function with the behavior described above for navigating from child to parent. parent tz should return a treezipper representing with parent of the current node in focus if it has a parent and NONE otherwise. Make sure that you don’t remove or modify any ancestors in the list other than the parent. This function should have O(1) runtime.
Task 2.2 (6 pts). Implement the leftChild and rightChild functions with the behavior described above for navigating from parent to child. leftChild tz should return a treezipper with the left child of the current node in focus, if it has a non-Empty left child, and NONE otherwise. This function should maintain the invariant that if tz has a left child, Option.map parent (leftChild tz))
∼= SOME tz and if tz is itself a left child of its parent1, Option.map leftChild (parent tz)) ∼= SOME tz. rightChild tz should return a treezipper with the right child of the current node in focus, if it has a non-Empty right child, and NONE otherwise. This function should maintain the invariant that if tz has a right child, Option.map parent (rightChild tz)) ∼= SOME tz and if tz is itself a right child of its parent, Option.map rightChild (parent tz)) ∼= SOME tz. These
functions should have O(1) runtime.Principles of Functional Programming代写
2.3 Testing
You can test your zipper code in the same way we’ve been testing functions all semester. Then, to run your code, type
smlnj TREEZIPPER.sig TreeZipper.sml
When creating test cases for your functions, you may encounter a warning about the value restriction. Don’t worry about what this means. To make it (and any associated errors) go away, just type annotate your treezipper (i.e., val tz : int treezipper = …).
2.4 Style Principles of Functional Programming代写
Warning: You cannot get style points back on this homework. Every style deduction you get from this point forward is permanent.
Additionally, we have a new style rule for this homework:
You will lose style points for using the open keyword at top level.
If you don’t know what this is, don’t worry about it! If you do, avoid using it, as it clutters up the namespace immensely.
1Remember that Option.map f (SOME x) ∼= SOME (f x) and Option.map f NONE ∼= NONE
3 A Functional Filesystem
With the TreeZipper structure, you now have everything you need to implement a purely functional filesystem! The filesystem you’ll be implementing is described by the FILESYSTEM signature.
The signature has navigation functions, styled after typical bash commands that perform similar functions, and functions to create and show the contents of files. All files are plain text files, and their contents are represented by strings. Each directory can contain up to two files or directories.
We’ve already implemented the start, createFile, and showFileContents func- tions for you, and defined the datatypes and exceptions at the top of FileSystem.sml. Do not change these!
3.1 Implementation
For this section, you’ll be implementing some of the functions in FileSystem.sml. Make sure to make good use of the functions in the TreeZipper structure. A reference page explaining what all the functions do can be found at the end of this homework assignment.
Tip: It may become tedious to rewrite the name of the TreeZipper structure over and over again. We’ve given you an alias for the TreeZipper structure at the top
of the file:
Task 3.1 (2 pts). Define the mkdir function. A call to mkdir fs name should create a directory in the current directory with the given name, at the leftmost available spot. If the current directory already has two non-empty children, it should raise DirectoryFull. Principles of Functional Programming代写
Task 3.2 (3 pts). Define the rm function. A call to rm fs name should delete the child of the current directory with the given name or raise NoSuchFileOrDirectory if no child of that name exists. This function should only search for the filename within the current directory. It should not look in any subdirectories.
Task 3.3 Principles of Functional Programming代写
(4 pts). Define the cd function. A call to cd fs UP should navigate to the parent directory or raise NoSuchDirectory if already at the root. A call to cd fs (DOWN filename) should navigate to the child directory with the name given or raise NoSuchDirectory if no child of that name exists or a child with that name is not a directory. This function should only search for a filename within the current directory. It should not look in any subdirectories.
Task 3.4 (4 pts). Define the ls function. A call to ls fs should return a list of the names of the children of the current working directory of fs. It should list only the working directory’s children – not any of it’s children’s children. The children listed by ls should be listed in order from left to right.
Task 3.5 (5 pts). Define the pwd function. A call to pwd fs should return a list of the “path” to the current working directory. This is a list of names of all directories in the filesystem along the path from the root to the current directory. The first element of the list should be the root node and the last should be the current directory.Principles of Functional Programming代写
3.2 Testing the Filesystem
For fun and for ease of testing, we’ve given you an interactive shell in which you can type in commands to perform the filesystem operations you defined above.
To run it, type
smlnj -m sources.cm
to load your code. Then, in the REPL type
SimpleInteractive.start();
This will bring up a little prompt in the shape of a capital lambda. In there, you can type commands to test your filesystem. Here is a list of all the commands you can use and an example of how to use them:
- pwd: prints the current working Principles of Functional Programming代写
/\ pwd
home/
- mkdir<name>: creates a directory with the name given
/\ mkdir 15150
- ls:prints the contents of the current directory Principles of Functional Programming代写
/\ ls
15150
- cd <filename>: navigates down to a childdirectory
/\ cd 15150
- cd ..: navigates up to the parent directory
/\ cd ..
- rm <filename>: removes a childdirectory
/\ rm 15150
To quit the interactive system, type Ctrl-c.
Example Interactive Run
– SimpleInteractive.start();
/\ pwd home/
/\ mkdir 15150
/\ cd 15150
/\ pwd home/15150/
/\ cd ..
/\ mkdir 15122
/\ ls
15150 15122
/\ rm 15122
/\ ls 15150
4 Text Editor Principles of Functional Programming代写
One thing this interactive file system is missing is the ability to edit files. The FileSystem structure has the ability to create, show, and delete files, but we haven’t given you commands to do that in the interactive shell. Instead, you’ll be implementing a very simple text editor for editing files.
A text editor, at it’s simplest, is a piece of software that allows you to place a cursor into a string, and modify the string by inserting and deleting characters at the location of the cursor. The cursor can be moved to different parts of the string to create new edits.
Because a text editor may deal with very large files, it is important that it can perform its insert, delete, and cursor movement functions in constant time.
4.1 Implementation Principles of Functional Programming代写
The TEXTEDITOR signature describes all of these required operations for a text editor.
A potential implementation of this TEXTEDITOR signature is given in the file
NaiveTextEditor.sml. Take a look before continuing to read.
The problem with this implementation is that it takes O(n) time to insert, delete, and move. We can do better. We can create a datatype that does all these things in constant time. Your task will be to come up with this datatype and implement a faster version of the same signature, with behavior described below
- moveRight: Moves the cursor one place to the right in O(1) time. If it is already at the right, it should not move.Principles of Functional Programming代写
moveRight (Hel|lo) ==> SOME (Hell|o)
moveRight (Hello|) ==> NONE
- moveLeft: Moves the cursor one place to the left in O(1) time. If it is already at the left, it should not move.
moveLeft (Hel|lo) ==> SOME (He|llo)
moveLeft (|Hello) ==> NONE
-
insert: Places a character to the left of the cursor. This should take O(1) time.
insert (H|ello) #”i” ==> Hi|ello
- delete: Removes the character to the right of the cursor and returns the new text editor and the character deleted in O(1) time. If there is no character to the right of the cursor, it should return NONE.
delete (H|ello) ==> SOME (H|llo, #”e”) delete (Hello|) ==> NONE
- fromString: Creates a text editor from the input string with the cursor at the front. This should take O(n) time.
- toString: Creates a string from the text in the editor. This should take O(n) time.
- toStringWithCursor: Creates a string from the text in the editor, but in- serts the character #”|” where the cursor is. This should take O(n) time.
Task 4.1 (1 pts). In the file TextEditor.sml, create a structure called TextEditor that opaquely ascribes to TEXTEDITOR and define the type t that will allow you to implement the functions of the structure in the specified time bounds. Hint: You will not need a treezipper for this task, but you may want something conceptually similar.Principles of Functional Programming代写
Task 4.2 (12 pts). Implement the functions in the TextEditor structure, with the behavior and runtimes described above. You may find the built-in functions implode : char list -> string and explode : string -> char list help- ful. They take a char list and turn it into the corresponding string and vice versa. They both have O(n) runtime. Additionally, you may assume that the standard list library functions rev and length have O(n) runtime.
4.2 Testing
To load your code, type smlnj -m sources.cm. Then run the interactive filesys- tem with your text editor by typing
-structure Interactive =MkSimpleInteractive(TextEditor);
-start();
/\ edit <filename>
If you’d like to compare the behavior of your implementation with the provided naive implementation, run the following after running smlnj -m sources.cm
-structure Interactive =MkSimpleInteractive(NaiveTextEditor);
-start();
/\ edit <filename>
Remember that your implementation should differ from the naive implementation only in performance, not behavior.
4.3 Representation Independence Principles of Functional Programming代写
One of the things that makes ML’s module system special is opaque ascription. In ML, types in an opaquely ascribed structure that are not defined in a signature are truly abstract and must be used as such: there are no ways to violate the interface, no typecasts, no secret backdoors into the structure’s internal represen- tation.
Because of this, to prove that two different definitions of the same type in a signature are equivalent, we just have to prove that they behave in the same way with respect to the functions and other values defined in the structure. To do this, we define a relation between the two types, and then show that each function in the structure, when given equivalent inputs, produces equivalent outputs. This type of proof is called a representation independence proof.
For example, consider the following signature for the natural numbers:
and two implementations of that signature2
When are an n : NormalNat.nat and an s : SillyNat.nat equivalent? When
n = length s, since SillyNat represents nats by how many units are in the list3.
2List.tabulate(i, f) creates a list whose elements are [f 0, f 1, …, f (i – 1)]
3Think of this as a unary representation of nats.
Formally, the relation between a NormalNat.nat and a SillyNat.nat is
R(n, s) iff n = length s
To prove that NormalNat.nat and SillyNat.nat are actually equivalent under this relation, we’d have to prove that corresponding functions in the two structures that take in inputs that are equivalent according to our relation have the same behavior. More formally, we must prove the following things:
- For all values i : int, R(fromInt i, SillyNat.fromInti)
- IfR(n, s) then toInt n ∼= SillyNat.toInt s
- If R(n, s) then R(increment n, SillyNat.increments)
While this is just a small example, representation independence can be used to prove equivalence of more complex structures – text editors, for example.
Task 4.3 (5 pts). Define a relation R between NaiveTextEditor.t and your TextEditor.t. Hint: You should not need the toString, toStringWithCursor, or fromString functions from either editor for this task.
Task 4.4 (7 pts). List what you must prove in order to prove that the equivalence holds. Your solution should be in the same format as the bulleted list given for nat. You should not write the proof; just write what you would need to prove.
5 A Better Editor Principles of Functional Programming代写
The text editor you implemented in the last section is not a very useful text editor. Sure, you can add and delete characters and move around in the string, but you can’t even perform simple operations like backspace—or very important ones, like copy and paste.
5.1 Functors!
To make the text editor slightly more usable, you’ll be implementing a functor that takes a text editor as an argument and outputs a better editor with more features. These features will be backspace, text selection, and copy and paste. The signature for the better editor is given below:
The include keyword means that all the type and value declarations in the
TEXTEDITOR signature are also part of the ENHANCEDEDITOR signature.
Backspace is the same as delete, but removes the character to the left the cursor rather than to the right.Principles of Functional Programming代写
Text selection works by setting a mark at a particular cursor location, and then moving the cursor to a new location. Everything between the mark and the cursor location is selected. Cutting removes the selected text and puts it in the clipboard, a data structure that keeps track of copied text. Pasting places whatever text was in the clipboard to the left of the cursor.
To implement these operations, we’ll need a new type for our editor. In particular, we’ll need a type that keeps track of three things:
- Thecursor and text in the editor, as before
- Howfar we’ve gone to the right or left of the mark (so we know how much we’ve selected)
- Theclipboard
The input to the functor will be a structure called TextEditor which ascribes to the TEXTEDITOR signature. Our new text editor type will be
where the TextEditor.t represents the current text in the editor, as before. The new datatype selected tells us whether there is NoMark, whether our cursor is At the mark, or how many characters (n > 0) to the Right or Left of the mark the cursor is.
For example, if I set a mark when the state of the text editor is Functi|ons, and then move the cursor to the left four times (Fu|nctions), then the selected value would be would be Left 4 and the text I’ve selected is ncti.
The char list is the string of characters currently in the clipboard. It should start out as [], and doesn’t change when we select text—only when we cut text.
Task 5.1 (1 pts). Principles of Functional Programming代写
Define a functor called MkEnhancedEditor in the file MkEnhancedEditor.sml. It should take a structure called TextEditor ascribing to the TEXTEDITOR signature as an argument and return a structure opaquely ascribing to ENHANCEDEDITOR. Copy the definition of the type t into the func- tor.
There are multiple ways to define a functor. This particular functor should create a structure ascribing to ENHANCEDEDITOR when called in the following way:
Task 5.2 (3 pts). Define the toString, toStringWithCursor and fromString functions. The toString and toStringWithCursor functions should return the same strings that the original TextEditor structure would have, regardless of what is marked or in the clipboard. The fromString function should return a TextEditor.t in the same way the original TextEditor structure would have, and should have NoMark set and nothing in the clipboard.
Task 5.3 (4 pts). Define the insert and delete functions. These should maintain the fact that the user cannot edit and select text at the same time. If there is no mark set, these function should have the same behavior as before. If there is a mark set, insert should return the same text editor it was given and delete should return NONE.
Task 5.4 (4 pts). Principles of Functional Programming代写
Define the backspace function. It should have the same behavior as delete, except it should remove and return the character to the left of the cursor instead of to the right. It should return NONE if there is no such character or if there is a mark set.
backspace (He|llo, NoMark, clipboard) ==> SOME ((H|llo, NoMark, clipboard), #”e”) backspace (|Hello, NoMark, clipboard) ==> NONE
backspace (He|llo, Left n, clipboard) ==> NONE
Task 5.5 (10 pts). Define the moveLeft and moveRight functions. These should affect the position of the cursor in the same way as before and should also update what text is selected if there is a mark set.
moveLeft (He|llo, At, clipboard) ==> (H|ello, Left 1, clipboard) moveLeft (He|llo, Right 1, clipboard) ==> (H|ello, At, clipboard) moveLeft (He|llo, Left 2, clipboard) ==> (H|ello, Left 3, clipboard) moveLeft (He|llo, NoMark, clipboard) ==> (H|ello, NoMark, clipboard)Principles of Functional Programming代写
moveRight (He|llo, At, clipboard) ==> (Hel|lo, Right 1, clipboard) moveRight (He|llo, Left 1, clipboard) ==> (Hel|lo, At, clipboard) moveRight (He|llo, Right 2, clipboard) ==> (Hel|lo, Right 3, clipboard) moveRight (He|llo, NoMark, clipboard) ==> (Hel|lo, NoMark, clipboard)
Task 5.6
(2 pts). Define the setMark and removeMark functions. The setMark function should modify selection to be At the current cursor. The removeMark function should modify the selection to be NoMark.
Task 5.7 (7 pts). Define the cut function. It should delete all highlighted text and move it to the clipboard, replacing any text that is currently in the clipboard. It should also remove the mark. If there is NoMark, cut should do nothing. Hint: You may want to take advantage of the fact that delete/backspace return the character they delete.
cut (He|llo, NoMark, clipboard) ==> (He|llo, NoMark, clipboard) cut (He|llo, At, clipboard) ==> (He|llo, NoMark, [])Principles of Functional Programming代写
cut (He|llo, Left 2, clipboard) ==> (He|o, NoMark, [#”l”, #”l”]) cut (He|llo, Right 2, clipboard) ==> (|llo, NoMark, [#”H”, #”e”])
Task 5.8 (4 pts). Define the paste function. It should place the text in the clipboard to the left of the cursor. It should not modify the text in the clipboard. If a mark is set, paste should do nothing.
paste (He|llo, NoMark, [#”h”, #”i”]) ==> (Hehi|llo, NoMark, [#”h”, #”i”])
paste (He|llo, At, [#”h”, #”i”]) ==> (He|llo, At, [#”h”, #”i”]) paste (He|llo, NoMark, []) ==> (He|llo, NoMark, [])
5.2 Testing
To load your code, type smlnj -m sources.cm. Then run the interactive filesys- tem with your enhanced text editor by typing
- structure Interactive =MkInteractive(MkEnhancedEditor(TextEditor));
- start();
/\ edit <filename>
As before, you can use NaiveTextEditor instead of TextEditor to test with the provided naive implementation instead.
5.3 I’m a real editor! Principles of Functional Programming代写
If you’d like, we have provided code to run your editor in a more editor-like graphical interface. We recommend only doing this after ensuring your code works with the simple interface.
We have provided a script sml_editor.sh that you must use to launch the graphi- cal interface. It will not work if you launch it with smlnj -m sources.cm.
Simply run ./sml_editor.sh, then type the following. Note the use of the editTui command instead of edit.Principles of Functional Programming代写
Note that when the editor says C-<character> for a certain command, this means
Ctrl-<character>
- structure Interactive =MkInteractive(MkEnhancedEditor(TextEditor));
- start();
/\ editTui <filename>
Note: There are a few caveats to running the editor in this way.
- You will not be able to use the arrow keys at the SML/NJ REPL. This is necessaryto make the editor read input
- You won’t be able to type ”—” characters due to the way cursor trackingis done.
- You may notice some intermittent flashing when typing. This is a conse- quence of the interface’s design and has nothing to do with your code.
This assignment has a total of 100 points.
Appendix: TreeZipper Function Reference
5.4Creators
This function creates a treezipper node with the given name and no children.
This function creates a leaf with the given value and name.
5.5 Accessors
This function will get the value from the in-focus node of the tree zipper, if it is a leaf, or return NONE otherwise.
This function will get the name of the in-focus node of the tree zipper.
5.6 Navigators
Descriptions of these functions are given earlier in the handout. You implemented them!
5.7 Modifiers
This removes the left child of the current in-focus node of the treezipper. If the in-focus node does not have a left child, it returns the original zipper unmodified.
This removes the right child of the current in-focus node of the treezipper. If the in-focus node does not have a left child, it returns the original zipper unmodified.
insertLeftChild treezipper child makes child the new left child of treezipper’s in-focus node. If treezipper already has a left child, that child is replaced with
the new one. If treezipper’s in-focus node is a Leaf, it returns the original leaf with no modifications.
insertRightChild treezipper child makes child the new right child of treezipper’s in-focus node. If treezipper already has a right child, that child is replaced with
the new one. If treezipper’s in-focus node is a Leaf, it returns the original leaf with no modifications.
5.8 Queries
findChild treezipper name returns Left child where child is the left child of treezipper if the left child of the in-focus node of treezipper has the name given. It returns Right child where child is the right child of treezipper if the right child of the in-focus node of treezipper has the name given. It returns Neither if neither child has that name.
When using this function, remember that the constructors in your cases need the full structure name before them. For example,
case TreeZipper.findChild treezipper “15150” of TreeZipper.Left child => …
| TreeZipper.Right child => …
| TreeZipper.Neither =>
This function says whether the in-focus node of the treezipper is a leaf.
