Previous Contents Next


Merging two lists

  1. Write a function merge_i which takes as input two integer lists sorted in increasing order and returns a new sorted list containing the elements of the first two.

  2. Write a general function merge which takes as argument a comparison function and two lists sorted in this order and returns the list merged in the same order. The comparison function will be of type 'a -> 'a -> bool.

  3. Apply this function to two integer lists sorted in decreasing order, then to two string lists sorted in decreasing order.

  4. What happens if one of the lists is not in the required decreasing order?

  5. Write a new list type in the form of a record containing three fields: the conventional list, an order function and a boolean indicating whether the list is in that order.

  6. Write the function insert which adds an element to a list of this type.

  7. Write a function sort which insertion sorts the elements of a list.

  8. Write a new function merge for these lists.

Lexical trees

Lexical trees (or tries) are used for the representation of dictionaries.

# type lex_node = Letter of char * bool * lex_tree
and lex_tree = lex_node list;;
# type word = string;;
The boolean value in lex_node marks the end of a word when it equals true. In such a structure, the sequence of words ``fa, false, far, fare, fried, frieze'' is stored in the following way:
An asterisk (*) marks the end of a word.
  1. Write the function exists which tests whether a word belongs to a dictionary of type lex_tree.

  2. Write a function insert which takes a word and a dictionary and returns a new dictionary which additionally contains this word. If the word is already in the dictionary, it is not necessary to insert it.

  3. Write a function construct which takes a list of words and constructs the corresponding dictionary.

  4. Write a function verify which takes a list of words and a dictionary and returns the list of words not belonging to this dictionary.

  5. Write a function select which takes a dictionary and a length and returns the set of words of this length.

Graph traversal

We define a type 'a graph representing directed graphs by adjacency lists containing for each vertex the list of its successors:

# type 'a graph = ( 'a * 'a list) list ;;

  1. Write a function insert_vtx which inserts a vertex into a graph and returns the new graph.

  2. Write a function insert_edge which adds an edge to a graph already possessing these two vertices.

  3. Write a function has_edges_to which returns all the vertices following directly from a given vertex.

  4. Write a function has_edges_from which returns the list of all the vertices leading directly to a given vertex.

Previous Contents Next