Standard ML: Datatype vs. Structure

Question

I'm reading through Paulson's ML For the Working Programmer and am a bit confused about the distinction between datatypes and structures.

On p. 142, he defines a type for binary trees as follows:

datatype 'a tree = Lf
    | Br of 'a * 'a tree * 'a tree;

This seems to be a recursive definition where 'a denotes some fixed type. So any time I see 'a, it must refer to the same type throughout.

On p. 148, he discusses a structure for binary trees:

"...we have been following an imaginary ML session in which we typed in the tree functions one at a time. Now we ought to collect the most important of those functions into a structure, called Tree. We really must do so, because one of our functions (size) clashes with a built-in function. One reason for using structures is to prevent such name clashes.

We shall, however, leave the datatype declaration of tree outside of the structure. If it were inside, we should be forced to refer to the constructors by Tree.Lf and Tree.Br, which would make our patters unreadable. Thus, in the sequel, imagine that we have made the following declarations:

datatype 'a tree = Lf
    | Br of 'a * 'a tree * 'a tree;

structure Tree = 
    struct
    fun size Lf = 0
        | size (Br( v, t1, t2)) = 1 + size t1 + size t2;
    fun depth...
    etc...
    end;

I'm a little confused.

1) What is the relationship between a datatype and a structure?

2) What is the role of "struct" within the structure definition?

3) Later on, Paulson discusses a structure for dictionaries as binary search trees. He does the following:

structure Dict : DICTIONARY = 
    struct

    type key = string;
    type 'a t = (key * 'a) tree;
    val empty = Lf;

    <a bunch of functions for dictionaries>

This makes me think struct specifies the different primitive or compound types involved int he definition of a Dict.

That's a really fuzzy definition though. Anyone like to clarify?

Thanks for the help, bclayman

Answer 1

A structure is a module. Everything between the struct and end keywords forms the body of this module. Similarly, you can view a signature as the description of an abstract module interface. Ascribing a signature to a structure (like the : DICTIONARY syntax does in your example) limits the exports of the module to what is specified in that signature (by default, everything would be accessible). That allows you to hide implementation details of a module.

However, ML modules are much richer than that. They can be arbitrarily nested. There are also functors, which are effectively functions from modules to modules ("parameterised modules", if you want). Altogether, the module language in ML forms a full functional language on its own, with structures as the basic entities, functors over them, and signatures describing the "types" of such modules. This little language is a layer on top of the so-called core language, where ordinary values and types live.

So, to answer your individual questions:

1) There is no specific relationship between the datatype and the structure. The latter simply uses the former.

2) struct-end is simply a keyword pair to delimit the structure body (languages in C tradition would probably use curly braces there).

3) As explained above, a structure is a basic module. It can contain (and export) arbitrary other language entities, including other modules. By grouping definitions together, and potentially hiding some of them through a signature ascription, you can express namespacing and encapsulation (in particular, abstract data types).

I should also note that Paulson's book is outdated regarding its description of modules, as it predates the current language version. In particular, it does not describe how to express abstract data types through modules, but instead introduces the obsolete abstype declaration which nobody has been using in almost 20 years. A more extensive and up-to-date introduction to modular programming in ML can be found in Harper's Programming in Standard ML.