# Using Functors

Since functors are really just parameterized modules, we can use them to produce functions that are parameterized on any structure that matches a signature. That can help to eliminate code duplication. Here are two examples of doing that.

## Example 1: Producing a Test Suite for Multiple Structures

Recall our data structures for stacks:

```
module type StackSig = sig
type 'a t
val empty : 'a t
val push : 'a -> 'a t -> 'a t
val peek : 'a t -> 'a
end
module ListStack = struct
type 'a t = 'a list
let empty = []
let push x s = x::s
let peek = function [] -> failwith "empty" | x::_ -> x
end
(* called MyStack because the standard library already has a Stack *)
module MyStack = struct
type 'a t = Empty | Entry of 'a * 'a t
let empty = Empty
let push x s = Entry (x, s)
let peek = function Empty -> failwith "empty" | Entry(x,_) -> x
end
```

Suppose we wanted to write code that would test a `ListStack`

:

```
assert (ListStack.(empty |> push 1 |> peek) = 1)
```

Unfortunately, to test a `MyStack`

, we'd have to duplicate that code:

```
assert (MyStack.(empty |> push 1 |> peek) = 1)
```

And if we had other stack implementations, we'd have to duplicate the test for them, too. That's not so horrible to contemplate if it's just one test case for a couple implementations, but if it's hundreds of tests for even a couple implementations, that's just too much duplication to be good software engineering.

Functors offer a better solution. We can write a functor that is parameterized on the stack implementation, and produces the test for that implementation:

```
module StackTester (S:StackSig) = struct
assert (S.(empty |> push 1 |> peek) = 1)
end
module MyStackTester = StackTester(MyStack)
module ListStackTester = StackTester(ListStack)
```

Now we can factor out all our tests into the functor `StackTester`

, and
when we apply that functor to a stack implementation, we get a set of
tests for that implementation. Of course, this would work with OUnit
as well as assertions.

## Example 2: Adding a Function to Multiple Structures

Earlier, we tried to add a function `add_all`

to both `ListSetNoDups`

and `ListSetDups`

without having any duplicated code, but we didn't
totally succeed. Now let's really do it right.

The problem we had earlier was that we needed to parameterize the
implementation of `add_all`

on the `add`

function in the set
data structure. We can accomplish that parameterization with
a functor.

Here is a functor that takes in a structure named `S`

that matches the `Set`

signature, then produces a new structure having a single function named
`add_all`

in it:

```
module AddAll(S:Set) = struct
let add_all lst set =
let add' s x = S.add x s in
List.fold_left add' set lst
end
```

Notice how the functor, in its body, uses `S.add`

. It takes the implementation
of `add`

from `S`

and uses it to implement `add_all`

, thus solving the
exact problem we had before when we tried to use includes.

When we apply `AddAll`

to our set implementations, we get structures
containing an `add_all`

function for each implementation:

```
# module AddAllListSetDups = AddAll(ListSetDups);;
module AddAllListSetDups :
sig
val add_all : 'a list -> 'a ListSetDups.t -> 'a ListSetDups.t
end
# module AddAllListSetNoDups = AddAll(ListSetNoDups);;
module AddAllListSetNoDups :
sig
val add_all : 'a list -> 'a ListSetNoDups.t -> 'a ListSetNoDups.t
end
```

So the functor has enabled the code reuse we couldn't get before:
we now can implement a single `add_all`

function and from it derive
implementations for two different set structures.

But that's the **only** function those two structures contain. Really
what we want is a full set implementation that also contains the
`add_all`

function. We can get that by combining includes with functors:

```
module ExtendSet(S:Set) = struct
include S
let add_all lst set =
let add' s x = S.add x s in
List.fold_left add' set lst
end
```

That functor takes a set structure as input, and produces a structure that contains
everything from that set structure (because of the `include`

) as well as
a new function `add_all`

that is implemented using the `add`

function from the
set.

When we apply the functor, we get a very nice set data structure as a result:

```
# module ListSetNoDupsExtended = ExtendSet(ListSetNoDups);;
module ListSetNoDupsExtended :
sig
type 'a t = 'a ListSetNoDups.t
val empty : 'a t
val mem : 'a -> 'a t -> bool
val add : 'a -> 'a t -> 'a t
val elts : 'a t -> 'a list
val add_all : 'a list -> 'a t -> 'a t
end
```

Notice how the output structure records the fact that its type `t`

is the
same type as the type `t`

in its input structure. They share it because
of the `include`

.

Stepping back, what we just did bears more than a passing resemblance
to what you're used to doing in CS 2110 with class extension in Java. We
created a base module and extended its functionality with new code
while preserving its old functionality. But whereas class extension
necessitates that the newly extended class is a subtype of the old,
and that it still has all the old functionality, OCaml functors
are more fine-grained in what they can accomplish. We can choose
whether they include the old functionality. And no subtyping relationships
are necessarily involved. Moreover, the functor we wrote can be used
to extend **any** set implementation with `add_all`

, whereas class
extension applies to just a **single** base class. There are ways
of achieving something similar in Java with *mixins*, which weren't
supported before Java 1.5.