More small changes to
[haskell-report.git] / report / basic.verb
1 %
2 % $Header: /home/cvs/root/haskell-report/report/basic.verb,v 1.17 2003/01/13 13:08:54 simonpj Exp $
3 %
4 %**<title>The Haskell 98 Report: Predefined Types and Classes</title>
5 %*section 6
6 %**~header
7 \section{Predefined Types and Classes}
8 \label{basic-types-and-classes}
9 The \Haskell{} Prelude contains predefined classes, types,
10 and functions that are implicitly imported into every Haskell
11 program.  In this chapter, we describe the types and classes found in
12 the Prelude.
13 Most functions are not described in detail here as they
14 can easily be understood from their definitions as given in Chapter~\ref{stdprelude}.
15 Other predefined types such as arrays, complex numbers, and rationals
16 are defined in Part~\ref{libraries}.
17
18 \subsection{Standard Haskell Types}
19 \label{basic-types}
20 These types are defined by the \Haskell{} Prelude.  Numeric types are
21 described in Section \ref{numbers}.  When appropriate, the \Haskell{}
22 definition of the type is given.  Some definitions may not be
23 completely valid on syntactic grounds but they faithfully convey the
24 meaning of the underlying type.
25
26 \subsubsection{Booleans}
27 \label{booleans}
28 \index{boolean}
29 \bprog
30 @
31 data  Bool  =  False | True deriving 
32                              (Read, Show, Eq, Ord, Enum, Bounded)
33 @
34 \eprog
35 The boolean type @Bool@ is an enumeration. % ; Figure~\ref{prelude-bool}
36 The basic boolean functions are @&&@ (and), @||@ (or), and @not@.
37 The name @otherwise@ is defined as @True@ to make guarded expressions
38 more readable.
39
40 \label{prelude-bool}
41 \indextycon{Bool}
42 \indextt{False}\indextt{True}
43 \index{""|""|@@{\tt  {\char'174}{\char'174}}}
44 \index{&&@@{\tt  \&\&}}
45 \indextt{not}
46 \indextt{otherwise}
47
48 \subsubsection{Characters and Strings}
49 \label{characters}
50 \index{character}\index{string}
51
52 The character type @Char@\indextycon{Char}
53 is an enumeration whose values represent Unicode characters~\cite{unicode}.
54 % and consists of 16 bit values, conforming to
55 % the Unicode standard~\cite{unicode}.
56 % of which the first 128
57 % are the ASCII\index{ASCII character set} character set.  
58 The lexical syntax for
59 characters is defined in Section~\ref{lexemes-char}; character
60 literals are nullary constructors in the datatype @Char@.  Type @Char@
61 is an instance of the classes @Read@, @Show@, @Eq@, @Ord@, 
62 @Enum@, and @Bounded@.  The @toEnum@ and @fromEnum@ functions,
63 standard functions from class @Enum@, map characters to and from the
64 @Int@ type.
65 % @Int@ values in the range "[ 0 , 2^{16}-1 ]".
66
67 Note that ASCII control characters each have several representations
68 in character literals: numeric escapes, ASCII mnemonic escapes,
69 and the @\^@"X" notation.
70 In addition, there are the following equivalences:
71 @\a@ and @\BEL@, @\b@ and @\BS@, @\f@ and @\FF@, @\r@ and @\CR@,
72 @\t@ and @\HT@, @\v@ and @\VT@, and @\n@ and @\LF@.
73
74 A {\em string} is a list of characters:\nopagebreak[4]
75 \bprog
76 @
77 type  String  =  [Char]
78 @
79 \eprog
80 \indexsynonym{String}
81 Strings may be abbreviated using the lexical syntax described in
82 Section~\ref{lexemes-char}.  For example, @"A string"@ abbreviates
83 \[
84 @[ 'A',' ','s','t','r', 'i','n','g']@
85 \]
86
87 \subsubsection{Lists}
88 \label{basic-lists}
89 \index{list}
90 \bprog
91 @
92 data  [a]  =  [] | a : [a]  deriving (Eq, Ord)
93 @
94 \eprog
95 Lists are an algebraic datatype of two constructors, although
96 with special syntax, as described in Section~\ref{lists}.
97 The first constructor is the null list, written `@[]@' (``nil''),
98 \index{[]@@{\tt  []} (nil)}%
99 and the second is `@:@' (``cons'').
100 \indextt{:}
101 The module @PreludeList@ (see Section~\ref{preludelist})
102 defines many standard list functions.  
103 Arithmetic sequences
104 \index{arithmetic sequence}
105 and list comprehensions,
106 \index{list comprehension}
107 two convenient
108 syntaxes for special kinds of lists, are described in
109 Sections~\ref{arithmetic-sequences} and \ref{list-comprehensions},
110 respectively.  Lists are an instance of classes @Read@, @Show@, @Eq@, @Ord@, 
111 @Monad@, @Functor@, and @MonadPlus@.
112
113 \subsubsection{Tuples}
114 \label{basic-tuples}
115 \index{tuple}
116
117 Tuples are algebraic datatypes with special syntax, as defined
118 in Section~\ref{tuples}.  Each tuple type has a single constructor.
119 All tuples are instances of @Eq@, @Ord@, @Bounded@, @Read@,
120 and @Show@ (provided, of course, that all their component types are).
121
122 There is no upper bound on the size of a tuple, but some \Haskell{}
123 implementations may restrict the size of tuples, and limit the
124 instances associated with larger tuples.  However, every Haskell
125 implementation must support tuples up to size 15, together with the instances
126 for @Eq@, @Ord@, @Bounded@, @Read@, and @Show@.  The Prelude and
127 libraries define tuple functions such as @zip@ for tuples up to a size
128 of 7.
129
130 The constructor for a tuple is written by omitting the expressions
131 surrounding the commas; thus @(x,y)@ and @(,) x y@ produce the same
132 value. The same holds for tuple type constructors; thus, @(Int,Bool,Int)@
133 and @(,,) Int Bool Int@ denote the same type.
134 \indextt{(,)}
135 \indextt{(,,)}
136
137 The following functions are defined for pairs (2-tuples):
138 @fst@, @snd@, @curry@, and @uncurry@.  Similar functions are not
139 predefined for larger tuples.
140 \indextt{fst}
141 \indextt{snd}
142 \indextt{curry}
143 \indextt{uncurry}
144 \indextt{zip}
145
146 \subsubsection{The Unit Datatype}
147 \label{basic-trivial}
148 \bprog
149 @
150 data  () = () deriving (Eq, Ord, Bounded, Enum, Read, Show)
151 @
152 \eprog
153 The unit datatype @()@ has one non-"\bot"
154 member, the nullary constructor @()@.  See also Section~\ref{unit-expression}.
155 \index{trivial type}
156
157 \subsubsection{Function Types}
158 \index{function}
159 Functions are an abstract type: no constructors directly create
160 functional values.  The following simple functions are found in the Prelude:
161 @id@, @const@, @(.)@, @flip@, @($)@, and @until@.
162 \indextt{id}
163 \indextt{const}
164 \indextt{.}
165 \indextt{flip}
166 \indextt{until}
167
168 \subsubsection{The IO and IOError Types}
169 The @IO@ type serves as a tag for operations (actions) that interact
170 with the outside world.  The @IO@ type is abstract: no constructors are
171 visible to the user.  @IO@ is an instance of the @Monad@ and @Functor@
172 classes.  Chapter~\ref{io} describes I/O operations.
173
174 @IOError@ is an abstract type representing errors raised by I/O
175 operations.  It is an instance of @Show@ and @Eq@.  Values of this type
176 are constructed by the various I/O functions and are not presented in
177 any further detail in this report.  The Prelude contains a few
178 I/O functions (defined in Section~\ref{preludeio}), and Part~\ref{libraries}
179 contains many more.
180 \indextycon{IO}
181 \indextycon{IOError}
182
183 \subsubsection{Other Types}
184 {\small
185 \bprog
186 @
187 data  Maybe a     =  Nothing | Just a  deriving (Eq, Ord, Read, Show)
188 data  Either a b  =  Left a | Right b  deriving (Eq, Ord, Read, Show)
189 data  Ordering    =  LT | EQ | GT deriving
190                                   (Eq, Ord, Bounded, Enum, Read, Show)
191 @
192 \indextt{Just}
193 \indextt{Nothing}
194 \indextycon{Maybe}
195 \indextt{Left}
196 \indextt{Right}
197 \indextycon{Either}
198 \indextt{LT}
199 \indextt{EQ}
200 \indextt{GT}
201 \indextycon{Ordering}
202 \indextt{maybe}
203 \indextt{either}
204 \eprog
205 }
206 The @Maybe@ type is an instance of classes @Functor@, @Monad@,
207 and @MonadPlus@.  The @Ordering@ type is used by @compare@
208 in the class @Ord@. The functions @maybe@ and @either@ are found in
209 the Prelude.
210
211 \subsection{Strict Evaluation}
212 \label{strict-eval}
213 \index{$""!@@{\tt  {\char'044}{\char'041}}}
214 \index{$@@{\tt  {\char'044}}}
215 \indextt{seq}
216 Function application in Haskell is non-strict; that is, a function
217 argument is evaluated only when required.  Sometimes it is desirable to
218 force the evaluation of a value, using the @seq@ function:
219 \bprog
220 @
221   seq :: a -> b -> b
222 @
223 \eprog
224 The function @seq@ is defined by the equations:
225 \[\ba{l}
226 "@seq@ \bot b = \bot" \\
227 "@seq@  a b =  b,  if a \ne \bot" \\
228 \ea\]
229 @seq@ is usually introduced to improve performance by
230 avoiding unneeded laziness.  Strict datatypes (see
231 \index{strictness flags}
232 Section~\ref{strictness-flags}) are defined in terms of the @$!@
233 operator. 
234 However, the provision of @seq@ has important semantic consequences, because it is available
235 {\em at every type}.
236 As a consequence, "\bot" is
237 not the same as @\x -> @ "\bot", since @seq@ can be used to distinguish them.
238 For the same reason, the existence of @seq@ weakens Haskell's parametricity properties.
239
240 The operator @$!@ is strict (call-by-value) application, and is defined
241 in terms of @seq@.  The Prelude also defines the @$@ operator to perform 
242 non-strict application.
243 \bprog
244 @
245   infixr 0 $, $!
246   ($), ($!) :: (a -> b) -> a -> b
247   f $  x   =          f x
248   f $! x   =  x `seq` f x
249 @
250 \eprog
251 The non-strict application operator @$@ may appear redundant, since 
252 ordinary application @(f x)@ means the same as @(f $ x)@.
253 However, @$@ has low, right-associative binding precedence,
254 so it sometimes allows parentheses to be omitted; for example:
255 \bprog
256 @
257   f $ g $ h x  =  f (g (h x))
258 @
259 \eprog
260 It is also useful in higher-order situations, such as @map ($ 0) xs@,
261 or @zipWith ($) fs xs@.
262
263 \subsection{Standard Haskell Classes}
264 Figure~\ref{standard-classes} shows the hierarchy of 
265 \Haskell{} classes defined in the Prelude and the Prelude types that
266 are instances of these classes.
267 \begin{figure}%
268 %*ignore
269 % \epsfbox{class-fig.eps}
270 \includegraphics{classes.eps}
271 % \struthack{11pt}
272 %*endignore
273 %**<div align=center><img src="classes.gif" alt="Diagram of standard Haskell classes"> 
274 %**<h4>Figure 5</h4> </div>
275 \ecaption{Standard Haskell Classes}
276 \label{standard-classes}
277 \end{figure}
278
279 Default class method declarations (Section~\ref{classes}) are provided
280 for many of the methods in standard classes.  A comment with each
281 @class@ declaration in Chapter~\ref{stdprelude} specifies the
282 smallest collection of method definitions that, together with the
283 default declarations, provide a reasonable definition for all the
284 class methods.  If there is no such comment, then all class methods
285 must be given to fully specify an instance.
286
287 \subsubsection{The Eq Class}
288 \indexclass{Eq}
289 \indextt{==}
290 \indextt{/=}
291 \bprog
292 @
293   class  Eq a  where
294         (==), (/=)  ::  a -> a -> Bool
295
296         x /= y  = not (x == y)
297         x == y  = not (x /= y)
298 @
299 \eprog
300 The @Eq@ class provides equality (@==@) and inequality (@/=@) methods.
301 All basic datatypes except for functions and @IO@ are instances of this class.
302 Instances of @Eq@ can be derived for any user-defined datatype whose
303 constituents are also instances of @Eq@.
304
305 This declaration gives default method declarations for both @/=@ and @==@,
306 each being defined in terms of the other.  If an instance declaration
307 for @Eq@ defines neither @==@ nor @/=@, then both will loop.
308 If one is defined, the default method for the other will make use of
309 the one that is defined.  If both are defined, neither default method is used.
310
311 \subsubsection{The Ord Class}
312 \indexclass{Ord}
313 \indextt{<}
314 \indextt{<=}
315 \indextt{>}
316 \indextt{>=}
317 \indextt{compare}
318 \indextt{max}
319 \indextt{min}
320 \bprog
321 @
322   class  (Eq a) => Ord a  where
323     compare              :: a -> a -> Ordering
324     (<), (<=), (>=), (>) :: a -> a -> Bool
325     max, min             :: a -> a -> a
326
327     compare x y | x == y    = EQ
328                 | x <= y    = LT
329                 | otherwise = GT
330
331     x <= y  = compare x y /= GT
332     x <  y  = compare x y == LT
333     x >= y  = compare x y /= LT
334     x >  y  = compare x y == GT
335
336     -- Note that (min x y, max x y) = (x,y) or (y,x)
337     max x y | x <= y    =  y
338             | otherwise =  x
339     min x y | x <= y    =  x
340             | otherwise =  y
341 @
342 \eprog
343 The @Ord@ class is used for totally ordered datatypes.  All basic
344 datatypes
345 except for functions, @IO@, and @IOError@, are instances of this class.  Instances
346 of @Ord@ 
347 can be derived for any user-defined datatype whose constituent types
348 are in @Ord@.  The declared order
349 of the constructors in the data declaration determines the ordering in
350 derived @Ord@ instances.
351 The @Ordering@ datatype
352 allows a single comparison to determine the precise ordering of two
353 objects.
354
355 The default declarations allow a user to create an @Ord@ instance 
356 either with a type-specific @compare@ function or with type-specific
357 @==@ and @<=@ functions.
358
359 \subsubsection{The Read and Show Classes}
360 \indexsynonym{ReadS}
361 \indexsynonym{ShowS}
362 \indexclass{Read}
363 \indexclass{Show}
364 \indextt{show}
365 \indextt{readsPrec}
366 \indextt{showsPrec}
367 \indextt{readList}
368 \indextt{showList}
369 \bprog
370 @
371 type  ReadS a = String -> [(a,String)]
372 type  ShowS   = String -> String
373
374 class  Read a  where
375     readsPrec :: Int -> ReadS a
376     readList  :: ReadS [a]
377     -- ... default decl for readList given in Prelude
378
379 class  Show a  where
380     showsPrec :: Int -> a -> ShowS
381     show      :: a -> String 
382     showList  :: [a] -> ShowS
383
384     showsPrec _ x s   = show x ++ s
385     show x            = showsPrec 0 x ""
386     -- ... default decl for showList given in Prelude
387 @
388 \eprog
389 The @Read@ and @Show@ classes are used to convert values to
390 or from strings. 
391 The @Int@ argument to @showsPrec@ and @readsPrec@ gives the operator
392 precedence of the enclosing context (see Section~\ref{derived-text}).
393
394 @showsPrec@ and @showList@ return a @String@-to-@String@
395 function, to allow constant-time concatenation of its results using function
396 composition.
397 A specialised variant, @show@, is also provided, which
398 uses precedence context zero, and returns an ordinary @String@.
399 The method @showList@ is provided to allow the programmer to
400 give a specialised way of showing lists of values.  This is particularly
401 useful for the @Char@ type, where values of type @String@ should be
402 shown in double quotes, rather than between square brackets.
403
404 Derived instances of @Read@ and @Show@ replicate the style in which a
405 constructor is declared: infix constructors and field names are used
406 on input and output.  Strings produced by @showsPrec@ are usually
407 readable by @readsPrec@.  
408
409 All @Prelude@ types, except function types and @IO@ types,
410 are instances of @Show@ and @Read@.
411 (If desired, a programmer can easily make functions and @IO@ types 
412 into (vacuous) instances of @Show@, by providing an instance declaration.)
413
414 \indextt{reads}
415 \indextt{shows}
416 \indextt{read}
417 For convenience, the Prelude provides the following auxiliary
418 functions: 
419 \bprog
420 @
421 reads   :: (Read a) => ReadS a
422 reads   =  readsPrec 0
423
424 shows   :: (Show a) => a -> ShowS
425 shows   =  showsPrec 0
426
427 read    :: (Read a) => String -> a
428 read s  =  case [x | (x,t) <- reads s, ("","") <- lex t] of
429               [x] -> x
430               []  -> error "PreludeText.read: no parse"
431               _   -> error "PreludeText.read: ambiguous parse"
432 @
433 \eprog
434 \indextt{shows}\indextt{reads}\indextt{show}\indextt{read}
435 @shows@ and @reads@ use a default precedence of 0.  The @read@ function reads
436 input from a string, which must be completely consumed by the input
437 process.  
438
439 \indextt{lex}
440 The function @lex :: ReadS String@, used by @read@, is also part of the Prelude.
441 It reads a single lexeme from the input, discarding initial white space, and
442 returning the characters that constitute the lexeme.  If the input string contains
443 only white space, @lex@ returns a single successful ``lexeme'' consisting of the
444 empty string.  (Thus @lex ""@ = @[("","")]@.)  If there is no legal lexeme at the
445 beginning of the input string, @lex@ fails (i.e. returns @[]@).
446
447
448 \subsubsection{The Enum Class}
449 \label{enum-class}
450 \indexclass{Enum}
451 \indextt{toEnum}
452 \indextt{fromEnum}
453 \indextt{enumFrom}
454 \indextt{enumFromThen}
455 \indextt{enumFromTo}
456 \indextt{enumFromThenTo}
457 \bprog
458 @
459 class  Enum a  where
460     succ, pred     :: a -> a
461     toEnum         :: Int -> a
462     fromEnum       :: a -> Int
463     enumFrom       :: a -> [a]            -- [n..]
464     enumFromThen   :: a -> a -> [a]       -- [n,n'..]
465     enumFromTo     :: a -> a -> [a]       -- [n..m]
466     enumFromThenTo :: a -> a -> a -> [a]  -- [n,n'..m]
467
468     -- Default declarations given in Prelude
469 @
470 \eprog
471 Class @Enum@ defines operations on sequentially ordered types.
472 The functions @succ@ and @pred@ return the successor and predecessor,
473 respectively, of a value.
474 The functions @fromEnum@ and @toEnum@ map values from a type in
475 @Enum@ to and from @Int@.  
476 The @enumFrom@... methods are used when translating arithmetic
477 sequences (Section~\ref{arithmetic-sequences}).
478
479 Instances of @Enum@ may be derived for any enumeration type (types
480 whose constructors have no fields); see Chapter~\ref{derived-appendix}.
481
482 For any type that is an instance of class @Bounded@ as well as @Enum@, the following
483 should hold:
484 \begin{itemize}
485 \item The calls @succ maxBound@ and @pred minBound@ should result in
486 a runtime error.
487
488 \item @fromEnum@ and @toEnum@ should give a runtime error if the 
489 result value is not representable in the result type.  For example,
490 @toEnum 7 :: Bool@ is an error.
491
492 \item @enumFrom@ and @enumFromThen@ should be defined with 
493 an implicit bound, thus:
494 \bprog
495 @
496   enumFrom     x   = enumFromTo     x maxBound
497   enumFromThen x y = enumFromThenTo x y bound
498     where
499       bound | fromEnum y >= fromEnum x = maxBound
500             | otherwise                = minBound
501 @
502 \eprog
503 \end{itemize}
504
505 The following @Prelude@ types are instances of @Enum@: 
506 \begin{itemize}
507 \item Enumeration types: @()@, @Bool@, and @Ordering@. The
508 semantics of these instances is given by Chapter~\ref{derived-appendix}.
509 For example, @[LT..]@ is the list @[LT,EQ,GT]@.
510
511 \item @Char@: the instance is given in Chapter~\ref{stdprelude}, based
512 on the primitive functions that convert between a @Char@ and an @Int@.
513 For example, @enumFromTo 'a' 'z'@ denotes
514 the list of lowercase letters in alphabetical order.
515
516 \item Numeric types: @Int@, @Integer@, @Float@, @Double@.  The semantics
517 of these instances is given next.
518 \end{itemize}
519 For all four numeric types, @succ@ adds 1, and @pred@ subtracts 1.
520 The conversions @fromEnum@ and @toEnum@ convert between the type and @Int@.
521 In the case of @Float@ and @Double@, the digits after the decimal point may be lost.
522 It is implementation-dependent what @fromEnum@ returns when applied to 
523 a value that is too large to fit in an @Int@.
524
525 For the types @Int@ and @Integer@, the enumeration functions 
526 have the following meaning:
527 \begin{itemize}
528 \item The sequence "@enumFrom@~e_1" is the list "@[@e_1@,@e_1+1@,@e_1+2@,@...@]@".
529
530 \item The sequence "@enumFromThen@~e_1~e_2" is the list "@[@e_1@,@e_1+i@,@e_1+2i@,@...@]@",
531 where the increment, "i", is "e_2-e_1".  The increment may be zero or negative.
532 If the increment is zero, all the list elements are the same.
533
534 \item The sequence "@enumFromTo@~e_1~e_3" is 
535 the list "@[@e_1@,@e_1+1@,@e_1+2@,@...e_3@]@".
536 The list is empty if "e_1 > e_3".
537
538 \item The sequence "@enumFromThenTo@~e_1~e_2~e_3" 
539 is the list "@[@e_1@,@e_1+i@,@e_1+2i@,@...e_3@]@",
540 where the increment, "i", is "e_2-e_1".  If the increment 
541 is positive or zero, the list terminates when the next element would
542 be greater than "e_3"; the list is empty if "e_1 > e_3".
543 If the increment is negative, the list terminates when the next element would
544 be less than "e_3"; the list is empty if "e1 < e_3".
545 \end{itemize}
546 For @Float@ and @Double@, the semantics of the @enumFrom@ family is
547 given by the rules for @Int@ above, except that the list terminates
548 when the elements become greater than "e_3+i/2" for positive increment
549 "i", or when they become less than "e_3+i/2" for negative "i".
550
551 For all four of these Prelude numeric types, all of the @enumFrom@ 
552 family of functions are strict in all their arguments.
553
554 \subsubsection{The Functor Class}
555 \indexclass{Functor}
556 \indextt{fmap}
557 \index{functor}
558
559 \bprog
560 @
561 class  Functor f  where
562     fmap    :: (a -> b) -> f a -> f b
563 @
564 \eprog
565 The @Functor@
566 class is used for types that can be mapped over.  Lists, @IO@, and
567 @Maybe@ are in this class. 
568
569 Instances of @Functor@ should satisfy the following laws:
570 \[\ba{lcl}
571 @fmap id@&=&@id@\\
572 @fmap (f . g)@&=&@fmap f . fmap g@\\
573 \ea\]
574 All instances of @Functor@ defined in the Prelude satisfy these laws.
575
576
577 \subsubsection{The Monad Class}
578 \label{monad-class}
579 \indexclass{Monad}
580 \indextt{return}
581 \indextt{fail}
582 \indextt{>>}
583 \indextt{>>=}
584 \index{monad}
585 \bprog
586 @
587 class  Monad m  where
588     (>>=)   :: m a -> (a -> m b) -> m b
589     (>>)    :: m a -> m b -> m b
590     return  :: a -> m a
591     fail    :: String -> m a
592
593     m >> k  =  m >>= \_ -> k
594     fail s  = error s
595 @
596 \eprog
597 The @Monad@ class defines the basic operations over a {\em monad}.
598 See Chapter~\ref{io} for more information about monads.
599
600 ``@do@'' expressions provide a convenient syntax for writing
601 monadic expressions (see Section~\ref{do-expressions}).
602 The @fail@ method is invoked on pattern-match failure in a @do@
603 expression.
604
605 In the Prelude, lists, 
606 @Maybe@, and @IO@ are all instances of @Monad@.
607 The @fail@ method for lists returns the empty list @[]@,
608 for @Maybe@ returns @Nothing@, and for @IO@ raises a user
609 exception in the IO monad (see Section~\ref{io-exceptions}).
610
611 Instances of @Monad@ should satisfy the following laws:
612 \[\ba{lcl}
613 @return a >>= k@&=&@k a@ \\
614 @m >>= return@&=&@m@ \\
615 @m >>= (\x -> k x >>= h)@&=&@(m >>= k) >>= h@\\
616 \ea\]
617 Instances of both @Monad@ and @Functor@ should additionally satisfy the law:
618 \[\ba{lcl}
619 @fmap f xs@&=&@xs >>= return . f@\\
620 \ea\]
621 All instances of @Monad@ defined in the Prelude satisfy these laws.
622
623 The Prelude provides the following auxiliary functions: 
624 \bprog
625 @
626 sequence  :: Monad m => [m a] -> m [a] 
627 sequence_ :: Monad m => [m a] -> m () 
628 mapM      :: Monad m => (a -> m b) -> [a] -> m [b]
629 mapM_     :: Monad m => (a -> m b) -> [a] -> m ()
630 (=<<)     :: Monad m => (a -> m b) -> m a -> m b
631 @
632 \eprog
633 \indextt{sequence}
634 \index{sequence{\char '137}@@{\tt  sequence{\char '137}}}
635 \index{mapM{\char '137}@@{\tt  mapM{\char '137}}}
636 \indextt{mapM}
637 \indextt{=<<}
638
639 \subsubsection{The Bounded Class}
640 \indexclass{Bounded}
641 \indextt{minBound}
642 \indextt{maxBound}
643 @
644 class  Bounded a  where
645     minBound, maxBound :: a
646 @
647
648 The @Bounded@ class is used to name the upper and lower limits of a
649 type.  @Ord@ is not a superclass of @Bounded@ since types that are not
650 totally ordered may also have upper and lower bounds.
651 The types @Int@, @Char@, @Bool@,
652 @()@, @Ordering@, and all tuples are instances of @Bounded@.  
653 The @Bounded@ class may be derived
654 for any enumeration type; @minBound@ is the first constructor listed
655 in the @data@ declaration and @maxBound@ is the last.  @Bounded@ may
656 also be derived for single-constructor datatypes whose constituent
657 types are in @Bounded@.
658
659 \subsection{Numbers}
660 \label{numbers}
661 \index{number}
662
663 \Haskell{} provides several kinds of numbers; the numeric
664 types and the operations upon them have been heavily influenced by
665 %Common Lisp \cite{steele:common-lisp} and Scheme \cite{RRRRS}.
666 Common Lisp and Scheme.
667 Numeric function names and operators are usually overloaded, using
668 several type classes with an inclusion relation shown in
669 Figure~\ref{standard-classes}%
670 %*ignore
671 , page~\pageref{standard-classes}%
672 %*endignore
673 .
674 The class @Num@\indexclass{Num} of numeric
675 types is a subclass of @Eq@\indexclass{Eq}, since all numbers may be
676 compared for equality; its subclass @Real@\indexclass{Real} is also a
677 subclass of @Ord@\indexclass{Ord}, since the other comparison operations
678 apply to all but complex numbers (defined in the @Complex@ library).
679 The class @Integral@\indexclass{Integral} contains integers of both 
680 limited and unlimited range; the class
681 @Fractional@\indexclass{Fractional} contains all non-integral types; and
682 the class @Floating@\indexclass{Floating} contains all floating-point
683 types, both real and complex.
684
685 The Prelude defines only the most basic numeric types: fixed sized
686 integers (@Int@), arbitrary precision integers (@Integer@), single
687 precision floating (@Float@), and double precision floating
688 (@Double@).  Other numeric types such as rationals and complex numbers
689 are defined in libraries.  In particular, the type @Rational@ is a
690 ratio of two @Integer@ values, as defined in the @Ratio@
691 library.  
692
693 The default floating point operations defined by the \Haskell{}
694 Prelude do not 
695 conform to current language independent arithmetic (LIA) standards.  These
696 standards require considerably more complexity in the numeric
697 structure and have thus been relegated to a library.  Some, but not
698 all, aspects of the IEEE floating point standard have been
699 accounted for in Prelude class @RealFloat@.
700
701 The standard numeric types are listed in Table~\ref{standard-numeric-types}.
702 The finite-precision integer type @Int@\indextycon{Int} covers at
703 least the range 
704 "[ - 2^{29}, 2^{29} - 1]\/".  As @Int@ is an instance of the @Bounded@
705 class, @maxBound@ and @minBound@ can be used to determine the exact
706 @Int@ range defined by an implementation.
707 %(Figure~\ref{basic-numeric-2}, page~\pageref{basic-numeric-2}) define the limits of
708 %@Int@\indextycon{Int} in each implementation.
709 @Float@\indextycon{Float} is implementation-defined; it is desirable that
710 this type be at least equal in range and precision to the IEEE
711 single-precision type.  Similarly, @Double@\indextycon{Double} should
712 cover IEEE double-precision.  The results of exceptional
713 conditions (such as overflow or underflow) on the fixed-precision
714 numeric types are undefined; an implementation may choose error
715 ("\bot", semantically), a truncated value, or a special value such as
716 infinity, indefinite, etc.
717
718 \begin{table}[tb]
719 \[
720 \bto{|l|l|l|}
721 \hline
722 \multicolumn{1}{|c|}{Type} & 
723         \multicolumn{1}{c|}{Class} &
724         \multicolumn{1}{c|}{Description} \\ \hline
725 @Integer@ & @Integral@ & Arbitrary-precision integers \\
726 @Int@ & @Integral@ & Fixed-precision integers \\
727 @(Integral a) => Ratio a@ & @RealFrac@ & Rational numbers \\
728 @Float@ & @RealFloat@ & Real floating-point, single precision \\
729 @Double@ & @RealFloat@ & Real floating-point, double precision \\
730 @(RealFloat a) => Complex a@ & @Floating@ & Complex floating-point \\
731 \hline
732 \eto
733 \]
734 %**<div align=center> <h4>Table 2</h4> </div>
735 \ecaption{Standard Numeric Types}
736 \label{standard-numeric-types}
737 \index{numeric type}
738 \end{table}
739
740 The standard numeric classes and other numeric functions defined in
741 the Prelude are shown
742 in Figures~\ref{basic-numeric-1}--\ref{basic-numeric-2}.
743 Figure~\ref{standard-classes} shows the class dependencies and
744 built-in types that are instances of the numeric classes.
745
746 \begin{figure}[tb]
747 \outlinec{
748 @
749 class  (Eq a, Show a) => Num a  where
750     (+), (-), (*)  :: a -> a -> a
751     negate         :: a -> a
752     abs, signum    :: a -> a
753     fromInteger    :: Integer -> a
754
755 class  (Num a, Ord a) => Real a  where
756     toRational ::  a -> Rational
757
758 class  (Real a, Enum a) => Integral a  where
759     quot, rem, div, mod :: a -> a -> a
760     quotRem, divMod     :: a -> a -> (a,a)
761     toInteger           :: a -> Integer
762
763 class  (Num a) => Fractional a  where
764     (/)          :: a -> a -> a
765     recip        :: a -> a
766     fromRational :: Rational -> a
767
768 class  (Fractional a) => Floating a  where
769     pi                  :: a
770     exp, log, sqrt      :: a -> a
771     (**), logBase       :: a -> a -> a
772     sin, cos, tan       :: a -> a
773     asin, acos, atan    :: a -> a
774     sinh, cosh, tanh    :: a -> a
775     asinh, acosh, atanh :: a -> a
776 @
777 }
778 %**<div align=center> <h4>Figure 6</h4> </div>
779 \ecaption{Standard Numeric Classes and Related Operations, Part 1}
780 \label{basic-numeric-1}
781 \indexclass{Num}
782 \indextt{+}
783 \indextt{-}
784 \indextt{*}
785 \indextt{negate}\indextt{abs}\indextt{signum}         
786 \indextt{fromInteger}
787 \indexclass{Real}\indextt{toRational}
788 \indexclass{Integral}
789 \indextt{quotRem}\indextt{divMod}\indextt{mod}\indextt{div}
790 \indextt{rem}\indextt{quot}
791 \indextt{even}\indextt{odd}
792 \indexclass{Fractional}
793 \indextt{/}
794 \indextt{recip}\indextt{fromRational}       
795 \indexclass{Floating}\indextt{pi}\indextt{exp}\indextt{log}\indextt{sqrt} 
796 \indextt{**}
797 \indextt{logBase}
798 \indextt{sin}\indextt{cos}\indextt{tan}                        
799 \indextt{asin}\indextt{acos}\indextt{atan}               
800 \indextt{sinh}\indextt{cosh}\indextt{tanh}               
801 \indextt{asinh}\indextt{acosh}\indextt{atanh}      
802 \end{figure}
803
804 \begin{figure}[tb]
805 \outlinec{
806 @
807 class  (Real a, Fractional a) => RealFrac a  where
808     properFraction   :: (Integral b) => a -> (b,a)
809     truncate, round  :: (Integral b) => a -> b
810     ceiling, floor   :: (Integral b) => a -> b
811
812 class  (RealFrac a, Floating a) => RealFloat a  where
813     floatRadix          :: a -> Integer
814     floatDigits         :: a -> Int
815     floatRange          :: a -> (Int,Int)
816     decodeFloat         :: a -> (Integer,Int)
817     encodeFloat         :: Integer -> Int -> a
818     exponent            :: a -> Int
819     significand         :: a -> a
820     scaleFloat          :: Int -> a -> a
821     isNaN, isInfinite, isDenormalized, isNegativeZero, isIEEE 
822                         :: a -> Bool
823     atan2               :: a -> a -> a
824
825 gcd, lcm :: (Integral a) => a -> a-> a
826 (^)      :: (Num a, Integral b) => a -> b -> a
827 (^^)     :: (Fractional a, Integral b) => a -> b -> a
828
829 fromIntegral :: (Integral a, Num b) => a -> b
830 realToFrac   :: (Real a, Fractional b) => a -> b
831 @
832 }
833 %**<div align=center> <h4>Figure 7</h4> </div>
834 \ecaption{Standard Numeric Classes and Related Operations, Part 2}
835 \label{basic-numeric-2}
836 \indexclass{RealFrac}\indextt{properFraction}\indextt{approxRational}
837 \indextt{truncate}\indextt{round}
838 \indextt{ceiling}\indextt{floor}    
839 \indexclass{RealFloat}
840 \indextt{floatRadix}\indextt{floatDigits}\indextt{floatRange} 
841 \indextt{decodeFloat}\indextt{encodeFloat}
842 \indextt{exponent}\indextt{significand}\indextt{scaleFloat}
843 \indextycon{Int}\indextycon{Integer}
844 \indextt{fromIntegral}
845 \indextt{gcd}\indextt{lcm} 
846 \index{^@@{\tt  {\char'136}}} % this is ^.  Must have 2 spaces after tt!
847 \index{^^@@{\tt  {\char'136}{\char'136}}} % this is ^^
848 \indexclass{RealFrac}
849 \indextycon{Float}\indextycon{Double}
850 \indextt{realToFrac}
851 \indextt{atan2}
852 \end{figure}
853
854 \subsubsection{Numeric Literals}
855 \label{numeric-literals}
856
857 The syntax of numeric literals is given in
858 Section~\ref{lexemes-numeric}.  An integer literal represents the
859 application
860 of the function @fromInteger@\indextt{fromInteger} to the appropriate
861 value of type 
862 @Integer@.  Similarly, a floating literal stands for an application of
863 @fromRational@\indextt{fromRational} to a value of type @Rational@ (that is, 
864 @Ratio Integer@).  Given the typings:
865 \bprog
866 @
867 fromInteger  :: (Num a) => Integer -> a
868 fromRational :: (Fractional a) => Rational -> a
869 @
870 \eprog\indextt{fromInteger}\indextt{fromRational}%
871 integer and floating literals have the
872 typings @(Num a) => a@ and @(Fractional a) => a@, respectively.
873 Numeric literals are defined in this indirect way so that they may be
874 interpreted as values of any appropriate numeric type.
875 See Section~\ref{default-decls} for a discussion of overloading ambiguity.
876
877 \subsubsection{Arithmetic and Number-Theoretic Operations}
878 \label{arithmetic-operators}
879 \index{arithmetic operator}
880
881 The infix class methods 
882 @(+)@,
883 \indextt{+}
884 @(*)@,
885 \indextt{*}
886 @(-)@,
887 \indextt{-}
888 and the unary function
889 @negate@\indextt{negate} (which can also be written as a prefix minus sign; see
890 section~\ref{operators}) apply to all numbers.  The class methods
891 @quot@\indextt{quot}, @rem@\indextt{rem}, @div@\indextt{div}, and
892 @mod@\indextt{mod} apply only to integral numbers, while the class method
893 @(/)@
894 \indextt{/}
895 applies only to fractional ones.  The @quot@, @rem@,
896 @div@, and @mod@ class methods satisfy these laws if @y@ is non-zero:
897 \[\ba{c}
898 @(x @\bkqB@quot@\bkqA@ y)*y + (x @\bkqB@rem@\bkqA@ y) == x@\\
899 @(x @\bkqB@div@\bkqA@  y)*y + (x @\bkqB@mod@\bkqA@ y) == x@
900 \ea\]
901 @`quot`@ is integer division truncated toward zero,
902 while the result of @`div`@ is truncated toward
903 negative infinity. 
904 %Note that @quot@ should be used rather than
905 %@div@ to give the semantics of Pascal's @div@.
906 The @quotRem@ class method takes a dividend and a divisor as arguments
907 and returns a (quotient, remainder) pair; @divMod@ is defined
908 similarly:
909 \bprog
910 @
911 quotRem x y  =  (x @\bkqB@quot@\bkqA@ y, x @\bkqB@rem@\bkqA@ y)
912 divMod  x y  =  (x @\bkqB@div@\bkqA@ y, x @\bkqB@mod@\bkqA@ y)
913 @
914 \eprog
915 Also available on integral numbers are the even and odd predicates:
916 \bprog
917 @
918 even x =  x @\bkqB@rem@\bkqA@ 2 == 0
919 odd    =  not . even
920 @
921 \eprog\indextt{even}\indextt{odd}
922 Finally, there are the greatest common divisor and least common
923 multiple functions.  @gcd@\indextt{gcd} "x" "y" is the greatest
924 (positive) integer that divides both "x" and "y"; for example @gcd (-3) 6@ = @3@, @gcd (-3) (-6)@ = @3@, 
925 @gcd 0 4@ = @4@. @gcd 0 0@ raises a runtime error.
926
927 @lcm@\indextt{lcm} "x" "y" is the smallest positive integer that both "x" and "y" divide.
928
929 \subsubsection{Exponentiation and Logarithms}
930 \index{exponentiation}\index{logarithm}
931
932 The one-argument exponential function @exp@\indextt{exp} and the
933 logarithm function @log@\indextt{log} act on floating-point numbers and
934 use base "e".  @logBase@\indextt{logBase} "a" "x" returns the
935 logarithm of "x" in base "a".  @sqrt@\indextt{sqrt} returns the
936 principal square root of a floating-point number.
937 There are three two-argument exponentiation operations:
938 @(^)@\index{^@@{\tt  {\char'136}}} raises any  % 
939 number to a nonnegative integer power,
940 @(^^)@\index{^^@@{\tt  {\char'136}{\char'136}}} raises a
941 fractional number to any integer power, and @(**)@
942 \indextt{**}
943 takes two floating-point arguments.  The value of "x"@^0@ or "x"@^^0@
944 is @1@ for any "x", including zero; @0**@"y" is undefined.
945   
946 \subsubsection{Magnitude and Sign}
947 \label{magnitude-sign}
948 \index{magnitude}\index{sign}
949
950 A number has a {\em magnitude}
951 and a {\em sign}.  The functions @abs@\indextt{abs} and
952 @signum@\indextt{signum} apply to any number and satisfy the law:
953 \bprog
954 @
955 abs x * signum x == x
956 @
957 \eprog
958 For real numbers, these functions are defined by:
959 \bprog
960 @
961 abs x    | x >= 0  = x
962          | x <  0  = -x
963
964 signum x | x >  0  = 1
965          | x == 0  = 0
966          | x <  0  = -1
967 @
968 \eprog
969
970 \subsubsection{Trigonometric Functions}
971 \index{trigonometric function}
972
973 Class @Floating@ provides the 
974 circular and hyperbolic sine\index{sine}, cosine\index{cosine},
975 and tangent\index{tangent} functions and their inverses.
976 Default implementations of @tan@, @tanh@, @logBase@, @**@, and @sqrt@ are
977 provided, but implementors are free to provide more accurate implementations.
978
979 Class @RealFloat@ provides a version of arctangent
980 taking two real floating-point arguments.
981 For real floating "x" and "y", @atan2@\indextt{atan2} "y" "x"
982 computes the angle (from the positive x-axis) of the vector from the origin
983 to the point "(x,y)".  @atan2@\indextt{atan2} "y" "x"
984 returns a value in the range @[-pi, pi]@.  It
985 follows the Common Lisp semantics for the origin when signed zeroes are
986 supported.  @atan2@ "y" @1@, with "y" in a type that is @RealFloat@, should return the
987 same value as @atan@ "y".  A default definition of @atan2@ is provided, but
988 implementors can provide a more accurate implementation. 
989
990 The precise definition of the above functions is as in Common Lisp,
991 which in turn follows Penfield's proposal for
992 APL~\cite{penfield:complex-apl}.  See these references for discussions
993 of branch cuts, discontinuities, and implementation.
994
995 \subsubsection{Coercions and Component Extraction}
996 \label{coercion}
997 \index{coercion}
998
999 The @ceiling@\indextt{ceiling}, @floor@\indextt{floor},
1000 @truncate@\indextt{truncate}, and @round@\indextt{round}
1001 functions each take a real fractional argument and return an integral
1002 result.  \mbox{@ceiling@ "x"} returns the least integer not less than "x", and
1003 \mbox{@floor@ "x"}, the greatest integer not greater than "x".  \mbox{@truncate@ "x"}
1004 yields the integer nearest "x" between "0" and "x", inclusive.
1005 \mbox{@round@ "x"} returns the nearest integer to "x", the even integer if
1006 "x" is equidistant between two integers.
1007
1008 %       Keith Wansbrough clarifies the above defn of @round@,
1009 %       which strangely rounds both 3.5 and 4.5 to 4
1010 %
1011 % This is generally considered the most accurate kind of rounding, since it 
1012 % avoids cumulative errors.  If you get lots of values on the 0.5 boundary, 
1013 % `round up' gives you an error of +0.5 for each, whereas round-to-even gives 
1014 % you a mean error of zero.
1015
1016 % IEEE floating point does this by default for its basic operations.
1017
1018 The function @properFraction@\indextt{properFraction} takes a real
1019 fractional number "x" and returns a pair "(n,f)" such that "x = n+f", and:
1020 "n" is an integral number with the same sign as "x"; and "f" is a
1021 fraction "f" with the same type and sign as "x", and with absolute
1022 value less than 1.
1023 The @ceiling@, @floor@, @truncate@, and @round@
1024 functions can be defined in terms of @properFraction@.
1025
1026 Two functions convert numbers to type @Rational@:
1027 @toRational@\indextt{toRational} returns the rational equivalent of
1028 its real argument with full precision;
1029 @approxRational@\indextt{approxRational} takes two real fractional arguments
1030 "x" and "\epsilon" and returns the simplest rational number within
1031 "\epsilon" of "x", where a rational $ p/q $ in reduced form is
1032 {\em simpler} than another $ p^{\prime} / q^{\prime} $ if 
1033 $ |p| \leq |p^{\prime}| $ and $ q \leq q^{\prime} $.
1034 Every real interval contains a unique simplest rational;
1035 in particular, note that $ 0/1 $ is the simplest rational of all.%
1036 %\cite[Section 6.5.5]{RRRRS}.
1037
1038 The class methods of class @RealFloat@\indexclass{RealFloat} allow
1039 efficient, machine-independent
1040 access to the components of a floating-point number.
1041 The functions @floatRadix@\indextt{floatRadix},
1042 @floatDigits@\indextt{floatDigits}, and
1043 @floatRange@\indextt{floatRange} give the parameters of a
1044 floating-point type:  the radix of the representation, the number of
1045 digits of this radix in the significand, and the lowest and highest
1046 values the exponent may assume, respectively.
1047 The function @decodeFloat@\indextt{decodeFloat}
1048 applied to a real floating-point number returns the significand
1049 expressed as an @Integer@ and an appropriately scaled exponent (an
1050 @Int@).  If \mbox{@decodeFloat x@} yields \mbox{@(@"m"@,@"n"@)@}, then @x@ is
1051 equal in value to "mb^n", where "b" is the floating-point radix, and
1052 furthermore, either "m" and "n" are both zero or else
1053 "b^{d-1}<=m<b^d", where "d" is the value of \mbox{@floatDigits x@}.
1054 @encodeFloat@\indextt{encodeFloat} performs the inverse of this
1055 transformation.  The functions @significand@\indextt{significand}
1056 and @exponent@\indextt{exponent} together provide the same
1057 information as @decodeFloat@,  but rather than an @Integer@,
1058 \mbox{@significand x@} yields a value of the same type as @x@, scaled to lie
1059 in the open interval "(-1,1)".  \mbox{@exponent 0@} is zero.  @scaleFloat@
1060 multiplies a floating-point number by an integer power of the radix.
1061
1062 The functions @isNaN@, @isInfinite@, @isDenormalized@,
1063 @isNegativeZero@, and @isIEEE@ all support numbers represented using
1064 the IEEE standard.  For non-IEEE floating point numbers, these may all
1065 return false.
1066
1067 Also available are the following coercion functions:
1068 \bprog
1069 @
1070 fromIntegral :: (Integral a, Num b)    => a -> b
1071 realToFrac   :: (Real a, Fractional b) => a -> b
1072 @
1073 \eprogNoSkip\indextt{fromIntegral}\indextt{realToFrac}
1074
1075
1076 %**~footer
1077
1078 % Local Variables: 
1079 % mode: latex
1080 % End: