CSCI 2041 Assignment 2: List Manager

Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.

NOTE: Tests Released Later: The tests for this assignment will not be released with the publication of the specification. They will be released sometime after once they have been completed. Further instructions on how to use them will be made available on release.

listmanager is demonstrated below. Study this demo session to gain an understanding of the direction of the program.

> make                          # build the program
ocamlc -g -annot -c util.ml
ocamlc -g -annot -c sortedlist.ml
ocamlc -g -annot -c undolist.ml
ocamlc -g -annot -c listmanager.ml
ocamlc -g -annot -o listmanager str.cma unix.cma util.cmo sortedlist.cmo undolist.cmo listmanager.cmo

> ./listmanager                 # start listmanager

LM> help                        # ask for help
LIST MANAGER
Maintains a sorted list without duplicates
No spaces allowed list data, use _ instead as in Lin_Beifong
Commands:
  help           : print this help message
  quit           : quit the program
  show           : print the current list to the screen
  clear          : set the list to empty, preserves undo history
  add <elem>     : add elem to the list
  remove <elem>  : remove elem from list
  save <file>    : save the current list to named file (not undoable)
  load <file>    : discard the current list, load sorted list in named file (undoable)
  mergein <file> : load the sorted list in the named file and merge with current list (undoable)
  undo           : undo the last operation restoring list to a previous state
  redo           : redo the last undone operation restoring list to a previous state

LM> show                        # show the current list
--BEG LIST--                    # it's empty
--END LIST--

LM> add Korra                   # add some elements
LM> add Mako
LM> add Bolin
LM> show                        # show it now
--BEG LIST--
Bolin                           # all three present
Korra
Mako
--END LIST--

LM> add Korra                   # adding existing elements
LM> show                        # does not create duplicates
--BEG LIST--
Bolin
Korra
Mako
--END LIST--

LM> add Tenzin                  # add some more elements
LM> add Asami
LM> show                        # show current list
--BEG LIST--
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> save heros.txt              # save to a text file

LM> clear                       # empty the list
LM> show
--BEG LIST--
--END LIST--

LM> add Amon                    # add some new elements
LM> add Tonraq
LM> add Kuvira
LM> add Zaheer
LM> show
--BEG LIST--
Amon
Kuvira
Tonraq
Zaheer
--END LIST--

LM> save villains.txt           # save into a different text file

LM> load heros.txt              # load from a file
LM> show                        # overwrites existing list
--BEG LIST--
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> mergein villains.txt        # merge current list with contents of file
LM> show                        # sorted order maintainted
--BEG LIST--
Amon
Asami
Bolin
Korra
Kuvira
Mako
Tenzin
Tonraq
Zaheer
--END LIST--

LM> remove Kuvira               # removing elements
LM> remove Tonraq
LM> remove Zaheer
LM> show
--BEG LIST--
Amon
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> remove Zaheer               # removing more elements
LM> show
--BEG LIST--
Amon
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> clear                       # empty the list
LM> show
--BEG LIST--
--END LIST--

LM> undo                        # undo the clear to restore it
LM> show
--BEG LIST--
Amon
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> add Kuvira                  # perform to more alterations
LM> remove Amon
LM> show
--BEG LIST--
Asami
Bolin
Korra
Kuvira
Mako
Tenzin
--END LIST--

LM> undo                        # undo the last operation: remove Amon
LM> show
--BEG LIST--
Amon
Asami
Bolin
Korra
Kuvira
Mako
Tenzin
--END LIST--

LM> undo                        # undo the last operation: add Kuvira
LM> show
--BEG LIST--
Amon
Asami
Bolin
Korra
Mako
Tenzin
--END LIST--

LM> redo                        # redo add Kuvira
LM> redo                        # redo remove Amon
LM> show                        # list restored
--BEG LIST--
Asami
Bolin
Korra
Kuvira
Mako
Tenzin
--END LIST--
LM> quit

List managed!
>                               # back to the unix prompt

