|
Note that the declaration of a structure, signature or functor
is not a declaration (dec).
It can only occur at the top-level of a program.
A structure, signature or functor is used in a specification (spec)
not in an expression or a normal declaration (dec)
(except to open a structure).
Although
structure:signature is "like"
value:type and
a functor is "like" a function,
it is only a matter of "like".
Structures, signatures and functors belong very much to compile-time.
E.g. Traversable
Here is a simple example of Traversable data structures --
where the elements can be extracted in some systematic order.
For this example, a structured data type is Traversable if
it has functions (~methods)
initialise, next, advance and toList,
an elementType, and a state for a traverse.
For example,
't list and 't tree
can be made Traversable.
signature Traversable = sig
type elementType;
type ds;
type state;
val initialise : ds -> state; (* state 0 *)
val next : state -> elementType option;
val advance : state -> state
val toList : ds -> elementType list
end;
(* --------------------------------------------------- *)
functor TravList( type et ) :Traversable = struct
type elementType = et;
type ds = et list;
type state = et list;
fun initialise v = v;
fun next [] = NONE
| next (x::_) = SOME x
fun advance (_::s) = s
fun toList v = (* trivial for the case of lists *)
let fun scan s =
case next s of NONE => []
| SOME x => x::(scan(advance s))
in scan(initialise v)
end
end;
structure TList = TravList( type et = char );
(* e.g. *) TList.toList (explode "abcd");
datatype 't tree = leaf of 't (* strict binary trees *)
| fork of 't*('t tree)*('t tree)
functor TravTree( type et ) :Traversable = struct
type elementType = et;
type ds = et tree;
type state = et tree list;
fun initialise t = [t];
fun next [] = NONE
| next ((fork(e,l,r))::_) = SOME e
| next ((leaf e) ::_) = SOME e ;
fun advance ((fork(e,l,r))::s') = s' @ [l, r]
| advance (((leaf e)) ::s') = s' ;
fun toList v = (* in breadth-first order *)
let fun scan s =
case next s of NONE => []
| SOME x => x :: (scan(advance s))
in scan(initialise v)
end
end;
structure TTree = TravTree( type et = int );
(* e.g. *) TTree.toList (fork(1,(fork(2,leaf 3, leaf 4)),
(leaf 5)))
(* Structures, signatures, functors LA, CSSE, *)
(* Monash .au 23/6/2005 *)
|
|
www #ad:
SML:
:: | cons |
[x1,...] | list |
[ ] | list |
@ | append |
fn => | &lambda . |
: | has type |
Compared
|
structure, struct; signature, sig; functor
|
|
|