Exercises

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.

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.
```
 module type ALIST =
  sig
   type ('a,'b) t
   val create : unit -> ('a,'b) t
   val add : 'a -> 'b -> ('a,'b) t ->  ('a,'b) t
   val get : 'a -> ('a,'b) t ->  'b
   val mem : 'a -> ('a,'b) t ->  bool
   val rem : 'a -> ('a,'b) t ->  ('a,'b) t
  end ;;
Characters 142-148:
Syntax error
```
The interface should be functional, i.e. without in-place modifications of the abstract type.

Define a module Alist implementing the signature ALIST


# module Alist:ALIST =
  struct
   type ('a,'b) t = ('a*'b) list
   let create () = []
   let add k v al = (k,v)::al
   let get = List.assoc
   let mem = List.mem_assoc
   let rem = List.remove_assoc
  end ;;
Characters 14-19:
Unbound module type ALIST

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


# module type ADM_ALIST =
  sig
   type ('a,'b) t
   val create : unit -> ('a,'b) t
   val add : 'a  -> 'b -> ('a,'b) t -> ('a,'b) t
   val rem : 'a -> ('a,'b) t -> ('a,'b) t
  end ;;
module type ADM_ALIST =
  sig
    type ('a, 'b) t
    val create : unit -> ('a, 'b) t
    val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
    val rem : 'a -> ('a, 'b) t -> ('a, 'b) t
  end

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


# module type USER_ALIST =
  sig
   type ('a,'b) t
   val get : 'a -> ('a,'b) t -> 'b
   val mem : 'a -> ('a,'b) t -> bool
  end ;;
module type USER_ALIST =
  sig
    type ('a, 'b) t
    val get : 'a -> ('a, 'b) t -> 'b
    val mem : 'a -> ('a, 'b) t -> bool
  end

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.
```
# module AdmAlist = (Alist:ADM_ALIST with type ('a,'b) t = ('a,'b) Alist.t) ;;
Characters 20-25:
Unbound module Alist
# module UserAlist = (Alist:USER_ALIST with type ('a,'b) t = ('a,'b) Alist.t) ;;
Characters 20-25:
Unbound module Alist
```

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 ;;

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.


# module  FVector (N:NUMBER) =
  struct
   type e = N.t
   type t = { mutable vx:e; mutable vy:e }
   let create x0 y0 = { vx=x0; vy=y0 }
   let add v1 v2=  {vx = N.add v1.vx v2.vx; vy = N.add v1.vy v2.vy}
   let string_of v= "("^N.string_of v.vx^" , "^N.string_of v.vy^")"
  end ;;
module FVector :
  functor(N : NUMBER) ->
    sig
      type e = N.t
      and t = { mutable vx: e; mutable vy: e }
      val create : e -> e -> t
      val add : t -> t -> t
      val string_of : t -> string
    end

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


# module type VECTOR =
  sig
   type e
   type t
   val create : e -> e -> t
   val add :t -> t -> t
   val string_of : t -> string
  end ;;
module type VECTOR =
  sig
    type e
    and t
    val create : e -> e -> t
    val add : t -> t -> t
    val string_of : t -> string
  end

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


# module Rational:NUMBER =
  struct
   type a = int*int
   type t = { p:int; q:int }
   let create (p0,q0) = { p=p0; q=q0 }
   let add r1 r2 = { p = r1.p*r2.q + r2.p*r1.q; q = r1.q*r2.q }
   let string_of r = (string_of_int r.p)^"/"^(string_of_int r.q)
  end ;;
module Rational : NUMBER

# module Float:NUMBER =
  struct
   type a = float
   type t = a
   let create x = x
   let add = (+.)
   let string_of = string_of_float
  end ;;
module Float : NUMBER

# module Complex:NUMBER =
  struct
   type a = float*float
   type t = { r:float; i:float }
   let create (r0, i0) = { r=r0; i=i0 }
   let add c1 c2 = { r = c1.r+.c2.r; i = c1.i+.c2.i }
   let string_of c = 
    (string_of_float c.r)^"+"^(string_of_float c.r)^"*i"
  end ;;
module Complex : NUMBER

Use these structures to define (by functor application) three modules for vectors of rationals, reals and complex.
```
# module RatVect:VECTOR = FVector(Rational) ;;
module RatVect : VECTOR
# module FloVect:VECTOR = FVector(Float) ;;
module FloVect : VECTOR
# module ComVect:VECTOR = FVector(Complex) ;;
module ComVect : VECTOR
```

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.

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.


# module type WORD =
  sig
   type alpha
   type t
   val null : t
   val of_alpha : alpha -> t
   val get : t -> int -> alpha
   val sub : t -> int -> int -> t
   val length : t -> int
   val concat : t -> t -> t
  end ;;
module type WORD =
  sig
    type alpha
    and t
    val null : t
    val of_alpha : alpha -> t
    val get : t -> int -> alpha
    val sub : t -> int -> int -> t
    val length : t -> int
    val concat : t -> t -> t
  end

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 ??.


# module LexTree (W:WORD) =
   struct
     type node = Letter of W.alpha * bool * t
     and t = node list
 
     let rec exist m d = 
       let aux sm i n = 
         match d with
             [] -> false
           | (Letter (a,b,l))::q when a = W.get sm i -> 
               if n = 1 then b else exist (W.sub sm (i+1) (n-1)) l       
           | (Letter (a,b,l))::q when a = W.get sm i -> 
               exist sm q
     in aux m 0 (W.length m)
 
     let rec insert m d = 
       let aux sm i n = 
         if n = 0 then d 
         else 
           match d with 
               [] -> 
                 let aux = insert (W.sub sm (i+1) (n-1)) [] in
                 [ Letter (W.get sm i, n = 1, aux) ] 
             | (Letter(a,b,l))::q when a = W.get sm i ->
                 if n = 1 then (Letter(a,true,l))::q
                 else Letter(a,b,add (W.sub sm (i+1) (n-1)) l)::q
             | (Letter(a,b,l))::q -> (Letter(a,b,l))::(ajoute sm q)
       in aux m 0 (W.length m)
 
     let rec select n d = match d with 
         [] -> []
       | (Letter(a,b,l))::q when n=1 -> 
           let f (Letter(a,b,_)) = if b then W.of_alpha a else W.null in 
           List.filter ((<>) W.null) (List.map f d) 
       | (Letter(a,b,l))::q  -> 
           let r = select (n-1) l and r2 = select n q in
           let pr = List.map (function s -> W.concat (W.of_alpha a) s) r in
           pr@r2
   end ;;
Characters 161-407:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
_::_
Characters 853-854:
This expression has type t = node list but is here used with type W.t dlist

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.


# module Chars =
   struct
     type alpha = char
     type t = string
     let null = ""
     let of_alpha c = String.make 1 c 
     let get s i = 
       try s.[i] 
       with Invalid_argument(_) -> raise (Invalid_argument "Chars.get")
     let sub s i1 i2 =
       try String.sub s i1 i2 
       with Invalid_argument(_) -> raise (Invalid_argument "Chars.sub")
     let length = String.length
     let concat = (^)
   end ;;
module Chars :
  sig
    type alpha = char
    and t = string
    val null : string
    val of_alpha : char -> string
    val get : string -> int -> char
    val sub : string -> int -> int -> string
    val length : string -> int
    val concat : string -> string -> string
  end

# module CharsDic = LexTree(Chars) ;;
Characters 19-26:
Unbound module LexTree