Structures

Structures, signatures, functors

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 *)