## Exercises

### Association Lists

In this first simple exercise, we will implement a polymorphic abstract type for association lists, and present two different views of the implementation.

1. Define a signature ALIST declaring an abstract type with two type parameters (one for the keys, the other for the associated values), a creation function, an add function, a lookup function, a membership test, and a deletion function. The interface should be functional, i.e. without in-place modifications of the abstract type.

2. Define a module Alist implementing the signature ALIST

3. Define a signature ADM_ALIST for ``administrators'' of association lists. Administrators can only create association lists, and add or remove entries from a list.

4. Define a signature USER_ALIST for ``users'' of association lists. Users can only perform lookups and membership tests.

5. Define two modules AdmAlist and UserAlist for administrators and for users. Keep in mind that users must be able to access lists created by administrators.

### Parameterized Vectors

This exercise illustrates the genericity and code reuse abilities of parameterized modules. We will define a functor for manipulating two-dimensional vectors (pairs of (x,y) coordinates) that can be instantiated with different types for the coordinates.

Numbers have the following signature:
```# module` `type` `NUMBER` ``=`` `` `sig` `` `` `type` `a` `` `` `type` `t` `` `` `val` `create` ``:`` `a` `->` `t` `` `` `val` `add` ``:`` `t` `->` `t` `->` `t` `` `` `val` `string_of` ``:`` `t` `->` `string` `` `end` `;;

```

1. Define the functor FVector, parameterized by a module of signature NUMBER, and defining a type t of two-dimensional vectors over these numbers, a creation function, an addition function, and a conversion to strings.

2. Define a signature VECTOR, without parameters, where the types of numbers and vectors are abstract.

3. Define three structures Rational, Float et Complex implementing the signature NUMBER.

4. Use these structures to define (by functor application) three modules for vectors of rationals, reals and complex.

### Lexical Trees

This exercise follows up on the lexical trees introduced in chapter 2, page ??. The goal is to define a generic module for handling lexical trees, parameterized by an abstract type of words.

1. Define the signature WORD defining an abstract type alpha for letters of the alphabet, and another abstract type t for words on this alphabet. Declare also the empty word, the conversion from an alphabet letter to a one-letter word, the accessor to a letter of a word, the sub-word operation, the length of a word, and word concatenation.

2. Define the functor LexTree, parameterized by a module implementing WORD, that defines (as a function of the types and operations over words) the type of lexical trees and functions exists, insert et select similar to those from chapter 2, page ??.

3. Define the module Chars implementing the WORD signature for the types alpha = char and t = string. Use it to obtain a module CharDict implementing dictionaries whose keys are character strings.