Tutorial 5 (11 Feb 2021) Topics Covered: References, mutables, imperative programming.
Guiding Questions
What do references add to a pure functional paradigm? Why are they good and why are they bad? What does that imply for proving program correctness? What about runtime optimisation?
Question 1
Many imperative languages based on pointers (whether transparently like C++ or automatically like Java) have a special null value. The default OCaml ref type does not, as it is bound by type constraints, and there isn¡¯t a special value that can be of any type.
1. Write a type ¡®a nulref which can be either a Null value or a reference of the appropriate type.
2. Write a function nulref which creates a nulref-type value from a fixed element.
3. Using exception NullReference, write a function deref which returns the value inside a
nulref, or throws the exception if the nulref is in fact Null.
4. Write a function find : ¡®a nulref -> (¡®a -> bool) -> ¡®a list -> unit that tries to find the first
element in a list passing a predicate test, updating the nulref with the result. What is the
issue you encounter?
5. Rewrite the type and the functions above to accommodate this issue.
Question 2
Many data structures use references due to the resulting boost in runtime. For example, it¡¯s very difficult to get the last element of an OCaml list, because the immutable structure builds the list like a stack. Let¡¯s try to make a relatively simple data structure: a doubly-linked list.
1. Write the type of nodes contained inside the list. Each node should have a reference to its predecessor (if it has one) and to its successor (if it has one), as well as an immutable data field.
2. Write a function create x that initializes a node from a single element.
3. Write a function empty () that initializes an empty linked list. (Hint: you¡¯ll need a new
type here! One that can track head AND tail of list) Once you figure the type out, write
singleton x to return a linked list based on create.
4. Write a function append l1 x that adds a new element at the end of the linked list.
5. Write a function body l that returns a new linked list containing all but the head and tail
of the argument linked list. (Hint: this has a weird edge case!)
Extra questions (not covered by tutorial)
1. The solution for Question 2.5 does not handle making sure that the new head has no predecessor, and tail has no successor. Why can we not just modify the nodes? Try to fix this to correctly implement body.
2. You can see that even this small set of code is rather cumbersome. Can you see the problem with the type we¡¯ve picked? Try to solve the problem again, but this time modifying the node type to allow for nodes containing no data (sometimes called dead nodes, dummy nodes, or other similar terms). Does that simplify it? Is there another solution to simplify the code?