The Haskell 1.4 Report
top | back | next | contents | function index

5  Modules

A module defines a collection of values, datatypes, type synonyms, classes, etc. (see Section 4) in an environment created by a set of imports, resources brought into scope from other modules, and exports some of these resources, making them available to other modules. We use the term entity to refer to a value, type, or classes defined in, imported into, or perhaps exported from a module.

A Haskell program is a collection of modules, one of which, by convention, must be called Main and must export the value main. The value of the program is the value of the identifier main in module Main, and main must have type IO () (see Section 7).

Modules may reference other modules via explicit import declarations, each giving the name of a module to be imported and specifying its entities to be imported. Modules may be mutually recursive.

The name-space for modules is flat, with each module being associated with a unique module name (which are Haskell identifiers beginning with a capital letter; i.e. modid). There is one distinguished module, Prelude, which is imported into all programs by default (see Section 5.3), plus a set of standard library modules that may be imported as required (see the Haskell Library Report[8]).

5.1  Module Structure

A module defines a mutually recursive scope containing declarations for value bindings, data types, type synonyms, classes, etc. (see Section 4).

module -> module modid [exports] where body
| body
body -> { [impdecls ;] [[fixdecls ;] topdecls [;]] }
| { impdecls [;] }
modid -> conid
impdecls -> impdecl1 ; ... ; impdecln   (n>=1)
topdecls -> topdecl1 ; ... ; topdecln   (n>=0)

A module begins with a header: the keyword module, the module name, and a list of entities (enclosed in round parentheses) to be exported. The header is followed by an optional list of import declarations that specify modules to be imported, optionally restricting the imported bindings. This is followed by an optional list of fixity declarations and the module body. The module body is simply a list of top-level declarations (topdecls), as described in Section 4.