Create a source file sortedlist.ml which will have the following bindings in it.

(* sortedlist.ml : Provides operations for sorted lists of any type. *)

let rec insert list elem = ... ;;
(* val insert : 'a list -> 'a -> 'a list
   PROBLEM 1: Insert elem into list which is sorted.  The insertion
   preserves the sorted order of the list.  No duplicates are allowed
   in the list: if elem is equal to an element of list, the resulting
   list is identical to the original list. Uses pattern matching, not
   tail recursive. Runs in linear time on length of list.

  REPL EXAMPLES
  # insert [1;3;5;7] 8;;
  - : int list = [1; 3; 5; 7; 8]
  # insert [1;3;5;7] 2;;
  - : int list = [1; 2; 3; 5; 7]
  # insert [1;3;5;7] 5;;
  - : int list = [1; 3; 5; 7]
  # insert ["b";"d";"f"] "a";;
  - : string list = ["a"; "b"; "d"; "f"]
  # insert ["b";"d";"f"] "g";;
  - : string list = ["b"; "d"; "f"; "g"]
  # insert ["b";"d";"f"] "b";;
  - : string list = ["b"; "d"; "f"]
  # insert [] "g";;
  - : string list = ["g"]
*)

let rec remove list elem = ... ;;
(* val remove : 'a list -> 'a -> 'a list
   PROBLEM 1: Create a new list with elem removed from the parameter
   list. If elem is not present in list, the result is identical to
   the original list. Uses pattern matching, not tail recursive.
   Runs in linear time on length of list.

   REPL EXAMPLES
   # remove [1;3;5;7] 1;;
   - : int list = [3; 5; 7]
   # remove [1;3;5;7] 5;;
   - : int list = [1; 3; 7]
   # remove [1;3;5;7] 6;;
   - : int list = [1; 3; 5; 7]
   # remove ["b";"d";"f"] "b";;
   - : string list = ["d"; "f"]
   # remove ["b";"d";"f"] "z";;
   - : string list = ["b"; "d"; "f"]
*)

let rec print strlist = ... ;;
(* val print_strlist : string list -> unit
   PROBLEM 1: Print all elements of a string list to standard
   output. Makes use of standard printing functions such as
   print_endline or printf to print. Uses pattern matching. This
   function IS tail recursive. Runs in linear time on length of list.

   REPL EXAMPLES
   # print ["apple";"orange";"banana"];;
   apple
   orange
   banana
   - : unit = ()
   # print ["grape";"pear"];;
   grape
   pear
   - : unit = ()
*)

let rec merge lista listb = ... ;;
(* val merge : 'a list -> 'a list -> 'a list
   PROBLEM 2: Merge two sorted lists: lista and listb.  Elemetns that
   appear in both lists appear only once in the result.  Operates in
   linear time on the length of lists: does not do repeated
   insertion. Not tail recursive. May use pattern matching OR if/else
   clauses. Runs in linear time on combined length of lists.

   REPL EXAMPLES  
   # merge [] [2;4;6];;
   - : int list = [2; 4; 6]
   # merge [1;3;5] [2;4;6];;
   - : int list = [1; 2; 3; 4; 5; 6]
   # merge [1;3;5] [];;
   - : int list = [1; 3; 5]
   # merge [1;3;5] [2;3;4;6;8];;
   - : int list = [1; 2; 3; 4; 5; 6; 8]
   # merge ["a";"c";"e"] ["b";"d"];;
   - : string list = ["a"; "b"; "c"; "d"; "e"]
   # merge ["a";"c";"e"] ["b";"c";"d";"e"];;
   - : string list = ["a"; "b"; "c"; "d"; "e"]
*)

While implement insert and remove keep the following in mind.

