Structures, signatures, functors

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

FP
 SML
  SML97
   Structures

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

window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

SML:
:: cons
[x1,...] list
[ ] list
@ append
fn =>  &lambda .
: has type
Compared

structure, struct; signature, sig; functor

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 31-Oct-2014 15:01:55 EST.