Association ListsIn this first simple exercise, we will implement a polymorphic
abstract type for association lists, and present two different views
of the implementation.
- 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
The interface should be functional, i.e. without in-place modifications of the abstract type.
- Define a module Alist implementing the
- Define a signature ADM_ALIST
for ``administrators'' of association lists. Administrators can only
create association lists, and add or remove entries from a list.
- Define a signature USER_ALIST
for ``users'' of association lists. Users can only perform lookups
and membership tests.
- 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.
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:
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.
- Define a signature VECTOR,
without parameters, where the types of numbers and vectors are abstract.
- Define three structures Rational,
Float et Complex implementing the signature
- Use these structures to define (by functor application)
three modules for vectors of rationals, reals
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.
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.
- 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
- 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.