• For full credit, make use of pattern matching in your solution via the match/with construct. You may use some if/else clauses as well within pattern matched cases.
• A nice alternative to if/else is the when guard in pattern matching which will be covered in lecture eventually briefly the syntax is

  let x = ... in
  match list with 
  | []               -> result for empty list
  | a :: b when a=x  -> some result
  | a :: b when a<x  -> some other result
  | a :: b           -> result when above don't apply
  

  This allows application of a pattern matching case only when a condition is true.

• The function should be recursive as indicated by the signature let rec. However, the DO NOT need to be tail-recursive.
• Ensure that no duplicate elements are created in lists: inserting an element that is already present returns a list equal to the original list (though it may be a somewhat different list)
• Exploit the fact that the list is sorted to gain some small efficiencies: on reaching an element larger than the element to be inserted or removed, there is no need to recurse further into the list.

• This is a simple function that prints the elements of any string list to the standard output which is usually the screen
• Each element of the list is printed on its own line
• Make use of printf for printing to show you understand its use
• Pattern matching should be employed to destructure the list
• Ensure that the function is tail recursive by making the last action in the recursive case a function call.

The following criteria will be checked in this problem.

• This is a classic exercise to merge two sorted lists in linear time on the length of the lists. It comes up when implementing algorithms such as Merge Sort though usually that setting involves merging arrays rather than linked lists
• The central approach breaks the problem into some general cases based on the two inputs lista and listb
  • One list empty: the remainder of the merged list is the other non-empty list
  • Both lists contain same element: the merged list has one copy of the element and the remainder is found by recursing on the tails of both lists
  • lista has an element smaller than listb: the merged list has the head of lista followed by the result of recursing on the tail of lista and all of listb
  • listb has an element smaller than lista: converse of the previous: one element from listb and recurse on tail of listb and all of lista
• The above process allows for progress through both lists simultaneously which results in a linear time complexity on the combined lengths of the lists.
• Since the case have to do with elements from both inputs, using pattern matching is a bit more intricate. For that reason, it is not required or this problem. Pure use of if/else will receive full credit.
• If interested, one can pattern match on pair of values using syntax like the following.

  match x,y with
  | [],(yh::yt)                  -> x empty, y has head and tail
  | (xh::xt),(yh::yt) when xh=yh -> both nonempty, heads equal
  ...
  

  This technique will be covered in some detail in lecture at a future date.

The following criteria will be checked in this problem.

Create a source file undolist.ml which will have the following bindings in it.

(* undolist.ml : This module manages a sorted list strings. add,
   remove, and merge operations are provided. undo/redo operations are
   provided to alter list. Type annotaions are required on the
   module-level values as refs to 'a list are not allowed due to weak
   typing. 

   All functions in this file pertain to PROBLEM 3
*)

let curr_list : string list ref = ... ;;
(* The current list of strings. *)

let undo_stack : string list list ref = ... ;;
(* List of previous curr_lists to enable undo. *)

let redo_stack : string list list ref = ... ;;
(* List of undone curr_lists to enable redo. *)

let reset_all () = ... ;;
(* Reset curr_list, undo_stack, redo_stack to all be empty lists. Used
   only in testing, not in main programs. *)

let set_to_list new_list = ... ;;
(* curr_list is moved to the top of the undo_Stack. Then curr_list is
   set to the new_list. Empties redo_stack. *)

let add_elem elem = ... ;;
(* Add the given elem to curr_list producing a new_list.  Calls
   set_to_list on result to unable undoing. *)

let remove_elem elem = ... ;;
(* Remove the given elem from curr_list producing a new list. Calls
   set_to_list on result to unable undoing.  *)

let merge_with_list list = ... ;;
(* Merge the param list with the current list. Calls set_to_list on
   the result to enable undoing. *)

let undo () = ... ;;
(* If the undo_stack is not empty, undo the last operation. curr_list
   is moved to the redo_stack and the top element of undo_stack is
   removed and becomes curr_list.  Returns true if changes are made
   and false if undo_stack is empty and no changes are made. Operates
   in constant time. *)

