PrelNum.lhs 13.4 KB
 simonpj committed Dec 19, 1996 1 2 3 4 5 6 % % (c) The AQUA Project, Glasgow University, 1994-1996 % \section[PrelNum]{Module @PrelNum@}  simonpj committed Dec 20, 1999 7 8 9 10 11 12 13 14 15 The class Num and the type Integer  simonpj committed Dec 19, 1996 16 \begin{code}  simonm committed Dec 02, 1998 17 {-# OPTIONS -fno-implicit-prelude #-}  sof committed Mar 20, 1997 18   simonpj committed Dec 19, 1996 19 20 module PrelNum where  simonm committed Dec 02, 1998 21 import {-# SOURCE #-} PrelErr  simonpj committed May 18, 1999 22 23 24 25 import PrelBase import PrelList import PrelEnum import PrelShow  simonpj committed Dec 19, 1996 26   simonpj committed May 18, 1999 27 28 29 infixl 7 * infixl 6 +, -  simonpj committed Dec 20, 1999 30 31 default () -- Double isn't available yet, -- and we shouldn't be using defaults anyway  simonpj committed Dec 19, 1996 32 33 34 35 \end{code} %********************************************************* %* *  simonpj committed Dec 20, 1999 36 \subsection{Standard numeric class}  simonpj committed Dec 19, 1996 37 38 39 40 %* * %********************************************************* \begin{code}  simonpj committed May 18, 1999 41 42 43 44 45 46 47 48 49 50 51 52 class (Eq a, Show a) => Num a where (+), (-), (*) :: a -> a -> a negate :: a -> a abs, signum :: a -> a fromInteger :: Integer -> a fromInt :: Int -> a -- partain: Glasgow extension x - y = x + negate y negate x = 0 - x fromInt (I# i#) = fromInteger (S# i#) -- Go via the standard class-op if the -- non-standard one ain't provided  simonpj committed Dec 20, 1999 53 \end{code}  simonpj committed May 18, 1999 54   simonpj committed Dec 20, 1999 55 A few small numeric functions  sof committed Jan 14, 1999 56   simonpj committed Dec 20, 1999 57 58 59 60 61 62 63 \begin{code} subtract :: (Num a) => a -> a -> a {-# INLINE subtract #-} subtract x y = y - x ord_0 :: Num a => a ord_0 = fromInt (ord '0')  simonpj committed Dec 19, 1996 64 65 \end{code}  simonpj committed Dec 20, 1999 66   simonpj committed Dec 19, 1996 67 68 69 70 71 72 73 %********************************************************* %* * \subsection{Instances for @Int@} %* * %********************************************************* \begin{code}  simonpj committed May 18, 1999 74 75 76 77 78 79 80 81 82 83 84 instance Num Int where (+) x y = plusInt x y (-) x y = minusInt x y negate x = negateInt x (*) x y = timesInt x y abs n = if n geInt 0 then n else (negateInt n) signum n | n ltInt 0 = negateInt 1 | n eqInt 0 = 0 | otherwise = 1  simonpj committed Dec 20, 1999 85 86 87  fromInteger n = integer2Int n fromInt n = n \end{code}  simonpj committed May 18, 1999 88 89   simonpj committed Dec 20, 1999 90 91 92 \begin{code} -- These can't go in PrelBase with the defn of Int, because -- we don't have pairs defined at that time!  simonpj committed Dec 19, 1996 93   simonpj committed Dec 20, 1999 94 95 quotRemInt :: Int -> Int -> (Int, Int) a@(I# _) quotRemInt b@(I# _) = (a quotInt b, a remInt b)  simonpj committed Dec 19, 1996 96 97  -- OK, so I made it a little stricter. Shoot me. (WDP 94/10)  simonpj committed Dec 20, 1999 98 99 divModInt :: Int -> Int -> (Int, Int) divModInt x@(I# _) y@(I# _) = (x divInt y, x modInt y)  simonpj committed Dec 19, 1996 100  -- Stricter. Sorry if you don't like it. (WDP 94/10)  simonpj committed Dec 20, 1999 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 \end{code} %********************************************************* %* * \subsection{The @Integer@ type} %* * %********************************************************* \begin{code} data Integer = S# Int# -- small integers | J# Int# ByteArray# -- large integers \end{code} Convenient boxed Integer PrimOps. \begin{code} zeroInteger :: Integer zeroInteger = S# 0#  simonpj committed Dec 19, 1996 121   simonpj committed Dec 20, 1999 122 123 124 int2Integer :: Int -> Integer {-# INLINE int2Integer #-} int2Integer (I# i) = S# i  simonm committed Dec 02, 1998 125   simonpj committed Dec 20, 1999 126 127 128 integer2Int :: Integer -> Int integer2Int (S# i) = I# i integer2Int (J# s d) = case (integer2Int# s d) of { n# -> I# n# }  simonpj committed Dec 19, 1996 129   simonpj committed Dec 20, 1999 130 131 132 133 134 135 addr2Integer :: Addr# -> Integer {-# INLINE addr2Integer #-} addr2Integer x = case addr2Integer# x of (# s, d #) -> J# s d toBig (S# i) = case int2Integer# i of { (# s, d #) -> J# s d } toBig i@(J# _ _) = i  simonpj committed Dec 19, 1996 136 137 \end{code}  simonpj committed Dec 20, 1999 138   simonpj committed Dec 19, 1996 139 140 %********************************************************* %* *  simonpj committed Dec 20, 1999 141 \subsection{Dividing @Integers@}  simonpj committed Dec 19, 1996 142 143 144 145 %* * %********************************************************* \begin{code}  simonpj committed Dec 20, 1999 146 quotRemInteger :: Integer -> Integer -> (Integer, Integer)  simonmar committed Feb 29, 2000 147 148 149 quotRemInteger a@(S# (-2147483648#)) b = quotRemInteger (toBig a) b quotRemInteger (S# i) (S# j) = case quotRemInt (I# i) (I# j) of ( I# i, I# j ) -> ( S# i, S# j )  simonpj committed Dec 20, 1999 150 151 152 153 154 155 156 quotRemInteger i1@(J# _ _) i2@(S# _) = quotRemInteger i1 (toBig i2) quotRemInteger i1@(S# _) i2@(J# _ _) = quotRemInteger (toBig i1) i2 quotRemInteger (J# s1 d1) (J# s2 d2) = case (quotRemInteger# s1 d1 s2 d2) of (# s3, d3, s4, d4 #) -> (J# s3 d3, J# s4 d4)  simonmar committed Feb 29, 2000 157 158 159 divModInteger a@(S# (-2147483648#)) b = divModInteger (toBig a) b divModInteger (S# i) (S# j) = case divModInt (I# i) (I# j) of ( I# i, I# j ) -> ( S# i, S# j)  simonpj committed Dec 20, 1999 160 161 162 163 164 165 166 167 168 169 divModInteger i1@(J# _ _) i2@(S# _) = divModInteger i1 (toBig i2) divModInteger i1@(S# _) i2@(J# _ _) = divModInteger (toBig i1) i2 divModInteger (J# s1 d1) (J# s2 d2) = case (divModInteger# s1 d1 s2 d2) of (# s3, d3, s4, d4 #) -> (J# s3 d3, J# s4 d4) remInteger :: Integer -> Integer -> Integer remInteger ia 0 = error "Prelude.Integral.rem{Integer}: divide by 0"  simonmar committed Feb 29, 2000 170 171 remInteger a@(S# (-2147483648#)) b = remInteger (toBig a) b remInteger (S# a) (S# b) = S# (remInt# a b)  simonmar committed Mar 23, 2000 172 173 {- Special case doesn't work, because a 1-element J# has the range -(2^32-1) -- 2^32-1, whereas S# has the range -2^31 -- (2^31-1)  simonpj committed Dec 20, 1999 174 175 176 177 178 remInteger ia@(S# a) (J# sb b) | sb ==# 1# = S# (remInt# a (word2Int# (integer2Word# sb b))) | sb ==# -1# = S# (remInt# a (0# -# (word2Int# (integer2Word# sb b)))) | 0# <# sb = ia | otherwise = S# (0# -# a)  simonmar committed Mar 23, 2000 179 180 -} remInteger ia@(S# _) ib@(J# _ _) = remInteger (toBig ia) ib  simonpj committed Dec 20, 1999 181 182 183 184 185 186 187 188 189 190 remInteger (J# sa a) (S# b) = case int2Integer# b of { (# sb, b #) -> case remInteger# sa a sb b of { (# sr, r #) -> S# (sr *# (word2Int# (integer2Word# sr r))) }} remInteger (J# sa a) (J# sb b) = case remInteger# sa a sb b of (# sr, r #) -> J# sr r quotInteger :: Integer -> Integer -> Integer quotInteger ia 0 = error "Prelude.Integral.quot{Integer}: divide by 0"  simonmar committed Feb 29, 2000 191 192 quotInteger a@(S# (-2147483648#)) b = quotInteger (toBig a) b quotInteger (S# a) (S# b) = S# (quotInt# a b)  simonmar committed Mar 23, 2000 193 {- Special case disabled, see remInteger above  simonpj committed Dec 20, 1999 194 195 196 197 quotInteger (S# a) (J# sb b) | sb ==# 1# = S# (quotInt# a (word2Int# (integer2Word# sb b))) | sb ==# -1# = S# (quotInt# a (0# -# (word2Int# (integer2Word# sb b)))) | otherwise = zeroInteger  simonmar committed Mar 23, 2000 198 199 -} quotInteger ia@(S# _) ib@(J# _ _) = quotInteger (toBig ia) ib  simonpj committed Dec 20, 1999 200 201 202 203 204 205 206 207 208 209 210 quotInteger (J# sa a) (S# b) = case int2Integer# b of { (# sb, b #) -> case quotInteger# sa a sb b of (# sq, q #) -> J# sq q } quotInteger (J# sa a) (J# sb b) = case quotInteger# sa a sb b of (# sg, g #) -> J# sg g \end{code} \begin{code} gcdInteger :: Integer -> Integer -> Integer  simonmar committed Feb 29, 2000 211 212 213 gcdInteger a@(S# (-2147483648#)) b = gcdInteger (toBig a) b gcdInteger a b@(S# (-2147483648#)) = gcdInteger a (toBig b) gcdInteger (S# a) (S# b) = S# (gcdInt# a b)  simonpj committed Dec 20, 1999 214 215 216 gcdInteger ia@(S# a) ib@(J# sb b) | a ==# 0# = abs ib | sb ==# 0# = abs ia  simonmar committed Jan 19, 2000 217  | otherwise = S# (gcdIntegerInt# sb b a)  simonpj committed Dec 20, 1999 218 219 220 gcdInteger ia@(J# sa a) ib@(S# b) | sa ==# 0# = abs ib | b ==# 0# = abs ia  simonmar committed Jan 19, 2000 221  | otherwise = S# (gcdIntegerInt# sa a b)  simonpj committed Dec 20, 1999 222 223 224 225 226 227 228 229 230 231 232 233 234 235 gcdInteger (J# sa a) (J# sb b) = case gcdInteger# sa a sb b of (# sg, g #) -> J# sg g lcmInteger :: Integer -> Integer -> Integer lcmInteger a 0 = zeroInteger lcmInteger 0 b = zeroInteger lcmInteger a b = (divExact aa (gcdInteger aa ab)) * ab where aa = abs a ab = abs b divExact :: Integer -> Integer -> Integer  simonmar committed Feb 29, 2000 236 237 divExact a@(S# (-2147483648#)) b = divExact (toBig a) b divExact (S# a) (S# b) = S# (quotInt# a b)  simonpj committed Dec 20, 1999 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 divExact (S# a) (J# sb b) = S# (quotInt# a (sb *# (word2Int# (integer2Word# sb b)))) divExact (J# sa a) (S# b) = case int2Integer# b of (# sb, b #) -> case divExactInteger# sa a sb b of (# sd, d #) -> J# sd d divExact (J# sa a) (J# sb b) = case divExactInteger# sa a sb b of (# sd, d #) -> J# sd d \end{code} %********************************************************* %* * \subsection{The @Integer@ instances for @Eq@, @Ord@} %* * %********************************************************* \begin{code} instance Eq Integer where (S# i) == (S# j) = i ==# j (S# i) == (J# s d) = cmpIntegerInt# s d i ==# 0# (J# s d) == (S# i) = cmpIntegerInt# s d i ==# 0# (J# s1 d1) == (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) ==# 0# (S# i) /= (S# j) = i /=# j (S# i) /= (J# s d) = cmpIntegerInt# s d i /=# 0# (J# s d) /= (S# i) = cmpIntegerInt# s d i /=# 0# (J# s1 d1) /= (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) /=# 0# ------------------------------------------------------------------------ instance Ord Integer where (S# i) <= (S# j) = i <=# j (J# s d) <= (S# i) = cmpIntegerInt# s d i <=# 0# (S# i) <= (J# s d) = cmpIntegerInt# s d i >=# 0# (J# s1 d1) <= (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) <=# 0# (S# i) > (S# j) = i ># j (J# s d) > (S# i) = cmpIntegerInt# s d i ># 0# (S# i) > (J# s d) = cmpIntegerInt# s d i <# 0# (J# s1 d1) > (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) ># 0# (S# i) < (S# j) = i <# j (J# s d) < (S# i) = cmpIntegerInt# s d i <# 0# (S# i) < (J# s d) = cmpIntegerInt# s d i ># 0# (J# s1 d1) < (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) <# 0# (S# i) >= (S# j) = i >=# j (J# s d) >= (S# i) = cmpIntegerInt# s d i >=# 0# (S# i) >= (J# s d) = cmpIntegerInt# s d i <=# 0# (J# s1 d1) >= (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) >=# 0# compare (S# i) (S# j) | i ==# j = EQ | i <=# j = LT | otherwise = GT compare (J# s d) (S# i) = case cmpIntegerInt# s d i of { res# -> if res# <# 0# then LT else if res# ># 0# then GT else EQ } compare (S# i) (J# s d) = case cmpIntegerInt# s d i of { res# -> if res# ># 0# then LT else if res# <# 0# then GT else EQ } compare (J# s1 d1) (J# s2 d2) = case cmpInteger# s1 d1 s2 d2 of { res# -> if res# <# 0# then LT else if res# ># 0# then GT else EQ } \end{code} %********************************************************* %* * \subsection{The @Integer@ instances for @Num@} %* * %*********************************************************  simonpj committed Dec 19, 1996 315   simonpj committed Dec 20, 1999 316 \begin{code}  simonm committed Feb 17, 1999 317 318 319 320 321 instance Num Integer where (+) i1@(S# i) i2@(S# j) = case addIntC# i j of { (# r, c #) -> if c ==# 0# then S# r else toBig i1 + toBig i2 }  simonpj committed Jul 06, 1999 322 323  (+) i1@(J# _ _) i2@(S# _) = i1 + toBig i2 (+) i1@(S# _) i2@(J# _ _) = toBig i1 + i2  simonm committed Feb 17, 1999 324 325 326 327 328 329 330  (+) (J# s1 d1) (J# s2 d2) = case plusInteger# s1 d1 s2 d2 of (# s, d #) -> J# s d (-) i1@(S# i) i2@(S# j) = case subIntC# i j of { (# r, c #) -> if c ==# 0# then S# r else toBig i1 - toBig i2 }  simonpj committed Jul 06, 1999 331 332  (-) i1@(J# _ _) i2@(S# _) = i1 - toBig i2 (-) i1@(S# _) i2@(J# _ _) = toBig i1 - i2  simonm committed Feb 17, 1999 333 334 335 336 337 338 339  (-) (J# s1 d1) (J# s2 d2) = case minusInteger# s1 d1 s2 d2 of (# s, d #) -> J# s d (*) i1@(S# i) i2@(S# j) = case mulIntC# i j of { (# r, c #) -> if c ==# 0# then S# r else toBig i1 * toBig i2 }  simonpj committed Jul 06, 1999 340 341  (*) i1@(J# _ _) i2@(S# _) = i1 * toBig i2 (*) i1@(S# _) i2@(J# _ _) = toBig i1 * i2  simonm committed Feb 17, 1999 342 343 344  (*) (J# s1 d1) (J# s2 d2) = case timesInteger# s1 d1 s2 d2 of (# s, d #) -> J# s d  simonpj committed Jul 06, 1999 345  negate (S# (-2147483648#)) = 2147483648  simonm committed Feb 17, 1999 346 347  negate (S# i) = S# (negateInt# i) negate (J# s d) = J# (negateInt# s) d  simonpj committed Dec 19, 1996 348 349 350  -- ORIG: abs n = if n >= 0 then n else -n  simonmar committed Dec 13, 1999 351  abs (S# (-2147483648#)) = 2147483648  simonm committed Feb 17, 1999 352  abs (S# i) = case abs (I# i) of I# j -> S# j  simonmar committed Dec 13, 1999 353  abs n@(J# s d) = if (s >=# 0#) then n else J# (negateInt# s) d  simonpj committed Dec 19, 1996 354   simonm committed Feb 17, 1999 355 356 357 358  signum (S# i) = case signum (I# i) of I# j -> S# j signum (J# s d) = let cmp = cmpIntegerInt# s d 0#  simonpj committed Dec 19, 1996 359  in  simonm committed Feb 17, 1999 360 361 362  if cmp ># 0# then S# 1# else if cmp ==# 0# then S# 0# else S# (negateInt# 1#)  simonpj committed Dec 19, 1996 363 364 365  fromInteger x = x  simonm committed Feb 17, 1999 366  fromInt (I# i) = S# i  simonpj committed Dec 20, 1999 367 \end{code}  simonpj committed Dec 19, 1996 368   simonmar committed Dec 08, 1999 369   simonpj committed Dec 20, 1999 370 371 372 373 374 %********************************************************* %* * \subsection{The @Integer@ instance for @Enum@} %* * %*********************************************************  simonmar committed Dec 08, 1999 375   simonpj committed Dec 20, 1999 376 \begin{code}  simonpj committed Dec 19, 1996 377 instance Enum Integer where  sof committed Jan 14, 1999 378 379  succ x = x + 1 pred x = x - 1  simonpj committed Dec 20, 1999 380 381  toEnum n = int2Integer n fromEnum n = integer2Int n  simonpj committed May 28, 1999 382 383 384 385 386  {-# INLINE enumFrom #-} {-# INLINE enumFromThen #-} {-# INLINE enumFromTo #-} {-# INLINE enumFromThenTo #-}  simonpj committed Jul 06, 1999 387 388  enumFrom x = build (\c _ -> enumDeltaIntegerFB c x 1) enumFromThen x y = build (\c _ -> enumDeltaIntegerFB c x (y-x))  simonpj committed May 28, 1999 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427  enumFromTo x lim = build (\c n -> enumDeltaToIntegerFB c n x 1 lim) enumFromThenTo x y lim = build (\c n -> enumDeltaToIntegerFB c n x (y-x) lim) enumDeltaIntegerFB :: (Integer -> b -> b) -> Integer -> Integer -> b enumDeltaIntegerFB c x d = x c enumDeltaIntegerFB c (x+d) d enumDeltaIntegerList :: Integer -> Integer -> [Integer] enumDeltaIntegerList x d = x : enumDeltaIntegerList (x+d) d enumDeltaToIntegerFB c n x delta lim | delta >= 0 = up_fb c n x delta lim | otherwise = dn_fb c n x delta lim enumDeltaToIntegerList x delta lim | delta >= 0 = up_list x delta lim | otherwise = dn_list x delta lim up_fb c n x delta lim = go (x::Integer) where go x | x > lim = n | otherwise = x c go (x+delta) dn_fb c n x delta lim = go (x::Integer) where go x | x < lim = n | otherwise = x c go (x+delta) up_list x delta lim = go (x::Integer) where go x | x > lim = [] | otherwise = x : go (x+delta) dn_list x delta lim = go (x::Integer) where go x | x < lim = [] | otherwise = x : go (x+delta) {-# RULES "enumDeltaInteger" enumDeltaIntegerFB (:) = enumDeltaIntegerList "enumDeltaToInteger" enumDeltaToIntegerFB (:) [] = enumDeltaToIntegerList #-}  simonmar committed Nov 22, 1999 428 \end{code}  simonpj committed May 28, 1999 429   simonpj committed Dec 20, 1999 430   simonmar committed Nov 22, 1999 431 432 %********************************************************* %* *  simonpj committed Dec 20, 1999 433 \subsection{The @Integer@ instances for @Show@}  simonmar committed Nov 22, 1999 434 435 %* * %*********************************************************  simonpj committed Dec 19, 1996 436   simonmar committed Nov 22, 1999 437 \begin{code}  simonpj committed Dec 19, 1996 438 439 440 441 instance Show Integer where showsPrec x = showSignedInteger x showList = showList__ (showsPrec 0)  simonm committed Dec 02, 1998 442 443 showSignedInteger :: Int -> Integer -> ShowS showSignedInteger p n r  sof committed Jan 14, 1999 444 445 446 447 448 449 450 451 452 453 454  | n < 0 && p > 6 = '(':jtos n (')':r) | otherwise = jtos n r jtos :: Integer -> String -> String jtos i rs | i < 0 = '-' : jtos' (-i) rs | otherwise = jtos' i rs where jtos' :: Integer -> String -> String jtos' n cs | n < 10 = chr (fromInteger n + (ord_0::Int)) : cs  simonpj committed Dec 20, 1999 455  | otherwise = jtos' q (chr (integer2Int r + (ord_0::Int)) : cs)  sof committed Jan 14, 1999 456  where  simonpj committed Dec 20, 1999 457  (q,r) = n quotRemInteger 10  simonmar committed Dec 08, 1999 458 \end{code}