use hierarchical module names
[haskell-report.git] / report / modules.verb
1 %
2 % $Header: /home/cvs/root/haskell-report/report/modules.verb,v 1.20 2003/01/13 13:08:56 simonpj Exp $
3 %
4 %**<title>The Haskell 98 Report: Modules</title>
5 %*section 5
6 %**~header
7 \section{Modules} 
8 \label{modules} 
9 \index{module}
10
11 A module defines a collection of values, datatypes, type synonyms,
12 classes, etc.~(see Chapter~\ref{declarations}), in an environment created
13 by a set of {\em imports} (resources brought into scope from other modules).
14 It {\em exports} some of these resources, making them available to
15 other modules.  
16 We use the term {\em entity}\index{entity} to refer to
17 a value, type, or class defined in, imported into, or perhaps
18 exported from a module.
19
20 A \Haskell{} {\em program} is a collection of modules, one of
21 which, by convention, must be called @Main@\indexmodule{Main} and must
22 export the value @main@\indextt{main}.  The {\em value} of the program
23 is the value of the identifier @main@ in module @Main@,
24 which must be a computation of type $@IO@~\tau$ for some type $\tau$
25 (see Chapter~\ref{io}).  When the program is executed, the computation
26 @main@ is performed, and its result (of type $\tau$) is discarded.
27
28 Modules may reference other modules via explicit
29 @import@ declarations, each giving the name of a module to be
30 imported and specifying its entities to be imported.
31 Modules may be mutually recursive.
32
33 Modules are used for name-space control, and are not first class values.
34 A multi-module Haskell program can be converted into a single-module
35 program by giving each entity a unique name, changing all occurrences
36 to refer to the appropriate unique name, and then concatenating all the module
37 bodies\footnote{There are two minor exceptions to this statement.
38 First, @default@ declarations scope over a single module (Section~\ref{default-decls}).
39 Second, Rule 2 of the monomorphism restriction (Section~\ref{sect:monomorphism-restriction})
40 is affected by module boundaries.
41 }.  
42 For example, here is a three-module program:
43 \bprog
44 @
45   module Main where
46     import A
47     import B
48     main = A.f >> B.f
49
50   module A where
51     f = ...
52
53   module B where
54     f = ...
55 @
56 \eprog
57 It is equivalent to the following single-module program:
58 \bprog
59 @
60   module Main where
61     main = af >> bf
62
63     af = ...
64
65     bf = ...
66 @
67 \eprog
68 Because they are allowed to be mutually recursive,
69 modules allow a program to be partitioned freely without regard to
70 dependencies.
71
72 \begin{haskellprime}
73 A module name (lexeme "modid") is a sequence of one or more
74 identifiers beginning with capital letters, separated by dots, with no
75 intervening spaces.  For example, @Data.Bool@, @Main@ and
76 @Foreign.Marshal.Alloc@ are all valid module names.
77
78 @@@
79 modid   ->  \hprime{\{conid @.@\}} conid        & (\tr{modules})
80 @@@
81 \indexsyn{modid}%
82
83 Module names can be thought of as being arranged in a hierarchy in
84 which appending a new component creates a child of the original module
85 name.  For example, the module @Control.Monad.ST@ is a child of the
86 @Control.Monad@ sub-hierarchy.  This is purely a convention, however,
87 and not part of the language definition; in this report a "modid" is
88 treated as a single identifier occupying a flat namespace.
89 \end{haskellprime}
90
91 There is one distinguished module, @Prelude@, which is imported into
92 all modules by default (see Section~\ref{standard-prelude}), plus a
93 set of standard library modules that may be imported as required
94 (see Part~\ref{libraries}).
95
96 \subsection{Module Structure} 
97 \label{module-implementations}
98
99 A module defines a mutually
100 recursive scope containing declarations for value bindings, data
101 types, type synonyms, classes, etc. (see Chapter~\ref{declarations}).
102
103 @@@
104 module -> @module@ modid [exports] @where@ body
105        |  body
106 body   -> @{@ impdecls @;@ topdecls @}@
107         | @{@ impdecls  @}@
108         | @{@ topdecls @}@
109
110 impdecls     -> impdecl_1 @;@ ... @;@ impdecl_n         & (n>=1)
111 topdecls     -> topdecl_1 @;@ ... @;@ topdecl_n         & (n>=1)
112 @@@
113
114 \indexsyn{module}%
115 \indexsyn{body}%
116 \indexsyn{impdecls}%
117 \indexsyn{topdecls}%
118
119 A module 
120 begins with a header: the keyword
121 @module@, the module name, and a list of entities (enclosed in round
122 parentheses) to be exported.  The header is followed by a possibly-empty
123 list of @import@ declarations ("impdecls", Section~\ref{import}) that specify modules to be imported,
124 optionally restricting the imported bindings.  
125 This is followed by a possibly-empty list of top-level declarations ("topdecls", Chapter~\ref{declarations}).
126
127 An abbreviated form of module, consisting only 
128 of\index{abbreviated module}
129 the module body, is permitted.  If this is used, the header is assumed to be
130 `@module Main(main) where@'.
131 If the first lexeme in the
132 abbreviated module is not a @{@, then the layout rule applies
133 for the top level of the module.
134
135 \subsection{Export Lists}
136 \label{export}
137 \index{export list}
138
139 @@@
140 exports  -> @(@ export_1 @,@ ... @,@ export_n [ @,@ ] @)@ & (n>=0)
141
142 export   -> qvar
143          |  qtycon [@(..)@ | @(@ cname_1 @,@ ... @,@ cname_n @)@] &  (n>=0)
144          |  qtycls [@(..)@ | @(@ var_1 @,@ ... @,@ var_n @)@] &  (n>=0)
145          |  @module@ modid
146
147 cname   -> var | con
148 @@@
149 \indexsyn{exports}%
150 \indexsyn{export}%
151
152 An {\em export list} identifies the entities to be exported by a
153 module declaration.  A module implementation may only export an entity
154 that it declares, or that it imports from some other module.  If the
155 export list is omitted, all values, types and classes defined in the
156 module are exported, {\em but not those that are imported}.
157
158 Entities in an export list may be named as follows:
159 \begin{enumerate}
160 \item
161 A value, field name, or class method, whether declared in
162 the module body or imported,
163 may be named by giving the name of the value as a "qvarid", which must be in scope.
164 Operators should be enclosed in parentheses to turn them into
165 "qvarid"s.  
166
167 \item
168 An algebraic datatype "T"
169 \index{algebraic datatype}
170 declared by a @data@ or @newtype@ declaration may be named in one of
171 three ways: 
172 \begin{itemize}
173 \item
174 The form "T" names the type {\em but not the constructors or field names}.
175 The ability to export a type without its constructors allows the
176 construction of abstract datatypes (see Section~\ref{abstract-types}).
177 \item
178 The form $T@(@c_1@,@\ldots@,@c_n@)@$, 
179 names the type and some or all of its constructors and field names.  
180 % Restriction removed March 02:
181 % The subordinate names $c_i$ must not contain duplicates.  
182 \item
183 The abbreviated form "T@(..)@" names the type 
184 and all its constructors and field names that are currently in scope
185 (whether qualified or not).
186 \end{itemize}
187 In all cases, the (possibly-qualified) type constructor "T" must be in scope. 
188 The constructor and field names $c_i$ in the second form are unqualified;
189 one of these subordinate names is legal if and only if (a) it names a constructor
190 or field of "T", and (b) the constructor or field
191 is in scope in the module body {\em regardless of whether it is in scope
192 under a qualified or unqualified name}. For example, the following is 
193 legal
194 \bprog
195 @
196   module A( Mb.Maybe( Nothing, Just ) ) where
197     import qualified Data.Maybe as Mb
198 @
199 \eprog
200 Data constructors cannot be named in export lists except as subordinate names, because
201 they cannot otherwise be distinguished from type constructors.
202
203 \item
204 A type synonym "T" declared by a
205 @type@ declaration may be named by the form "T", where "T" is in scope.
206 \index{type synonym}
207
208 \item
209 \index{class declaration}
210 A class $C$ with operations $f_1,\ldots,f_n$
211 declared in a @class@ declaration may be named in one of three ways:
212 \begin{itemize}
213 \item
214 The form "C" names the class {\em but not the class methods}.
215 \item
216 The form $C@(@f_1@,@\ldots@,@f_n@)@$, names the class and some or all
217 of its methods.  
218 % Restriction removed March 02:
219 % The subordinate names $f_i$ must not contain duplicates.
220 \item
221 The abbreviated form $C@(..)@$ names the class and all its methods
222 that are in scope (whether qualified or not).
223 \end{itemize}
224 In all cases, "C" must be in scope.  In the second form,
225 one of the (unqualified) subordinate names $f_i$ is legal if and only if (a) it names a
226 class method of "C", and (b) the class method 
227 is in scope in the module body regardless of whether it is in scope
228 under a qualified or unqualified name.
229
230 \item
231 The form ``@module M@'' names the set of all entities that are in
232 scope with both an unqualified name ``@e@'' and a qualified name
233 ``@M.e@''.
234 This set may be empty.
235 For example:
236 \bprog
237 @
238   module Queue( module Stack, enqueue, dequeue ) where
239       import Stack
240       ...
241 @
242 \eprog
243 Here the module @Queue@ uses the module name @Stack@ in its export
244 list to abbreviate all the entities imported from @Stack@.  
245
246 A module can name its own local definitions in its export
247 list using its own name in the ``@module M@'' syntax, because a local
248 declaration brings into scope both a qualified and unqualified name (Section~\ref{qualifiers}). 
249 For example:
250 \bprog
251 @
252   module Mod1( module Mod1, module Mod2 ) where
253   import Mod2
254   import Mod3
255 @
256 \eprog
257 Here module @Mod1@ exports all local definitions as well as those
258 imported from @Mod2@ but not those imported from @Mod3@.
259
260 It is an error to use @module M@ in an export list unless @M@ is 
261 the module bearing the export list, or @M@ is imported by at 
262 least one import declaration (qualified or unqualified).
263 \end{enumerate}
264 Exports lists are cumulative: the set of entities exported by an export
265 list is the union of the entities exported by the individual items of the list.
266
267 It makes no difference to an importing module how an entity was 
268 exported.  For example, a field name @f@ from data type @T@ may be exported individually
269 (@f@, item (1) above); or as an explicitly-named member of its data type (@T(f)@, item (2));
270 or as an implicitly-named member (@T(..)@, item(2)); or by exporting an entire
271 module (@module M@, item (5)).  
272
273 The {\em unqualified} names of the entities exported by a module must all be distinct
274 (within their respective namespace).  For example
275 \bprog
276 @
277   module A ( C.f, C.g, g, module B ) where   -- an invalid module
278   import B(f)
279   import qualified C(f,g)
280   g = f True
281 @
282 \eprog
283 There are no name clashes within module @A@ itself, 
284 but there are name clashes in the export list between @C.g@ and @g@
285 (assuming @C.g@ and @g@ are different entities -- remember, modules
286 can import each other recursively), and between @module B@ and @C.f@
287 (assuming @B.f@ and @C.f@ are different entities).
288
289 \subsection{Import Declarations}
290 \label{import}
291 \index{import declaration}
292
293 @@@
294 impdecl   -> @import@ [@qualified@] modid [@as@ modid] [impspec]
295           |     & (empty declaration)
296 impspec   -> @(@ import_1 @,@ ... @,@ import_n [ @,@ ] @)@ & (n>=0)
297              |  @hiding@ @(@ import_1 @,@ ... @,@ import_n [ @,@ ] @)@ & (n>=0)
298
299 import    -> var
300           |  tycon [ @(..)@ | @(@ cname_1 @,@ ... @,@ cname_n @)@] &  (n>=0)
301           |  tycls [@(..)@ | @(@ var_1 @,@ ... @,@ var_n @)@] & (n>=0)
302 cname     -> var | con
303 @@@
304 %             var
305 %          |  tycon
306 %          |  tycon @(..)@
307 %          |  tycon @(@ con_1 @,@ ... @,@ con_n@)@ & (n>=1)
308 %          |  tycls @(..)@
309 %          |  tycls @(@ var_1 @,@ ... @,@ var_n@)@ & (n>=0)
310 \indexsyn{impdecl}%
311 \indexsyn{impspec}%
312 \indexsyn{import}%
313 \indexsyn{cname}%
314
315 The entities exported by a module may be brought into scope in
316 another module with
317 an @import@
318 declaration at the beginning
319 of the module.  
320 The @import@ declaration names the module to be
321 imported
322 and optionally specifies the entities to be imported.
323 A single module may be imported by more than one @import@ declaration.  
324 Imported names serve as top level declarations: they scope over
325 the entire body of the module but may  be shadowed by local
326 non-top-level bindings.  
327
328 The effect of multiple @import@ declarations is strictly
329 cumulative: an entity is in scope if it is imported by any of the @import@
330 declarations in a module.  The ordering of import declarations is irrelevant.
331
332 Lexically, the terminal symbols ``@as@'', ``@qualified@'' and
333 ``@hiding@'' are each a "varid" rather than a "reservedid".  They have
334 special significance only in the context of an @import@ declaration;
335 they may also be used as variables.
336
337 \subsubsection{What is imported}
338 \label{whatisimported}
339
340 Exactly which entities are to be imported can be specified in one
341 of the following three ways:\nopagebreak[4]
342 \begin{enumerate}
343 \item
344 The imported entities can be specified explicitly
345 by listing them in parentheses.
346 Items in the list have the same form as those in export lists, except
347 qualifiers are not permitted and
348 the `@module@ "modid"' entity is not permitted.  When the @(..)@ form
349 of import is used for a type or class, the @(..)@ refers to all of the
350 constructors, methods, or field names exported from the module.
351
352 The list must name only
353 entities exported by the imported module.
354 The list may be empty, in which case nothing except the instances is
355 imported.
356
357 \item
358 Entities can be excluded by 
359 using the form @hiding(@"import_1 @,@ ... @,@ import_n"
360 @)@,\index{hiding} which
361 specifies that all entities exported by the named module should
362 be imported except for those named in the list.  Data constructors may be
363 named directly in hiding lists without being prefixed by the
364 associated type.  Thus, in
365 \bprog
366 @
367   import M hiding (C)
368 @
369 \eprog
370 any constructor, class, or type named @C@ is excluded.  In contrast,
371 using @C@ in an import list names only a class or type.  
372
373 It is an error to hide an entity that is not, in fact, exported by
374 the imported module.
375
376 \item
377 Finally, if "impspec" is omitted then 
378 all the entities exported by the specified module are imported.
379 \end{enumerate}
380
381 \subsubsection{Qualified import}
382 \index{qualified name}
383
384 For each entity imported under the rules of Section~\ref{whatisimported},
385 the top-level environment is extended.  If the import declaration used
386 the @qualified@ keyword, only the {\em qualified name} of the entity is
387 brought into scope.  If the @qualified@ keyword is omitted, then {\em both} the
388 qualified {\em and} unqualified name of the entity is brought into scope.
389 Section~\ref{qualifiers} describes qualified names in more detail.
390
391 The qualifier on the imported name is either the name of the imported module,
392 or the local alias given in the @as@ clause (Section~\ref{as-clause}) 
393 on the @import@ statement.
394 Hence, {\em the qualifier is not necessarily the name of the module in which the
395 entity was originally declared}.
396
397 The ability to exclude the unqualified names allows full programmer control of
398 the unqualified namespace: a locally defined entity can share the same
399 name as a qualified import:
400 \par
401 {\small
402 \bprog
403 @
404   module Ring where
405   import qualified Prelude    -- All Prelude names must be qualified
406   import Data.List( nub )
407
408   l1 + l2 = l1 Prelude.++ l2  -- This + differs from the one in the Prelude
409   l1 * l2 = nub (l1 + l2)     -- This * differs from the one in the Prelude
410
411   succ = (Prelude.+ 1)
412 @
413 \eprog
414 }
415
416 \subsubsection{Local aliases}
417 \label{as-clause}
418
419 Imported modules may be assigned a local alias in the importing module
420 using the @as@ clause.
421 For example, in
422 \bprog
423 @
424   import qualified VeryLongModuleName as C
425 @
426 \eprog
427 entities must be referenced using `@C.@' as a qualifier instead of
428 `@VeryLongModuleName.@'.  This also allows a different module to be substituted
429 for @VeryLongModuleName@ without changing the qualifiers used for the imported module.
430 It is legal for more than one module in scope to 
431 use the same qualifier, provided that all names can still be resolved unambiguously.
432 For example:
433 \bprog
434 @
435   module M where
436     import qualified Foo as A
437     import qualified Baz as A
438     x = A.f
439 @
440 \eprog
441 This module is legal provided only that @Foo@ and @Baz@ do not both export @f@.
442
443 An @as@ clause may also be used on an un-@qualified@ @import@ statement:
444 \bprog
445 @
446   import Foo as A(f)
447 @
448 \eprog
449 This declaration brings into scope @f@ and @A.f@.
450
451
452 \subsubsection{Examples}
453
454 To clarify the above import rules, suppose the module @A@ exports @x@ and @y@.
455 Then this table shows what names are brought into scope by the specified import statement:
456 \begin{center}
457 \begin{tabular}{|ll|}
458 \hline
459 Import declaration & Names brought into scope \\
460 \hline
461   @import A@                    & @x@, @y@, @A.x@, @A.y@ \\
462   @import A()@                  & (nothing)     \\
463   @import A(x)@                 & @x@, @A.x@ \\
464   @import qualified A@          & @A.x@, @A.y@ \\
465   @import qualified A()@        & (nothing) \\
466   @import qualified A(x)@       & @A.x@ \\
467   @import A hiding ()@          & @x@, @y@, @A.x@, @A.y@ \\
468   @import A hiding (x)@         & @y@, @A.y@ \\
469   @import qualified A hiding ()@        & @A.x@, @A.y@ \\
470   @import qualified A hiding (x)@       & @A.y@ \\
471   @import A as B@               & @x@, @y@, @B.x@, @B.y@ \\
472   @import A as B(x)@            & @x@, @B.x@ \\
473   @import qualified A as B@     & @B.x@, @B.y@ \\
474 \hline
475 \end{tabular}
476 \end{center}
477 In all cases, all instance declarations in scope in module @A@ are imported
478 (Section~\ref{import-instances}).
479
480 \subsection{Importing and Exporting Instance Declarations}
481 \label{import-instances}
482 \index{instance declaration!importing and exporting}
483
484 Instance declarations cannot be explicitly named on import or export
485 lists.  All instances in scope within a module are {\em always}
486 exported and any import brings {\em all} instances in from the
487 imported module.  Thus, an
488 instance declaration is in scope if and only if a chain of @import@
489 declarations leads to the module containing the instance declaration.
490
491 For example, @import M()@ does not bring
492 any new names in scope from module @M@, but does bring in any instances
493 visible in @M@.  A module whose only purpose is to provide instance
494 declarations can have an empty export list.  For example
495 \bprog
496 @
497   module MyInstances() where
498     instance Show (a -> b) where
499       show fn = "<<function>>"
500     instance Show (IO a) where
501       show io = "<<IO action>>"
502 @
503 \eprog
504
505 \subsection{Name Clashes and Closure}
506
507 \subsubsection{Qualified names}\index{qualified name}
508 \label{qualifiers}
509
510 A {\em qualified name} is written as "modid"@.@"name" (Section~\ref{ids}).
511 A qualified name is brought into scope:
512 \begin{itemize}
513 \item {\em By a top level declaration.}
514 A top-level declaration brings into scope both the unqualified {\em and}
515 the qualified name of the entity being defined.  Thus:
516 \bprog
517 @
518   module M where
519     f x = ...
520     g x = M.f x x
521 @
522 \eprog
523 is legal.  The {\em defining} occurrence must mention the {\em unqualified} name; therefore, it is
524 illegal to write
525 \bprog
526 @
527   module M where
528     M.f x = ...                 -- ILLEGAL
529     g x = let M.y = x+1 in ...  -- ILLEGAL
530 @
531 \eprog
532 \item {\em By an @import@ declaration.}  An @import@ declaration, whether @qualified@ or not,
533 always brings into scope the qualified name of the imported entity (Section~\ref{import}).
534 This allows a qualified
535 import to be replaced with an unqualified one without forcing changes
536 in the references to the imported names.  
537 \end{itemize}
538
539
540 \subsubsection{Name clashes}
541
542 If a module contains a bound occurrence of a name, such as @f@ or @A.f@,
543 it must be possible unambiguously to resolve which entity is thereby referred to;
544 that is, there must be only one binding for @f@ or @A.f@ respectively.
545
546 It is {\em not} an error for there to exist names that cannot be so 
547 resolved, provided that the program does not mention those names.  For example:
548 \bprog
549 @
550   module A where
551     import B
552     import C
553     tup = (b, c, d, x)
554   
555   module B( d, b, x, y ) where
556     import D
557     x = ...
558     y = ...
559     b = ...
560   
561   module C( d, c, x, y ) where
562     import D
563     x = ...
564     y = ...
565     c = ...
566
567   module D( d ) where
568     d = ...
569 @
570 \eprog
571 Consider the definition of @tup@.  
572 \begin{itemize}
573 \item The references to @b@ and @c@
574 can be unambiguously resolved to @b@ declared in @B@, and @c@ declared in
575 @C@ respectively.  
576 \item The reference to @d@ is unambiguously resolved to
577 @d@ declared in @D@.  In this case the same entity is brought into scope by two routes
578 (the import of @B@ and the import of @C@), and can be referred to in @A@ by the names
579 @d@, @B.d@, and @C.d@.
580 \item The reference to @x@ is ambiguous: it could mean @x@ declared in @B@, or @x@ 
581 declared in @C@.  The ambiguity could be fixed by replacing the reference to @x@ by
582 @B.x@ or @C.x@.
583 \item There is no reference to @y@, so it is not erroneous that distinct entities called
584 @y@ are exported by both @B@ and @C@.  An error is only reported if @y@ is actually mentioned.
585 \end{itemize}
586
587 The name occurring in a type signature or fixity declarations is
588 always unqualified, and unambiguously refers to another declaration in
589 the same declaration list (except that the fixity declaration for a
590 class method can occur at top level --- Section~\ref{fixity}). For example,
591 the following module is legal:
592 \bprog
593 @
594   module F where
595
596     sin :: Float -> Float
597     sin x = (x::Float)
598
599     f x = Prelude.sin (F.sin x)
600 @
601 \eprog
602 The local declaration for @sin@ is
603 legal, even though the Prelude function @sin@ is implicitly in
604 scope. The references to @Prelude.sin@ and @F.sin@ must both be qualified
605 to make it unambiguous which @sin@ is meant. However, the unqualified
606 name "@sin@" in the type signature in the first line of @F@ unambiguously
607 refers to the local declaration for @sin@.
608
609 \subsubsection{Closure}
610 \label{closure}
611 \index{closure}
612
613 Every module in a \Haskell{} program must be {\em closed}.  That is,
614 every name explicitly mentioned by the source code
615 must be either defined locally or imported from another module.
616 However, entities that the compiler requires for type checking or other
617 compile time analysis need not be imported if they are not mentioned
618 by name.  The \Haskell{} compilation system is responsible for finding
619 any information needed for compilation without the help of the
620 programmer.  That is, the import of a variable @x@ does not
621 require that the datatypes and classes in the signature of @x@ be
622 brought into the module along with @x@ unless these entities are
623 referenced by name in the user program.  The \Haskell{}
624 system silently imports any information that must accompany an
625 entity for type checking or any other purposes.  Such entities need
626 not even be explicitly exported: the following program is valid even though
627 @T@ does not escape @M1@:
628 \bprog
629 @
630   module M1(x) where
631     data T = T
632     x = T
633   
634   module M2 where
635     import M1(x)
636     y = x
637 @
638 \eprog
639 In this example, there is no way to supply an explicit type signature
640 for @y@ since @T@ is not in scope.
641 Whether or not @T@ is explicitly exported, module @M2@ knows
642 enough about @T@ to correctly type check the program.
643
644 The type of an exported entity is unaffected by non-exported type
645 synonyms.  For example, in
646 \bprog
647 @
648   module M(x) where
649     type T = Int
650     x :: T
651     x = 1
652 @
653 \eprog
654 the type of @x@ is both @T@ and @Int@; these are interchangeable even
655 when @T@ is not in scope.  That is, the definition of @T@ is available
656 to any module that encounters it whether or not the name @T@ is
657 in scope.  The only reason to export @T@ is to allow other modules to
658 refer it by name; the type checker finds the definition of @T@ if
659 needed whether or not it is exported.
660
661 \subsection{Standard Prelude}
662 \label{standard-prelude}
663 \index{standard prelude}
664 \index{libraries}
665 Many of the features of \Haskell{} are defined in \Haskell{}
666 itself as a library of standard datatypes, classes, and
667 functions, called the ``Standard Prelude.''  In
668 \Haskell{}, the Prelude is contained in the
669 module @Prelude@.\indexmodule{Prelude} There are also
670 many predefined library modules, which provide less frequently used
671 functions and types.  For example, complex numbers, arrays, 
672 and most of the input/output are all part of the standard
673 libraries.    These are 
674 defined in Part~\ref{libraries}.
675 Separating
676 libraries from the Prelude has the advantage of reducing the size and
677 complexity of the Prelude, allowing it to be more easily assimilated,
678 and increasing the space of useful names available to the programmer.
679
680 Prelude and library modules differ from other modules in that
681 their semantics (but not their implementation) are a fixed part of the
682 \Haskell{} language definition.
683 This means, for example, that a compiler may optimize calls to
684 functions in the Prelude without consulting the source code
685 of the Prelude.
686
687 \subsubsection{The @Prelude@ Module}
688 \indexmodule{Prelude}
689 \index{Prelude!implicit import of}
690
691 The @Prelude@ module is imported automatically into all modules as if
692 by the statement `@import Prelude@', if and only if it is not imported
693 with an explicit @import@ declaration. This provision for explicit
694 import allows entities defined in the Prelude to be selectively imported,
695 just like those from any other module.
696
697 The semantics of the entities in @Prelude@ is specified by a reference
698 implementation of @Prelude@ written in \Haskell{}, given in
699 Chapter~\ref{stdprelude}.  Some datatypes (such as @Int@) and
700 functions (such as @Int@ addition) cannot be specified directly in
701 \Haskell{}.  Since the treatment of such entities depends on the
702 implementation, they are not formally defined in Chapter~\ref{stdprelude}.
703 The implementation of
704 @Prelude@ is also incomplete in its treatment of tuples: there should
705 be an infinite family of tuples and their instance declarations, but the
706 implementation only gives a scheme.
707
708 Chapter~\ref{stdprelude} defines the module @Prelude@ using
709 several other modules: @PreludeList@, @PreludeIO@, and so on.
710 These modules are {\em not} part of Haskell 98, and they cannot be imported
711 separately.  They are simply 
712 there to help explain the structure of the @Prelude@ module; they
713 should be considered part of its implementation, not part of the language
714 definition.
715  
716 \subsubsection{Shadowing Prelude Names}
717 \label{std-prel-shadowing}
718
719 The rules about the Prelude have been cast so that it is
720 possible to use Prelude names for nonstandard purposes; however,
721 every module that does so must have an @import@ declaration
722 that makes this nonstandard usage explicit.  For example:
723 \bprog
724 @
725   module A( null, nonNull ) where
726     import Prelude hiding( null ) 
727     null, nonNull :: Int -> Bool
728     null    x = x == 0
729     nonNull x = not (null x)
730 @
731 \eprog
732 Module @A@ redefines @null@, and contains an unqualified reference to @null@
733 on the right hand side of @nonNull@. The latter would be ambiguous
734 without the @hiding(null)@ on the @import Prelude@ statement. Every
735 module that imports @A@ unqualified, and then makes an unqualified
736 reference to @null@ must also resolve the ambiguous use of @null@ just as
737 @A@ does. Thus there is little danger of accidentally shadowing Prelude
738 names.
739
740 It is possible to construct and use a different module to serve in
741 place of the Prelude.  Other than the fact that it is implicitly
742 imported, the Prelude is an ordinary \Haskell{} module; it is special
743 only in that some objects in the Prelude are referenced by special
744 syntactic constructs.  Redefining names used by the Prelude does not
745 affect the meaning of these special constructs.  For example, in
746 \bprog
747 @
748   module B where
749     import Prelude()
750     import MyPrelude
751     f x = (x,x)
752     g x = (,) x x
753     h x = [x] ++ []
754 @
755 \eprog
756 the explicit @import Prelude()@ declaration prevents the automatic
757 import of @Prelude@, while the declaration @import MyPrelude@ brings the
758 non-standard prelude into scope.  
759 The special syntax for tuples (such as @(x,x)@ and @(,)@) and lists
760 (such as @[x]@ and @[]@) continues to refer to the tuples and lists
761 defined by the standard @Prelude@;
762 there is no way to redefine the meaning of @[x]@, for example, in terms of a
763 different implementation of lists.
764 On the other hand, the use of @++@ is not special syntax, so it refers
765 to @++@ imported from @MyPrelude@.
766
767 It is not possible, however, to hide @instance@ declarations in the
768 @Prelude@.  For example, one cannot define a new instance for @Show Char@.
769
770 \subsection{Separate Compilation}
771 \index{separate compilation}
772 Depending on the \Haskell{} implementation used, separate compilation
773 of mutually recursive modules may require that imported modules contain
774 additional information so that they may be referenced before they are
775 compiled.  Explicit type signatures for all exported values may be
776 necessary to deal with mutual recursion.  The
777 precise details of separate compilation are not defined by this
778 report. 
779
780 \subsection{Abstract Datatypes}
781 \label{abstract-types}
782
783 \index{abstract datatype}
784 The ability to export a datatype without its constructors
785 allows the construction of abstract datatypes (ADTs).  For example,
786 an ADT for stacks could be defined as:
787 \bprog
788 @
789   module Stack( StkType, push, pop, empty ) where
790     data StkType a = EmptyStk | Stk a (StkType a)
791     push x s = Stk x s
792     pop (Stk _ s) = s
793     empty = EmptyStk
794 @
795 \eprog
796 Modules importing @Stack@ cannot construct values of type @StkType@
797 because they do not have access to the constructors of the type.
798 Instead, they must use @push@, @pop@, and @empty@ to construct such values.
799
800 It is also possible to build an ADT on top of an existing type by
801 using a @newtype@ declaration.  For example, stacks can be defined
802 with lists: 
803 \bprog
804 @
805   module Stack( StkType, push, pop, empty ) where
806     newtype StkType a = Stk [a]
807     push x (Stk s) = Stk (x:s)
808     pop (Stk (_:s)) = Stk s
809     empty = Stk []
810 @
811 \eprogNoSkip
812
813
814 %**~footer
815
816 % Local Variables: 
817 % mode: latex
818 % End: