## Exercises

### Classes and Modules for Data Structures

We wish to construct class hierarchies based on the application of functors for classical data structures.

We define the following structures

```# module` `type` `ELEMENT` ``=`` `` `` `` `sig` `` `` `` `` `class` `element` ``:`` `` `` `` `` `` `` `` `` `string` `->` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `` `` `` `method` `to_string` ``:`` `unit` `->` `string` `` `` `` `` `` `` `` `` `` `` `method` `of_string` ``:`` `string` `->` `unit` `` `` `` `` `` `` `` `` `end` `` `` `end` `;;# module` `type` `STRUCTURE` ``=`` `` `` `` `sig` `` `` `` `` `class` ``[`'a`]`` `structure` ``:`` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `` `method` `add` ``:`` `'a` `->` `unit` `` `` `` `` `` `` `` `` `method` `del` ``:`` `'a` `->` `unit` `` `` `` `` `` `` `` `` `method` `mem` ``:`` `'a` `->` `bool` `` `` `` `` `` `` `` `` `method` `get` ``:`` `unit` `->` `'a` `` `` `` `` `` `` `` `` `` `method` `all` ``:`` `unit` `->` `'a` `list` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `method` `iter` ``:`` `('a` `->` `unit)` `->` `unit` `` `` `` `` `` `` `end` `` `` `end` `;;

```
1. Write a module with 2 parameters M1 and M2 of types ELEMENT and STRUCTURE, constructing a sub-class of ['a] structure in which 'a is constrained to M1.element.
```# module` `Struct_Elmt` `(E`:`ELEMENT)` `(S`:`STRUCTURE)` ``=`` `` `` `` `struct` `` `` `` `` `class` `e_structure` ``=`` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `inherit` ``[`E.element`]`` `S.structure` `` `` `` `` `` `` `` `` `end` `` `` `end` `;;`module Struct_Elmt :``  functor(E : ELEMENT) ->``    functor(S : STRUCTURE) ->``      sig``        class e_structure :``          object``            method add : E.element -> unit``            method all : unit -> E.element list``            method del : E.element -> unit``            method get : unit -> E.element``            method iter : (E.element -> unit) -> unit``            method mem : E.element -> bool``          end``      end`

```

2. Write a simple module Integer which respects the signature ELEMENT.
```# module` `Entier` ``:`` `ELEMENT` ``=`` `` `` `` `struct` `` `` `` `` `` `class` `element` `v` ``=`` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `` `val` `mutable` `n` ``=`` `int_of_string` `v` `` `` `` `` `` `` `` `` `` `` `method` `to_string` `()` ``=`` `string_of_int` `n` `` `` `` `` `` `` `` `` `` `method` `of_string` `x` ``=`` `n` ``<-`` `(int_of_string` `x)` `` `` `` `` `` `` `end` `` `` `end` `;;`module Entier : ELEMENT`

```

3. Write a simple moduleStack which respects the signature STRUCTURE.
```# module` `Pile` ``:`` `STRUCTURE` ``=`` `` `` `struct` `` `` `` `` `class` ``[`'a`]`` `structure` ``=`` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `val` `mutable` `p` ``=`` `(` `[]` ``:`` `'a` `list` `)` `` `` `` `` `` `` `` `` `method` `add` `x` ``=`` `p` ``<-`` `x::p` `` `` `` `` `` `` `` `` `` `method` `del` `x` ``=`` `p` ``<-`` `List.filter` `((`<>`)` `x)` `p` `` `` `` `` `` `` `` `` `method` `mem` `x` ``=`` `List.mem` `x` `p` `` `` `` `` `` `` `` `` `` `method` `get` `()` ``=`` `List.hd` `p` `` `` `` `` `` `` `` `` `method` `all` `()` ``=`` `p` `` `` `` `` `` `` `` `` `method` `iter` `f` ``=`` `List.iter` `f` `p` `` `` `` `` `` `` `` `end` `` `` `end` `;;`module Pile : STRUCTURE`

```

4. Apply the functor to its two parameters.
```# module` `Pile_Entier` ``=`` `Struct_Elmt(Entier)(Pile)` `;;`module Pile_Entier :``  sig``    class e_structure :``      object``        method add : Entier.element -> unit``        method all : unit -> Entier.element list``        method del : Entier.element -> unit``        method get : unit -> Entier.element``        method iter : (Entier.element -> unit) -> unit``        method mem : Entier.element -> bool``      end``  end`

```

5. Modify the functor by adding the methods to_string and of_string.
```# let` `split` `c` `s` ``=`` `` `` `` `let` `suffix` `s` `i` ``=`` `` `` `` `` `` `try` `` `String.sub` `s` `i` `((String.length` `s)`-`i)` `` `` `` `` `` `with` `Invalid_argument(`"String.sub"`)` `->` ``""`` `` `` `` `in` `` `` `let` `rec` `split_from` `n` ``=`` `` `` `` `` `` `try` `` `let` `p` ``=`` `String.index_from` `s` `n` `c` `` `` `` `` `` `` `` `` `` `` `in` `(String.sub` `s` `n` `(p`-`n))` `::` `(split_from` `(p`+``1`))` `` `` `` `` `` `with` `Not_found` `->` ``[`` `suffix` `s` `n` ``]`` `` `` `` `in` `` `` `` `if` `s`=``""`` `then` `[]` `else` `split_from` ``0`` `;;`val split : char -> string -> string list = <fun>`# module` `Elmt_Struct` `(E`:`ELEMENT)` `(S`:`STRUCTURE)` ``=`` `` `` `` `struct` `` `` `` `` `class` `element` `v` ``=`` `` `` `` `` `` `` `` `object` `(self)` `` `` `` `` `` `` `` `` `val` `n` ``=`` `new` `S.structure` `` `` `` `` `` `` `` `` `` `method` `to_string` `()` ``=`` `` `` `` `` `` `` `` `` `` `` `` `let` `res` ``=`` `ref` ``""`` `in` `` `` `` `` `` `` `` `` `` `` `` `let` `f` `x` ``=`` `res` ``:=`` ``!`res` ``^`` `((x#to_string` `())` `` ``^`` ``" "`)` `in` `` `` `` `` `` `` `` `` `` `` `` `n#iter` `f` `;` `` `` `` `` `` `` `` `` `` `` ``!`res` `` `` `` `` `` `` `` `` `` `method` `of_string` `x` ``=`` `` `` `` `` `` `` `` `` `` `` `` `let` `l` ``=`` `split` ``' '`` `x` `in` `` `` `` `` `` `` `` `` `` `` `` `List.iter` `(fun` `x` `->` `n#add` `(new` `E.element` `x))` `l` `` `` `` `` `` `` `` `` `initializer` `self#of_string` `v` `` `` `` `` `` `` `` `` `end` `` `` `end` `;;`module Elmt_Struct :``  functor(E : ELEMENT) ->``    functor(S : STRUCTURE) ->``      sig``        class element :``          string ->``          object``            val n : E.element S.structure``            method of_string : string -> unit``            method to_string : unit -> string``          end``      end`

```

6. Apply the functor again , and then apply it to the result .
```# module` `Entier_Pile` ``=`` `Elmt_Struct` `(Entier)` `(Pile)` `;;`module Entier_Pile :``  sig``    class element :``      string ->``      object``        val n : Entier.element Pile.structure``        method of_string : string -> unit``        method to_string : unit -> string``      end``  end`

```
```# module` `Entier_Pile_Pile` ``=`` `` `Elmt_Struct` `(Entier_Pile)` `(Pile)` `;;`module Entier_Pile_Pile :``  sig``    class element :``      string ->``      object``        val n : Entier_Pile.element Pile.structure``        method of_string : string -> unit``        method to_string : unit -> string``      end``  end`

```

### Abstract Types

Continuing from the previous exercise, we wish to implement a module with signature ELEMENT of which the class element uses one instance variable of abstract type.

We define the following parameterized type:
```# type` `'a` `t` ``=`` `{mutable` `x` ``:`` `'a` `t;` `f` ``:`` `'a` `t` `->` `unit};;

```

1. Write the functions apply, from_string and to_string. These last two functions will use the Marshal module.
```# let` `apply` `val_abs` ``=`` `val_abs`.`f` `val_abs`.`x` `;;`val apply : 'a t -> unit = <fun>`# let` `from_string` `s` ``=`` `Marshal.from_string` `s` ``0`` `;;`val from_string : string -> 'a = <fun>`# let` `to_string` `v` ``=`` `Marshal.to_string` `v` ``[`Marshal`.`Closures`]`` `;;`val to_string : 'a -> string = <fun>`

```

2. Write a signature S which corresponds to the signature previously inferred by abstracting the type t.
```# module` `type` `S` ``=`` `` `` `` `sig` `` `` `` `` `` `type` `t` `` `` `` `` `val` `apply` ``:`` `t` `->` `unit` `` `` `` `` `val` `from_string` ``:`` `string` `->` `t` `` `` `` `` `val` `to_string` ``:`` `t` `->` `string` `` `` `` `end` `;;`module type S =``  sig``    type t``    val apply : t -> unit``    val from_string : string -> t``    val to_string : t -> string``  end`

```

3. Write a functor which takes a parameter with signature S and returns a module of which the signature is compatible with ELEMENT.
```# module` `Element_of` `(M`:`S)` ``=`` `` `` `` `struct` `` `` `` `` `` `class` `element` `v` ``=`` `` `` `` `` `` `` `` `object` `` `` `` `` `` `` `` `` `` `` `` `val` `mutable` `n` ``=`` `M.from_string` `v` `` `` `` `` `` `` `` `` `method` `to_string` `()` ``=`` `M.to_string` `n` `` `` `` `` `` `` `` `` `` `method` `of_string` `x` ``=`` `n` ``<-`` `M.from_string` `x` `` `` `` `` `` `` `` `end` `` `` `end` `;;`module Element_of :``  functor(M : S) ->``    sig``      class element :``        string ->``        object``          val mutable n : M.t``          method of_string : string -> unit``          method to_string : unit -> string``        end``    end`

```

4. Use the resulting module as the parameter of the module from the previous exercise.
```# module` `Abstrait_Pile` `(M`:`S)` ``=`` `` `Elmt_Struct` `(Element_of(M))` `;;`module Abstrait_Pile :``  functor(M : S) ->``    functor(S : STRUCTURE) ->``      sig``        class element :``          string ->``          object``            val n : Element_of(M).element S.structure``            method of_string : string -> unit``            method to_string : unit -> string``          end``      end`

```