To learn how to create and manipulate simple data structures in ocaml.
Chapters 4-6 of the textbook.
Once again, you will be writing a series of independent functions and
supporting code rather than a full-blown program. Write them all in a file
called lab2.ml. Here are the functions and data types you have
to write. I've put the number of lines of ocaml code I used in my solution
in brackets after the description of each function/type/etc. Your code can
be longer than mine if you wish, but it's fun to try to write the code
concisely (without playing typographical games e.g. eliminating
newlines).
An insertion sort routine called insertion_sort
[11]. This will take as its arguments:
a list of items (of any type, although all items in any given list have to be the same type)
a comparison function (which takes two arguments of the same type and returns -1 if the first is "less" than the second, 1 if the first is "greater" than the second, and 0 otherwise
and returns a sorted list. The algorithm is simply this: insert the first item into the list created by insertion sorting the rest of the list. This has a very natural recursive solution. Note that you'll need to define a helper function to do the inserting.
A record type called complex [1] that represents
complex numbers. It will have two fields, called real and
imag. Also write the functions complex_of_float
[1] and complex_of_int [1] to convert from
floats/integers to complex numbers. Also write a function
compare_complex [4] to compare two complex numbers and
return -1, 0, or 1 if the first number is (respectively) less than, equal to,
or greater than the second. Since comparing complex numbers is ill-defined
mathematically, for the purposes of this lab assume that one complex number
is greater than another if the real part is greater, and only check the
imaginary part if the real part is the same.
A union data type called number [1] that can
represent either integers, floating-point numbers or complex numbers. Also
write a comparison function called compare_number
[11] that works on integers, floats, complex numbers, or any
combination of them. Note that the float_of_int function
converts from an int to a float. The built-in
compare function will return -1, 0, or 1 as described above and
will work on either floats or ints (but not both). Use this and your
insertion_sort function to sort a list that you create that
contains integers, floats, and complex numbers.
A quicksort function called quicksort [13] with
the same type signature as your insertion sort. First write a
split [5] function which takes an item and a list (plus
perhaps some other arguments (hint, hint)) and returns a tuple of two lists:
a list of items smaller than the item and a list of the remaining items.
This will be an internal function in your quicksort function.
Sort the two sublists recursively and append the sorted list less than the
item, the item itself (made into a one-element list), and the sorted list
greater than or equal to the item.
Note that the "@" operator is the list append operator
in ocaml. Use your quicksort function to sort a list of
strings. Note that the compare function will also work on
strings. The compare function is "magical" in that you can't
define a function like it yourself in ocaml i.e. which is overloaded
on various types.
A merge sort function called mergesort [20] with
the same type signature as your insertion sort. Merge sorting works like
this: first divide the list into two equal parts (or as equal as you can get
them). Then recursively sort the parts. Then merge the two sorted lists
into one big sorted lists. You will need two helper functions, one to do the
splitting [5] and one to do the merging [6].
Use your mergesort function to sort a list of list of integers. Note that
the magical compare function will still work for lists of
integers!
Consider the binary tree data type defined by:
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
Use this to define several functions on trees:
a function called count_leaves [4] that counts all
the leaves in a tree
a function called map_tree [5] that takes a function
and maps it over all elements of a tree, returning another tree
a function called tree_of_list [12] that takes a
list and turns it into a balanced tree (as balanced as possible)
a function called print_tree [18] that takes a tree
of ints and pretty-prints it into a readable form. Use indentation to
indicate different levels of the tree. Don't overdo it; it doesn't need
to be complicated or fancy.
Write some sample trees and apply your functions to them.
Your file lab2.ml. Note that you may have to put
double-semicolons (;;) at the end of expressions in a few places
in your file to allow the file to be executed with your test cases left in.
The compiler will tell you where those places are ;-)
None.