End Sept
[haskell-report.git] / report / Prelude.hs
1 module Prelude (
2 module PreludeList, module PreludeText, module PreludeIO,
3 Bool(False, True),
4 Maybe(Nothing, Just),
5 Either(Left, Right),
6 Ordering(LT, EQ, GT),
7 Char, String, Int, Integer, Float, Double, Rational, IO,
8
9 -- These built-in types are defined in the Prelude, but
10 -- are denoted by built-in syntax, and cannot legally
11 -- appear in an export list.
12 -- List type: []((:), [])
13 -- Tuple types: (,), (,,), etc.
14 -- Trivial type: ()
15 -- Functions: (->)
16
17 Eq((==), (/=)),
18 Ord(compare, (<), (<=), (>=), (>), max, min),
19 Enum(succ, pred, toEnum, fromEnum, enumFrom, enumFromThen,
20 enumFromTo, enumFromThenTo),
21 Bounded(minBound, maxBound),
22 Num((+), (-), (*), negate, abs, signum, fromInteger),
23 Real(toRational),
24 Integral(quot, rem, div, mod, quotRem, divMod, toInteger),
25 Fractional((/), recip, fromRational),
26 Floating(pi, exp, log, sqrt, (**), logBase, sin, cos, tan,
27 asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh),
28 RealFrac(properFraction, truncate, round, ceiling, floor),
29 RealFloat(floatRadix, floatDigits, floatRange, decodeFloat,
30 encodeFloat, exponent, significand, scaleFloat, isNaN,
31 isInfinite, isDenormalized, isIEEE, isNegativeZero, atan2),
32 Monad((>>=), (>>), return, fail),
33 Functor(fmap),
34 mapM, mapM_, sequence, sequence_, (=<<),
35 maybe, either,
36 (&&), (||), not, otherwise,
37 subtract, even, odd, gcd, lcm, (^), (^^),
38 fromIntegral, realToFrac,
39 fst, snd, curry, uncurry, id, const, (.), flip, ($), until,
40 asTypeOf, error, undefined,
41 seq, ($!)
42 ) where
43
44 import PreludeBuiltin -- Contains all `prim' values
45 import PreludeList
46 import PreludeText
47 import PreludeIO
48 import Ratio( Rational )
49
50 infixr 9 .
51 infixr 8 ^, ^^, **
52 infixl 7 *, /, `quot`, `rem`, `div`, `mod`
53 infixl 6 +, -
54
55 -- The (:) operator is built-in syntax, and cannot legally be given
56 -- a fixtity declaration; but its fixity is given by:
57 -- infixr 5 :
58
59 infix 4 ==, /=, <, <=, >=, >
60 infixr 3 &&
61 infixr 2 ||
62 infixl 1 >>, >>=
63 infixr 1 =<<
64 infixr 0 $, $!, `seq`
65
66 -- Standard types, classes, instances and related functions
67
68 -- Equality and Ordered classes
69
70 class Eq a where
71 (==), (/=) :: a -> a -> Bool
72
73 -- Minimal complete definition:
74 -- (==) or (/=)
75 x /= y = not (x == y)
76 x == y = not (x /= y)
77
78 class (Eq a) => Ord a where
79 compare :: a -> a -> Ordering
80 (<), (<=), (>=), (>) :: a -> a -> Bool
81 max, min :: a -> a -> a
82
83 -- Minimal complete definition:
84 -- (<=) or compare
85 -- Using compare can be more efficient for complex types.
86 compare x y
87 | x == y = EQ
88 | x <= y = LT
89 | otherwise = GT
90
91 x <= y = compare x y /= GT
92 x < y = compare x y == LT
93 x >= y = compare x y /= LT
94 x > y = compare x y == GT
95
96 -- note that (min x y, max x y) = (x,y) or (y,x)
97 max x y
98 | x <= y = y
99 | otherwise = x
100 min x y
101 | x <= y = x
102 | otherwise = y
103
104 -- Enumeration and Bounded classes
105
106 class Enum a where
107 succ, pred :: a -> a
108 toEnum :: Int -> a
109 fromEnum :: a -> Int
110 enumFrom :: a -> [a] -- [n..]
111 enumFromThen :: a -> a -> [a] -- [n,n'..]
112 enumFromTo :: a -> a -> [a] -- [n..m]
113 enumFromThenTo :: a -> a -> a -> [a] -- [n,n'..m]
114
115 -- Minimal complete definition:
116 -- toEnum, fromEnum
117 succ = toEnum . (+1) . fromEnum
118 pred = toEnum . (subtract 1) . fromEnum
119 enumFrom x = map toEnum [fromEnum x ..]
120 enumFromTo x y = map toEnum [fromEnum x .. fromEnum y]
121 enumFromThen x y = map toEnum [fromEnum x, fromEnum y, ..]
122 enumFromThenTo x y z =
123 map toEnum [fromEnum x, fromEnum y .. fromEnum z]
124
125 class Bounded a where
126 minBound :: a
127 maxBound :: a
128
129 -- Numeric classes
130
131 class (Eq a, Show a) => Num a where
132 (+), (-), (*) :: a -> a -> a
133 negate :: a -> a
134 abs, signum :: a -> a
135 fromInteger :: Integer -> a
136
137 -- Minimal complete definition:
138 -- All, except negate or (-)
139 x - y = x + negate y
140 negate x = 0 - x
141
142 class (Num a, Ord a) => Real a where
143 toRational :: a -> Rational
144
145 class (Real a, Enum a) => Integral a where
146 quot, rem :: a -> a -> a
147 div, mod :: a -> a -> a
148 quotRem, divMod :: a -> a -> (a,a)
149 toInteger :: a -> Integer
150
151 -- Minimal complete definition:
152 -- quotRem, toInteger
153 n `quot` d = q where (q,r) = quotRem n d
154 n `rem` d = r where (q,r) = quotRem n d
155 n `div` d = q where (q,r) = divMod n d
156 n `mod` d = r where (q,r) = divMod n d
157 divMod n d = if signum r == - signum d then (q-1, r+d) else qr
158 where qr@(q,r) = quotRem n d
159
160 class (Num a) => Fractional a where
161 (/) :: a -> a -> a
162 recip :: a -> a
163 fromRational :: Rational -> a
164
165 -- Minimal complete definition:
166 -- fromRational and (recip or (/))
167 recip x = 1 / x
168 x / y = x * recip y
169
170 class (Fractional a) => Floating a where
171 pi :: a
172 exp, log, sqrt :: a -> a
173 (**), logBase :: a -> a -> a
174 sin, cos, tan :: a -> a
175 asin, acos, atan :: a -> a
176 sinh, cosh, tanh :: a -> a
177 asinh, acosh, atanh :: a -> a
178
179 -- Minimal complete definition:
180 -- pi, exp, log, sin, cos, sinh, cosh
181 -- asin, acos, atan
182 -- asinh, acosh, atanh
183 x ** y = exp (log x * y)
184 logBase x y = log y / log x
185 sqrt x = x ** 0.5
186 tan x = sin x / cos x
187 tanh x = sinh x / cosh x
188
189
190 class (Real a, Fractional a) => RealFrac a where
191 properFraction :: (Integral b) => a -> (b,a)
192 truncate, round :: (Integral b) => a -> b
193 ceiling, floor :: (Integral b) => a -> b
194
195 -- Minimal complete definition:
196 -- properFraction
197 truncate x = m where (m,_) = properFraction x
198
199 round x = let (n,r) = properFraction x
200 m = if r < 0 then n - 1 else n + 1
201 in case signum (abs r - 0.5) of
202 -1 -> n
203 0 -> if even n then n else m
204 1 -> m
205
206 ceiling x = if r > 0 then n + 1 else n
207 where (n,r) = properFraction x
208
209 floor x = if r < 0 then n - 1 else n
210 where (n,r) = properFraction x
211
212 class (RealFrac a, Floating a) => RealFloat a where
213 floatRadix :: a -> Integer
214 floatDigits :: a -> Int
215 floatRange :: a -> (Int,Int)
216 decodeFloat :: a -> (Integer,Int)
217 encodeFloat :: Integer -> Int -> a
218 exponent :: a -> Int
219 significand :: a -> a
220 scaleFloat :: Int -> a -> a
221 isNaN, isInfinite, isDenormalized, isNegativeZero, isIEEE
222 :: a -> Bool
223 atan2 :: a -> a -> a
224
225 -- Minimal complete definition:
226 -- All except exponent, significand,
227 -- scaleFloat, atan2
228 exponent x = if m == 0 then 0 else n + floatDigits x
229 where (m,n) = decodeFloat x
230
231 significand x = encodeFloat m (- floatDigits x)
232 where (m,_) = decodeFloat x
233
234 scaleFloat k x = encodeFloat m (n+k)
235 where (m,n) = decodeFloat x
236
237 atan2 y x
238 | x>0 = atan (y/x)
239 | x==0 && y>0 = pi/2
240 | x<0 && y>0 = pi + atan (y/x)
241 |(x<=0 && y<0) ||
242 (x<0 && isNegativeZero y) ||
243 (isNegativeZero x && isNegativeZero y)
244 = -atan2 (-y) x
245 | y==0 && (x<0 || isNegativeZero x)
246 = pi -- must be after the previous test on zero y
247 | x==0 && y==0 = y -- must be after the other double zero tests
248 | otherwise = x + y -- x or y is a NaN, return a NaN (via +)
249
250 -- Numeric functions
251
252 subtract :: (Num a) => a -> a -> a
253 subtract = flip (-)
254
255 even, odd :: (Integral a) => a -> Bool
256 even n = n `rem` 2 == 0
257 odd = not . even
258
259 gcd :: (Integral a) => a -> a -> a
260 gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
261 gcd x y = gcd' (abs x) (abs y)
262 where gcd' x 0 = x
263 gcd' x y = gcd' y (x `rem` y)
264
265 lcm :: (Integral a) => a -> a -> a
266 lcm _ 0 = 0
267 lcm 0 _ = 0
268 lcm x y = abs ((x `quot` (gcd x y)) * y)
269
270 (^) :: (Num a, Integral b) => a -> b -> a
271 x ^ 0 = 1
272 x ^ n | n > 0 = f x (n-1) x
273 where f _ 0 y = y
274 f x n y = g x n where
275 g x n | even n = g (x*x) (n `quot` 2)
276 | otherwise = f x (n-1) (x*y)
277 _ ^ _ = error "Prelude.^: negative exponent"
278
279 (^^) :: (Fractional a, Integral b) => a -> b -> a
280 x ^^ n = if n >= 0 then x^n else recip (x^(-n))
281
282 fromIntegral :: (Integral a, Num b) => a -> b
283 fromIntegral = fromInteger . toInteger
284
285 realToFrac :: (Real a, Fractional b) => a -> b
286 realToFrac = fromRational . toRational
287
288 -- Monadic classes
289
290 class Functor f where
291 fmap :: (a -> b) -> f a -> f b
292
293 class Monad m where
294 (>>=) :: m a -> (a -> m b) -> m b
295 (>>) :: m a -> m b -> m b
296 return :: a -> m a
297 fail :: String -> m a
298
299 -- Minimal complete definition:
300 -- (>>=), return
301 m >> k = m >>= \_ -> k
302 fail s = error s
303
304 sequence :: Monad m => [m a] -> m [a]
305 sequence = foldr mcons (return [])
306 where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
307
308 sequence_ :: Monad m => [m a] -> m ()
309 sequence_ = foldr (>>) (return ())
310
311 -- The xxxM functions take list arguments, but lift the function or
312 -- list element to a monad type
313 mapM :: Monad m => (a -> m b) -> [a] -> m [b]
314 mapM f as = sequence (map f as)
315
316 mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
317 mapM_ f as = sequence_ (map f as)
318
319 (=<<) :: Monad m => (a -> m b) -> m a -> m b
320 f =<< x = x >>= f
321
322
323 -- Trivial type
324
325 data () = () deriving (Eq, Ord, Enum, Bounded)
326
327 -- Function type
328
329 data a -> b -- No constructor for functions is exported.
330
331 -- identity function
332 id :: a -> a
333 id x = x
334
335 -- constant function
336 const :: a -> b -> a
337 const x _ = x
338
339 -- function composition
340 (.) :: (b -> c) -> (a -> b) -> a -> c
341 f . g = \ x -> f (g x)
342
343 -- flip f takes its (first) two arguments in the reverse order of f.
344 flip :: (a -> b -> c) -> b -> a -> c
345 flip f x y = f y x
346
347 seq :: a -> b -> b
348 seq = ... -- Primitive
349
350 -- right-associating infix application operators
351 -- (useful in continuation-passing style)
352 ($), ($!) :: (a -> b) -> a -> b
353 f $ x = f x
354 f $! x = x `seq` f x
355
356
357 -- Boolean type
358
359 data Bool = False | True deriving (Eq, Ord, Enum, Read, Show, Bounded)
360
361 -- Boolean functions
362
363 (&&), (||) :: Bool -> Bool -> Bool
364 True && x = x
365 False && _ = False
366 True || _ = True
367 False || x = x
368
369 not :: Bool -> Bool
370 not True = False
371 not False = True
372
373 otherwise :: Bool
374 otherwise = True
375
376
377 -- Character type
378
379 data Char = ... 'a' | 'b' ... -- 2^16 unicode values
380
381 instance Eq Char where
382 c == c' = fromEnum c == fromEnum c'
383
384 instance Ord Char where
385 c <= c' = fromEnum c <= fromEnum c'
386
387 instance Enum Char where
388 toEnum = primIntToChar
389 fromEnum = primCharToInt
390 enumFrom c = map toEnum [fromEnum c .. fromEnum (maxBound::Char)]
391 enumFromThen c c' = map toEnum [fromEnum c, fromEnum c' .. fromEnum lastChar]
392 where lastChar :: Char
393 lastChar | c' < c = minBound
394 | otherwise = maxBound
395
396 instance Bounded Char where
397 minBound = '\0'
398 maxBound = '\xffff'
399
400 type String = [Char]
401
402
403 -- Maybe type
404
405 data Maybe a = Nothing | Just a deriving (Eq, Ord, Read, Show)
406
407 maybe :: b -> (a -> b) -> Maybe a -> b
408 maybe n f Nothing = n
409 maybe n f (Just x) = f x
410
411 instance Functor Maybe where
412 fmap f Nothing = Nothing
413 fmap f (Just x) = Just (f x)
414
415 instance Monad Maybe where
416 (Just x) >>= k = k x
417 Nothing >>= k = Nothing
418 return = Just
419 fail s = Nothing
420
421 -- Either type
422
423 data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)
424
425 either :: (a -> c) -> (b -> c) -> Either a b -> c
426 either f g (Left x) = f x
427 either f g (Right y) = g y
428
429 -- IO type
430
431 data IO a -- abstract
432
433 instance Functor IO where
434 fmap f x = x >>= (return . f)
435
436 instance Monad IO where
437 (>>=) = ...
438 return = ...
439 fail s = ioError (userError s)
440
441 -- Ordering type
442
443 data Ordering = LT | EQ | GT
444 deriving (Eq, Ord, Enum, Read, Show, Bounded)
445
446
447 -- Standard numeric types. The data declarations for these types cannot
448 -- be expressed directly in Haskell since the constructor lists would be
449 -- far too large.
450
451 data Int = minBound ... -1 | 0 | 1 ... maxBound
452 instance Eq Int where ...
453 instance Ord Int where ...
454 instance Num Int where ...
455 instance Real Int where ...
456 instance Integral Int where ...
457 instance Enum Int where ...
458 instance Bounded Int where ...
459
460 data Integer = ... -1 | 0 | 1 ...
461 instance Eq Integer where ...
462 instance Ord Integer where ...
463 instance Num Integer where ...
464 instance Real Integer where ...
465 instance Integral Integer where ...
466 instance Enum Integer where ...
467
468 data Float
469 instance Eq Float where ...
470 instance Ord Float where ...
471 instance Num Float where ...
472 instance Real Float where ...
473 instance Fractional Float where ...
474 instance Floating Float where ...
475 instance RealFrac Float where ...
476 instance RealFloat Float where ...
477
478 data Double
479 instance Eq Double where ...
480 instance Ord Double where ...
481 instance Num Double where ...
482 instance Real Double where ...
483 instance Fractional Double where ...
484 instance Floating Double where ...
485 instance RealFrac Double where ...
486 instance RealFloat Double where ...
487
488 -- The Enum instances for Floats and Doubles are slightly unusual.
489 -- The `toEnum' function truncates numbers to Int. The definitions
490 -- of enumFrom and enumFromThen allow floats to be used in arithmetic
491 -- series: [0,0.1 .. 0.95]. However, roundoff errors make these somewhat
492 -- dubious. This example may have either 10 or 11 elements, depending on
493 -- how 0.1 is represented.
494
495 instance Enum Float where
496 succ x = x+1
497 pred x = x-1
498 toEnum = fromIntegral
499 fromEnum = fromInteger . truncate -- may overflow
500 enumFrom = numericEnumFrom
501 enumFromThen = numericEnumFromThen
502 enumFromTo = numericEnumFromTo
503 enumFromThenTo = numericEnumFromThenTo
504
505 instance Enum Double where
506 succ x = x+1
507 pred x = x-1
508 toEnum = fromIntegral
509 fromEnum = fromInteger . truncate -- may overflow
510 enumFrom = numericEnumFrom
511 enumFromThen = numericEnumFromThen
512 enumFromTo = numericEnumFromTo
513 enumFromThenTo = numericEnumFromThenTo
514
515 numericEnumFrom :: (Fractional a) => a -> [a]
516 numericEnumFromThen :: (Fractional a) => a -> a -> [a]
517 numericEnumFromTo :: (Fractional a, Ord a) => a -> a -> [a]
518 numericEnumFromThenTo :: (Fractional a, Ord a) => a -> a -> a -> [a]
519 numericEnumFrom = iterate (+1)
520 numericEnumFromThen n m = iterate (+(m-n)) n
521 numericEnumFromTo n m = takeWhile (<= m+1/2) (numericEnumFrom n)
522 numericEnumFromThenTo n n' m = takeWhile p (numericEnumFromThen n n')
523 where
524 p | n' > n = (<= m + (n'-n)/2)
525 | otherwise = (>= m + (n'-n)/2)
526
527 -- Lists
528
529 -- This data declaration is not legal Haskell
530 -- but it indicates the idea
531 data [a] = [] | a : [a] deriving (Eq, Ord)
532
533 instance Functor [] where
534 fmap = map
535
536 instance Monad [] where
537 m >>= k = concat (map k m)
538 return x = [x]
539 fail s = []
540
541 -- Tuples
542
543 data (a,b) = (a,b) deriving (Eq, Ord, Bounded)
544 data (a,b,c) = (a,b,c) deriving (Eq, Ord, Bounded)
545
546
547 -- component projections for pairs:
548 -- (NB: not provided for triples, quadruples, etc.)
549 fst :: (a,b) -> a
550 fst (x,y) = x
551
552 snd :: (a,b) -> b
553 snd (x,y) = y
554
555 -- curry converts an uncurried function to a curried function;
556 -- uncurry converts a curried function to a function on pairs.
557 curry :: ((a, b) -> c) -> a -> b -> c
558 curry f x y = f (x, y)
559
560 uncurry :: (a -> b -> c) -> ((a, b) -> c)
561 uncurry f p = f (fst p) (snd p)
562
563 -- Misc functions
564
565 -- until p f yields the result of applying f until p holds.
566 until :: (a -> Bool) -> (a -> a) -> a -> a
567 until p f x
568 | p x = x
569 | otherwise = until p f (f x)
570
571 -- asTypeOf is a type-restricted version of const. It is usually used
572 -- as an infix operator, and its typing forces its first argument
573 -- (which is usually overloaded) to have the same type as the second.
574 asTypeOf :: a -> a -> a
575 asTypeOf = const
576
577 -- error stops execution and displays an error message
578
579 error :: String -> a
580 error = primError
581
582 -- It is expected that compilers will recognize this and insert error
583 -- messages that are more appropriate to the context in which undefined
584 -- appears.
585
586 undefined :: a
587 undefined = error "Prelude.undefined"
588