let redo () = ... ;;
(* If the redo_stack is not empty, redo the last operation. curr_list
   is moved to the undo_stack and the top element of redo_stack is
   removed and becomes curr_list.  Returns true if changes are made
   and false if redo_stack is empty and no changes are made. Operates
   in constant time. *)

The standard lists provided OCaml are immutable. This means that most lists can be conceptualized as separate and distinct from one another. In reality, pure functions such as those implemented in sortedlists.ml may create "new" lists with a combination of fresh and existing Cons boxes. Below is figure showing both the "conceptual" view of how curr_list, undo_stack, redo_stack are related as well as a fine-grained view of their actual relations. The interlinking between lists could be intricate. This sharing saves memory but is not a concern to the program due to the lists being persistent: they cannot be changed moving forward.

Most programmers are acquainted with undo/redo in standard programs: discrete actions that are taken are can be undone to go back to a previous state. If undone, they can be redone to restore the "future" state. In simple implementations like ours, undoing actions then performing a new action "clobbers" the redo history so that those states are lost.

To implement this in listmanager , actions progressively push new lists into the undo_stack list of lists (Below Figure (A)). Calling undo will pop an element from the top of this stack and set curr_list to point to it while the state in curr_list is moved to the redo_stack (Figure (B)-(C)). Calling redo will pop an element from redo_stack off moving it the curr_list which is moved to the undo_stack (Figure (D)). Any new action taken will empty the redo_stack so that lists there are lost (Figure (E)).

Study this diagram carefully to ensure that your implementation of undolist.ml functions matches these semantics.

• The file contains "global" refs curr_list to the current string list and undo_stack/redo_stack which are lists of previous values of curr_list. Functions will directly manipulate these refs to keep track of the history associated with curr_list.
• The function set_to_list new_list is the work horse of the module. It moves the curr_list to the undo_stack and sets curr_list to the specified new_list. Use the set_tolist in the other mutator functions such as add_elem and remove_elem.
• Remember that when working with OCaml refs, the following apply
  • Assign using the := operator as in aref := new_value;
  • Access the value refs with !aref
• You will use a variety of functions from the sortedlist.ml such as insert here. Refer to these functions using the module reference syntax: Sortedlist.insert or Sortedlist.remove etc. Examples are below.

  let new_list = Sortedlist.insert some_list new_elem in
  ...
  let smaller = Sortedlist.remove alist gone in
  ...
  listref := Sortedlist.merge xlist !listref;
  ...
  

• Do not use open Sortedlist in this module: practice addressing functions in another file using the module syntax above.
• The undo/redo functions should manipulate the refs to accomplish semantics described the previous section. Note that these functions never throw exceptions. If it is not possible to undo or redo, nothing is done. Both functions return a boolean: true when they make changes, false otherwise due to an associated function being empty.

The following criteria will be checked in this problem.

This file does not require modification. It provides two I/O routines to read and write lists in files. These are needed for associated listmanager commands.

(* util.ml: utilities for splitting and file opeartions. All functions
   in this file are already implemented. *)

let strlist_from_file filename = ... ;;
(* Load a list of strings from a text file. Not particularly efficient
   as it is not tail recursive but gets the job done. *)

let strlist_to_file strlist filename  = ... ;;
(* Write a list of strings to file filename. Tail recursive so
   reasonably efficient. *)

This file has a variety of code in it already. It has the following features.

• execute_command needs to be defined. This function is called every time a user types a command. It calls functions from modules Sortedlist, Undolist and Util to execute affect the program state. It is described in some detail later.
• The two values help_string and quit_now are used in execute_command and are thus defined above it. These definitions are provided.
• Code is provided below execute_command to set up an interactive loop that reads user input. This code does not require modification but may provide interesting reading for folks that wonder about command line argument processing, exception handling, and other features in OCaml. This is not required now but will be covered by the end of the course

Below are the top-level bindings in the file.

