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