Merging two lists
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.
- 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.
this function to two integer lists sorted in decreasing order, then to two
string lists sorted in decreasing order.
- What happens
if one of the lists is not in the required decreasing order?
- 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
- Write the function insert
which adds an element to a list of this type.
- Write a function
sort which insertion sorts the elements of a list.
- Write a new function merge
for these lists.
Lexical treesLexical trees (or tries) are used for the representation of
The boolean value in lex_node marks the end of a word when it
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.
Write the function exists
which tests whether a word belongs to a dictionary of type
- 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.
- Write a function construct
which takes a list of words and constructs the corresponding dictionary.
- Write a function verify
which takes a list of words and a dictionary and returns the list of words
not belonging to this dictionary.
- Write a function select
which takes a dictionary and a length and returns the set of words of this
Graph traversalWe define a type 'a graph representing directed graphs by
adjacency lists containing for each vertex the list of its successors:
Write a function insert_vtx
which inserts a vertex into a graph and returns the new graph.
- Write a function insert_edge
which adds an edge to a graph already possessing these two vertices.
- Write a function has_edges_to
which returns all the vertices following directly from a given vertex.
- Write a function has_edges_from
which returns the list of all the vertices leading directly to a given