(* listmanager.ml : main function to allow manipulation of a sorted
   list of unique elements. Makes use of functions provided in
   Sortedlist, Undolist, and Util. *)

let debug = ... ;;
(* debug printing on/off *)

let help_string = ... ;;
(* Help string to be printed for the "help" command. *)

let quit_now = ... ;;
(* When false, prompts for another command and continues interactive
   loop. When true, ends interactive loop and quits program. *)

let execute_command tokens = ... ;;
(* PROBLEM 4: Execute a single command for the listmanager
   program. Argument tokens is an array of strings at least 1 element
   long.  The 0th element is the command to execute like "add" or
   "clear". Depending on the command, there may be subsequent
   arguments.  Makes use of functions provided in Sortedlist,
   Undolist, and Util a well as values in this module like help_string
   and quit_now. *)

let echo  = ... ;;
(* Code beyond this point should not require modification though it
   may be interesting to examine. *)

let prompt = ... ;;


let options = ... ;;
(* Options accepted by the program *)

let handle_extra_args arg = ... ;;
(* Do nothing with extra command line arguments *)

let usage = ... ;;
(* Simple usage message for Arg.parse *)

let _ = ... ;;
(* main routine *)

A good place to start in understanding how execute_command works is to examine the help string associated with the program which is provided below.

Commands:
  help           : print this help message
  quit           : quit the program
  show           : print the current list to the screen
  clear          : set the list to empty, preserves undo history
  add <elem>     : add elem to the list
  remove <elem>  : remove elem from list
  save <file>    : save the current list to named file (not undoable)
  load <file>    : discard the current list, load sorted list in named file (undoable)
  mergein <file> : load the sorted list in the named file and merge with current list (undoable)
  undo           : undo the last operation restoring list to a previous state
  redo           : redo the last undone operation restoring list to a previous state

When execute_command tokens is run, the argument tokens array will have a string like help or remove as the 0th element. This is the command to execute. If the command requires another argument like a <file>, it will be the 1th element in the array. This situation is set up by other code later in listmanager.ml.

A good way to structure this function is pattern matching on the command being issued. Full credit solutions will do this

Below are notes on how to address each of the commands mentioned. Many of these mix functions from other modules like Undolist.add_elem and Sortedlist.print. Refer to these functions using their full module address; do not add any open statements.

The following criteria will be checked in this problem.

listmanager is set up to accept two options: -debug and -echo. Both of these require no implementation for this problem but are described below for completeness.

listmanager -debug will set the ref Listmanager.debug to true. This prints some additional info in the interactive loop. It can also be used for debug messages in execute_command by doing something like the following.

if !debug then                  (* check if debugging is on *)
  begin
    printf "curr_list has %d elements\n"  (List.length !Undolist.curr_list);
    printf "undo_stack has %d elements\n" (List.length !Undolist.undo_stack);
    printf "redo_stack has %d elements\n" (List.length !Undolist.redo_stack);
  end;

listmanager -echo turns on command echoing: everything that is received as input is printed back on the screen. This allows for scripted behavior like the following which is used during testing to make output look more readable.

> cat input.txt       # contents of file input.txt, commands for listmanager
add D
add R
add B
add S
add F
remove S
show
undo
show
quit

> cat input.txt | listmanager -echo    # pipe into listmanager echoing commands
LM> add D
LM> add R
LM> add B
LM> add S
LM> add F
LM> remove S
LM> show
--BEG LIST--
B
D
F
R
--END LIST--
LM> undo
LM> show
--BEG LIST--
B
D
F
R
S
--END LIST--
LM> quit
List managed!
>

If creating a zip file is unfamiliar to you, refer to the following guide: Making Zips (tutorial)

Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to Canvas.

On Canvas:

• Click on the Assignments section
• Click on the appropriate link for this lab/assignment
• Scroll down to "Attach a File"
• Click "Browse My Computer"
• Select you Zip file and press OK

You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.

http://www-users.cs.umn.edu/~kauffman/2041/syllabus.html#late-projects