Previous Contents Next

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.

    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.

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


  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.

    # 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


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


  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.

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


  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.

    # 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


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


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


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

  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.

    # 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


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

    # 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


  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.

    # 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

Previous Contents Next