Thông thường để giải quyết bài toán một thuật toán tổng quát cho nhiều kiểu dữ liệu thì dùng Polymorphism. Nhưng cách này ta phải implement chi tiết cho từng loại kiểu dữ liệu khác nhau.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Ví dụ: Interface Set với các hàm Add, Remove, Empty.
Với kiểu dữ liệu String thì ta phải cài đặt 3 hàm Add, Remove và Empty cho String.
Với kiểu dữ liệu Int thì ta phải cài đặt 3 hàm Add, Remove và Empty cho Int.
Cách làm này dường như phải cài đặt nhiều hơn và khó bảo trì hơn.
Nếu khai báo bằng functor thì Interface Set khi này có thể được truyền như là tham số, tuỳ thuộc kiểu dữ liệu truyền vào là String hay Int mà Interface này có thể làm phép tính trên đó dễ dàng.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Phần quan trọng nhất giải thích về functors là đây:
A functor is a mapping from modules to modules.
It allows the construction of a module parameterized by one or more other modules.
Functors allow us to create a set module that is parameterized by another module that does the equality testing, thereby allowing the same code to be used for different equality tests.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Lecture 9: Functors — Parameterized Modules
For the past few classes we have been considering abstraction and modular design, primarily through the use of the module mechanism in OCaml. We have seen that good design principles include writing clear specifications of interfaces, independent of the actual implementation. We have also seen that writing good documentation of the implementation is important. Today we will consider another means of abstraction calledfunctors, a construct that enables modules to be combined by parameterizing a module in terms of other modules.
Consider the SET data abstraction that we have looked at during the past few classes:
module type SET = sig
type 'a set
val empty : 'a set
val mem : 'a -> 'a set -> bool
val add : 'a -> 'a set -> 'a set
val rem : 'a -> 'a set -> 'a set
val size: 'a set -> int
val union: 'a set -> 'a set -> 'a set
val inter: 'a set -> 'a set -> 'a set
end
While this interface uses polymorphism to enable sets with different types of elements to be created, any implementation of this signature needs to use the built-in = function in testing whether an element is a member of such a set. Thus we cannot for example have a set of strings where comparison of the elements is done in a case-insensitive manner, or a set of integers where elements are considered equal when their magnitudes (absolute values) are equal. We could write two separate signatures, one for sets with string elements and one for sets with integer elements, and then in the implementation of each signature use an appropriate comparison function. However this would yield a lot of nearly duplicated code, both in the signatures and in the implementation. Such nearly duplicated code is more work to write and maintain and more importantly is often a source of bugs when things are changed in one place and not another.
A functor is a mapping from modules to modules. It allows the construction of a module parameterized by one or more other modules. Functors allow us to create a set module that is parameterized by another module that does the equality testing, thereby allowing the same code to be used for different equality tests. To make this concrete, we will consider an example using the following signatures:
module type EQUAL = sig
type t
val equal : t -> t -> bool
end
module type SETFUNCTOR =
functor (Equal : EQUAL) ->
sig
type elt = Equal.t
type set
val empty : set
val mem : elt -> set -> bool
val add: elt -> set -> set
val size: set -> int
end
The signature EQUAL describes the input type for the functor. To implement EQUAL, a module need only specify a type t and a comparison function equal : t -> t -> bool, but these can be anything.
The signature SETFUNCTOR describes the type of the functor. This differs from the SET interface in several respects. First, the keyword functor indicates that it is a functor accepting a parameter, which in this case is any module of type EQUAL. Note how the syntax is reminiscent of the notation for functions. The parameter is referenced by the name Equal in the body of SETFUNCTOR, but that does not have to be its actual name.
The body of SETFUNCTOR describes the type of the module that will be produced. In the body, instead of the polymorphic 'a of SET, the type of the elements is named elt and is defined to be the same as the type t of the module Equal, whatever that is. There is also a fixed but unspecified type set, along with some set operations of the appropriate types, specified in terms of elt and set. (We have omitted a few of the operations for simplicity of the presentation, although they could easily be added back in.)
Now we are ready to define a functor implementing the SETFUNCTOR signature.
module MakeSet : SETFUNCTOR =
functor (Equal : EQUAL) ->
struct
open Equal
type elt = t
type set = elt list
let empty = []
let mem x = List.exists (equal x)
let add x s = if mem x s then s else x :: s
let size = List.length
end
First, the header
module MakeSet : SETFUNCTOR =
indicates that we are defining an implementation named MakeSet of the functor type SETFUNCTOR. The second line
functor (Equal : EQUAL) ->
indicates that we are defining a functor with parameter Equal of type EQUAL. Again, the module implementingEQUAL is referenced by the name Equal in the body of MakeSet, but that does not have to be its actual name. In general there can be any number of parameter modules, each of which must be specified with a name and signature. Note that these parameters can only be modules, including other parameterized modules—they cannot be first-class objects of the language such as functions or other types.
Finally, the body of MakeSet between struct and end describes the implementation of the output module. This module must satisfy the signature described in the body of SETFUNCTOR.
The body of MakeSet is like the body of any other module. In this example the open directive is used so that the names t and equal can be used without qualifying them as Equal.t and Equal.equal.
It is also worth noting the partial evaluation of both equal and List.exists in:
let mem x = List.exists (equal x)
To write it out in full, we might have written
let mem x s = List.exists (fun y -> equal x y) s
but the shorter version is equivalent. In both cases, we are using the fact that fun z -> f z is equivalent to just f. For example, both fun y -> equal x y and equal x are functions that test whether a given element is equal to the value of x.
Now we show how to create modules using the functor MakeSet. To do this, we need an implementation of the EQUAL signature. Say, for example, we want to test equality of strings in a case-independent fashion. Here is a module that does this.
module StringNoCase =
struct
type t = string
let equal s1 s2 =
String.lowercase s1 = String.lowercase s2
end
Now we can use MakeSet to create a string set module with case-insensitive equality by applying it toStringNoCase:
module SSet = MakeSet (StringNoCase)
Evaluating this expression, the interpreter prints out:
module SSet :
sig
type elt = StringNoCase.t
type set = MakeSet(StringNoCase).set
val empty : set
val mem : elt -> set -> bool
val add : elt -> set -> set
val size : set -> int
end
That is, the SSet module defines the types set and elt and the function mem, add, and size, but the actual implementation is hidden.
Now we can use this set abstraction to create and manipulate sets of strings with case-insensitive comparison.
# let s = SSet.add "I like CS 3110" SSet.empty;;
val s : SSet.set =
# SSet.mem "i LiKe cs 3110" s;;
- : bool = true
# SSet.size s;;
- : int = 1
After doing this, creating a module for sets of integers using absolute value comparison involves almost no additional code. We only need to create another module implementing EQUAL and use it as the parameter toMakeSet:
module IntAbs = struct
type t = int
let equal i1 i2 = abs i1 = abs i2
end
module ISet = MakeSet (IntAbs)
Now we can use this set abstraction to create and manipulate sets of integers with absolute value comparison:
# let i = ISet.add 1 ISet.empty;;
val i : ISet.set =
# ISet.mem 1 i;;
- : bool = true
# ISet.mem (-1) i;;
- : bool = true
# ISet.size i;;
- : int = 1
# let i = ISet.add (-1) i;;
val i : ISet.set =
# ISet.size i;;
- : int = 1
Caveats
There are a few subtleties with functors that are worth mentioning. First, note that we did not specify the signature EQUAL when we defined StringNoCase. We might have written
module StringNoCase : EQUAL =
struct
type t = string
let equal s1 s2 =
String.lowercase s1 = String.lowercase s2
end
but this would have been a bad idea:
# module SSet = MakeSet (StringNoCase);;
module SSet :
sig
type elt = StringNoCase.t
type set = MakeSet(StringNoCase).set
val empty : set
val mem : elt -> set -> bool
val add : elt -> set -> set
val size : set -> int
end
# let s = SSet.add "I like CS 3110" SSet.empty;;
Characters 17-33:
let s = SSet.add "I like CS 3110" SSet.empty;;
^^^^^^^^^^^^^^^^
Error: This expression has type string but is here used with type
SSet.elt = StringNoCase.t
The issue here is that the signature EQUAL does not expose the type definition type t = string in the implementation StringNoCase, so the functor is not free to use that information. It may only deal with the module StringNoCase through its signature. This is consistent with the principle of information hiding through the use of signatures. Thus the module that is produced does not know that StringNoCase.t is reallystring. But if we omit the EQUAL, then the signature of StringNoCase is inferred from the implementation:
# module StringNoCase =
struct
type t = string
let equal s1 s2 =
String.lowercase s1 = String.lowercase s2
end;;
module StringNoCase :
sig
type t = string
val equal : string -> string -> bool
end
(formatting inserted by hand for clarity). You can see that here the type definition type t = string is exposed, and the functor may now use that information.
Contravariance
Another good reason for not specifying the signature is that modules can implement lots of different signatures and can be used in different ways. For example, if we had defined
module StringNoCase =
struct
type t = string
let compare s1 s2 =
String.compare (String.lowercase s1) (String.lowercase s2)
let equal s1 s2 = compare s1 s2 = 0
end
then StringNoCase implements not only EQUAL, but also Map.OrderedType and Set.OrderedType from the OCaml library, so it can also be used as an argument to Map.Make and Set.Make. If we had specifiedEQUAL, then we would have precluded those uses.
We can always restrict it if we like:
# module StringNoCaseEq = (StringNoCase : EQUAL);;
module StringNoCaseEq : EQUAL
The modules StringNoCaseEq and StringNoCase have the same implementation, but their signatures are different. This is very much like a type upcast in Java. It is an upcast because it is going from a more specific specification (fewer instances) to a more general specification (more instances), which means it can be used as the argument to fewer functors. This inverse relationship is known as contravariance.
...with type...
For clarity, we may wish to define the result signature of a functor independently from the signature of the functor itself. So instead of the definition of SETFUNCTOR as given above, we may wish to write something like
module type SET =
sig
type elt
type set
val empty : set
val mem : elt -> set -> bool
val add: elt -> set -> set
val size: set -> int
end
module type SETFUNCTOR = functor (Equal : EQUAL) -> SET
The difficulty here is that we need a way to equate the type elt of SET with Equal.t. We could do that in the previous definition of SETFUNCTOR by writing type elt = Equal.t in the body, but here there is no parameter module Equal around when we define SET.
To handle this, OCaml allows you to write
module type SETFUNCTOR =
functor (Equal : EQUAL) -> SET with type elt = Equal.t
Now it can link up the two types:
# module type SETFUNCTOR =
functor (Equal : EQUAL) -> SET with type elt = Equal.t;;
module type SETFUNCTOR =
functor (Equal : EQUAL) ->
sig
type elt = Equal.t
type set
val empty : set
val mem : elt -> set -> bool
val add : elt -> set -> set
val size : set -> int
end