An abbreviated form of module, consisting only of the module body, is permitted. If this is used, the header is assumed to be `module Main(main) where'. If the first lexeme in the abbreviated module is not a {, then the layout rule applies for the top level of the module.

5.1.1  Export Lists

exports -> ( export1 , ... , exportn [ , ] )   (n>=0)
export -> qvar
| qtycon [(..) | ( qcname1 , ... , qcnamen )]   (n>=0)
| qtycls [(..) | ( qvar1 , ... , qvarn )]   (n>=0)
| module modid
qcname -> qvar | qcon

An export list identifies the entities to be exported by a module declaration. A module implementation may only export an entity that it declares, or that it imports from some other module. If the export list is omitted, all values, types and classes defined in the module are exported, but not those that are imported.

Entities in an export list may be named as follows:

  1. A value, field name, or class method, whether declared in the module body or imported, may be named by giving the name of the value as a qvarid. Operators should be enclosed in parentheses to turn them into qvarid's.
  2. An algebraic datatype T declared by a data or newtype declaration may be named in one of three ways: Data constructors cannot be named in export lists in any other way.
  3. A type synonym T declared by a type declaration may be named by the form T.
  4. A class C with operations f1,...,fn declared in a class declaration may be named in one of three ways:
  5. The set of all entities brought into scope from a module m by one or more unqualified import declarations may be named by the form `module m', which is equivalent to listing all of the entities lowed by e type variables. It follows from Rule 1 that if all top-level declaration groups are unrestricted, then Rule 2 is automatically satisfied.

    Rule 1 is required for two reasons, both of which are fairly subtle. First, it prevents computations from being unexpectedly repeated. For example, genericLength is a standard function (in library List) whose type is given by

    genericLength :: Num a => [b] -> a

    Now consider the following expression:

    let { len = genericLength xs } in (len, len)

    It looks as if len should be computed only once, but without Rule 1 it might be computed twice, once at each of two different overloadings. If the programmer does actually wish the computation to be repeated, an explicit type signature may be added:

    let { len :: Num a => a; len = genericLength xs } in (len, len)

    When non-simple pattern bindings are used, the types inferred are always monomorphic in their constrained type variables, irrespective of whether a type signature is provided. For example, in

    (f,g) = ((+),(-))

    both f and g are monomorphic regardless of any type signatures supplied for f or g.

    Rule 1 also prevents ambiguity. For example, consider the declaration group

    [(n,s)] = reads t

    Recall that reads is a standard function whose type is given by the signature

    reads :: (Read a) => String -> [(a,String)]

    Without Rule 1, n would be assigned the type forall a. Read a =>a and s the type forall a. Read a =>String. The latter is an invalid type, because it is inherently ambiguous. It is not possible to determine at what overloading to use s. Rule 1 makes n and s monomorphic in a.

    Lastly, Rule 2 is required because there is no way to enforce monomorphic use of an exported binding, except by performing type inference on modules outside the current module. Exported variables are handled in the same way as non-exported ones even though their usage outside the module could theoreticly be used to determine monomorphic type. For example, in the program

    module M(x) where
    x = 1

    the monomorphism restriction prevents the type of x from being generalized to Num a => a. Since references to x outside module M cannot be used to determine the type of x, the defaulting rule (see Section 4.3.4) assigns the type Int to x.

    The monomorphism rule has a number of consequences for the programmer. Anything defined with function syntax usually generalizes as a function is expected to. Thus in

    f x y = x+y

    the function f may be used at any overloading in class Num. There is no danger of recomputation here. However, the same function defined with pattern syntax:

    f = \x -> \y -> x+y

    requires a type signature if f is to be fully overloaded. Many functions are most naturally defined using simple pattern bindings; the user must be careful to affix these with type signatures to retain full overloading. The standard prelude contains many examples of this:

    sum            :: (Num a) => [a] -> a
    sum            =  foldl (+) 0  

    4.6  Kind Inference

    This section describes the rules that are used to perform kind inference, i.e. to calculate a suitable kind for each type constructor and class appearing in a given program.

    The first step in the kind inference process is to arrange the set of datatype, synonym, and class definitions into dependency groups. This can be achieved in much the same way as the dependency analysis for value declarations that was described in Section 4.5. For example, the following program fragment includes the definition of a datatype constructor D, a synonym S and a class C, all of which would be included in the same dependency group:

    data C a => D a = Foo (S a)
    type S a = [D a]
    class C a where
        bar :: a -> D a -> Bool

    The kinds of variables, constructors, and classes within each group are determined using standard techniques of type inference and kind-preserving unification [6]. For example, in the definitions above, the parameter a appears as an argument of the function constructor (->) in the type of bar and hence must have kind *. It follows that both D and S must have kind *->* and that every instance of class C must have kind *.

    It is possible that some parts of an inferred kind may not be fully determined by the corresponding definitions; in such cases, a default of * is assumed. For example, we could assume an arbitrary kind k for the a parameter in each of the following examples:

    data App f a = A (f a)
    data Tree a  = Leaf | Fork (Tree a) (Tree a)

    This would give kinds (k->*)->k->* and k->* for App and Tree, respectively, for any kind k, and would require an extension to allow polymorphic kinds. Instead, using the default binding k=*, the actual kinds for these two constructors are (*->*)->*->* and *->*, respectively.

    Defaults are applied to each dependency group without consideration of the ways in which particular type constructor constants or classes are used in later dependency groups or elsewhere in the program. For example, adding the following definition to those above do not influence the kind inferred for Tree (by changing it to (*->*)->*, for instance), and instead generates a static error because the kind of [], *->*, does not match the kind * that is expected for an argument of Tree:

    type FunnyTree = Tree []     -- invalid

    This is important because it ensures that each constructor and class are used consistently with the same kind whenever they are in scope.

    The Haskell 1.4 Report
    top | back | next | contents | function index
    March 27, 1997

    usr/doc/hugs/docs/report/modules.html100644 0 0 75461 6460162135 16322 0ustar rootroot The Haskell 1.4 Report: Modules The Haskell 1.4 Report
    top | back | next | contents | function index

    5  Modules

    A module defines a collection of values, datatypes, type synonyms, classes, etc. (see Section 4) in an environment created by a set of imports, resources brought into scope from other modules, and exports some of these resources, making them available to other modules. We use the term entity to refer to a value, type, or classes defined in, imported into, or perhaps exported from a module.

    A Haskell program is a collection of modules, one of which, by convention, must be called Main and must export the value main. The value of the program is the value of the identifier main in module Main, and main must have type IO () (see Section 7).

    Modules may reference other modules via explicit import declarations, each giving the name of a module to be imported and specifying its entities to be imported. Modules may be mutually recursive.

    The name-space for modules is flat, with each module being associated with a unique module name (which are Haskell identifiers beginning with a capital letter; i.e. modid). There is one distinguished module, Prelude, which is imported into all programs by default (see Section 5.3), plus a set of standard library modules that may be imported as required (see the Haskell Library Report[8]).

    5.1  Module Structure

    A module defines a mutually recursive scope containing declarations for value bindings, data types, type synonyms, classes, etc. (see Section 4).

    module -> module modid [exports] where body
    | body
    body -> { [impdecls ;] [[fixdecls ;] topdecls [;]] }
    | { impdecls [;] }
    modid -> conid
    impdecls -> impdecl1 ; ... ; impdecln   (n>=1)
    topdecls -> topdecl1 ; ... ; topdecln   (n>=0)

    A module begins with a header: the keyword module, the module name, and a list of entities (enclosed in round parentheses) to be exported. The header is followed by an optional list of import declarations that specify modules to be imported, optionally restricting the imported bindings. This is followed by an optional list of fixity declarations and the module body. The module body is simply a list of top-level declarations (topdecls), as described in Section 4.

    An abbreviated form of module, consisting only of the module body, is permitted. If this is used, the header is assumed to be `module Main(main) where'. If the first lexeme in the abbreviated module is not a {, then the layout rule applies for the top level of the module.

    5.1.1  Export Lists

    exports -> ( export1 , ... , exportn [ , ] )   (n>=0)
    export -> qvar
    | qtycon [(..) | ( qcname1 , ... , qcnamen )]   (n>=0)
    | qtycls [(..) | ( qvar1 , ... , qvarn )]   (n>=0)
    | module modid
    qcname -> qvar | qcon

    An export list identifies the entities to be exported by a module declaration. A module implementation may only export an entity that it declares, or that it imports from some other module. If the export list is omitted, all values, types and classes defined in the module are exported, but not those that are imported.

    Entities in an export list may be named as follows:

    1. A value, field name, or class method, whether declared in the module body or imported, may be named by giving the name of the value as a qvarid. Operators should be enclosed in parentheses to turn them into qvarid's.
    2. An algebraic datatype T declared by a data or newtype declaration may be named in one of three ways:
      • The form T names the type but not the constructors or field names. The ability to export a type without its constructors allows the construction of abstract datatypes (see Section 5.5).
      • The form T(qcname1,...,qcnamen), where the qcnamei name only constructors and field names in T, names the type and some or all of its constructors and field names. The qcnamei must not contain duplications.
      • The abbreviated form T(..) names the type and all its constructors and field names that are currently in scope (whether qualified or not).
      Data constructors cannot be named in export lists in any other way.
    3. A type synonym T declared by a type declaration may be named by the form T.
    4. A class C with operations f1,...,fn declared in a class declaration may be named in one of three ways:
      • The form C names the class but not the class methods.
      • The form C(f1,...,fn), where the fi must be class methods C, names the class and some or all of its methods. The fi must not contain duplications.
      • The abbreviated form C(..) names the class and all its methods that are in scope (whether qualified or not).
    5. The set of all entities brought into scope from a module m by one or more unqualified import declarations may be named by the form `module m', which is equivalent to listing all of the entities lowed by e type variables. It follows from Rule 1 that if all top-level declaration groups are unrestricted, then Rule 2 is automatically satisfied.

      Rule 1 is required for two reasons, both of which are fairly subtle. First, it prevents computations from being unexpectedly repeated. For example, genericLength is a standard function (in library List) whose type is given by

      genericLength :: Num a => [b] -> a

      Now consider the following expression:

      let { len = genericLength xs } in (len, len)

      It looks as if len should be computed only once, but without Rule 1 it might be computed twice, once at each of two different overloadings. If the programmer does actually wish the computation to be repeated, an explicit type signature may be added:

      let { len :: Num a => a; len = genericLength xs } in (len, len)

      When non-simple pattern bindings are used, the types inferred are always monomorphic in their constrained type variables, irrespective of whether a type signature is provided. For example, in

      (f,g) = ((+),(-))

      both f and g are monomorphic regardless of any type signatures supplied for f or g.

      Rule 1 also prevents ambiguity. For example, consider the declaration group

      [(n,s)] = reads t

      Recall that reads is a standard function whose type is given by the signature

      reads :: (Read a) => String -> [(a,String)]

      Without Rule 1, n would be assigned the type forall a. Read a =>a and s the type forall a. Read a =>String. The latter is an invalid type, because it is inherently ambiguous. It is not possible to determine at what overloading to use s. Rule 1 makes n and s monomorphic in a.

      Lastly, Rule 2 is required because there is no way to enforce monomorphic use of an exported binding, except by performing type inference on modules outside the current module. Exported variables are handled in the same way as non-exported ones even though their usage outside the module could theoreticly be used to determine monomorphic type. For example, in the program

      module M(x) where
      x = 1

      the monomorphism restriction prevents the type of x from being generalized to Num a => a. Since references to x outside module M cannot be used to determine the type of x, the defaulting rule (see Section 4.3.4) assigns the type Int to x.

      The monomorphism rule has a number of consequences for the programmer. Anything defined with function syntax usually generalizes as a function is expected to. Thus in

      f x y = x+y

      the function f may be used at any overloading in class Num. There is no danger of recomputation here. However, the same function defined with pattern syntax:

      f = \x -> \y -> x+y

      requires a type signature if f is to be fully overloaded. Many functions are most naturally defined using simple pattern bindings; the user must be careful to affix these with type signatures to retain full overloading. The standard prelude contains many examples of this:

      sum            :: (Num a) => [a] -> a
      sum            =  foldl (+) 0  

      4.6  Kind Inference

      This section describes the rules that are used to perform kind inference, i.e. to calculate a suitable kind for each type constructor and class appearing in a given program.

      The first step in the kind inference process is to arrange the set of datatype, synonym, and class definitions into dependency groups. This can be achieved in much the same way as the dependency analysis for value declarations that was described in Section 4.5. For example, the following program fragment includes the definition of a datatype constructor D, a synonym S and a class C, all of which would be included in the same dependency group:

      data C a => D a = Foo (S a)
      type S a = [D a]
      class C a where
          bar :: a -> D a -> Bool

      The kinds of variables, constructors, and classes within each group are determined using standard techniques of type inference and kind-preserving unification [6]. For example, in the definitions above, the parameter a appears as an argument of the function constructor (->) in the type of bar and hence must have kind *. It follows that both D and S must have kind *->* and that every instance of class C must have kind *.

      It is possible that some parts of an inferred kind may not be fully determined by the corresponding definitions; in such cases, a default of * is assumed. For example, we could assume an arbitrary kind k for the a parameter in each of the following examples:

      data App f a = A (f a)
      data Tree a  = Leaf | Fork (Tree a) (Tree a)

      This would give kinds (k->*)->k->* and k->* for App and Tree, respectively, for any kind k, and would require an extension to allow polymorphic kinds. Instead, using the default binding k=*, the actual kinds for these two constructors are (*->*)->*->* and *->*, respectively.

      Defaults are applied to each dependency group without consideration of the ways in which particular type constructor constants or classes are used in later dependency groups or elsewhere in the program. For example, adding the following definition to those above do not influence the kind inferred for Tree (by changing it to (*->*)->*, for instance), and instead generates a static error because the kind of [], *->*, does not match the kind * that is expected for an argument of Tree:

      type FunnyTree = Tree []     -- invalid