This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.

# Data.Integer

Infinite digits integers

# The datatype

type Integer = Integer (Sign, Magnitude)

Integer type

type Sign = Positive | Negative

The sign of the integer

# From/To

fromInt : Int -> Integer

Makes an Integer from an Int

fromString : String -> Maybe Integer

Makes an Integer from a String

toString : Integer -> String

Converts the Integer to a String

# Common operations

add : Integer -> Integer -> Integer

sub : Integer -> Integer -> Integer

Substracts the second Integer from the first

negate : Integer -> Integer

Changes the sign of an Integer

mul : Integer -> Integer -> Integer

Multiplies two Integers

divmod : Integer -> Integer -> Maybe (Integer, Integer)

Division and modulus

unsafeDivmod : Integer -> Integer -> (Integer, Integer)

divmod that returns the pair of values, or crashes if the divisor is zero

abs : Integer -> Integer

Absolute value

sign : Integer -> Sign

Get the sign of the integer

# Comparison

compare : Integer -> Integer -> Order

Compares two Integers

gt : Integer -> Integer -> Bool

Greater than

gte : Integer -> Integer -> Bool

Greater than or equals

lt : Integer -> Integer -> Bool

Less than

lte : Integer -> Integer -> Bool

Less than or equals

eq : Integer -> Integer -> Bool

Equals

neq : Integer -> Integer -> Bool

Not equals

max : Integer -> Integer -> Integer

Returns the largest of two Integers

min : Integer -> Integer -> Integer

Returns the smallest of two Integers

# Common numbers

zero : Integer

Number 0

one : Integer

Number 1

minusOne : Integer

Number -1

# Internals

max : Integer -> Integer -> Integer

Returns the largest of two Integers

``````module Data.Integer exposing
( Integer
, Sign(Positive, Negative)
, sign
, max_digit_value
, fromInt
, fromString
, toString
, sub
, negate
, mul
, divmod
, unsafeDivmod
, abs
, compare
, gt
, gte
, lt
, lte
, eq
, neq
, max
, min
, zero
, one
, minusOne
)

{-| Infinite digits integers
# The datatype
@docs Integer
@docs Sign

# From/To
@docs fromInt
@docs fromString
@docs toString

# Common operations
@docs sub
@docs negate
@docs mul
@docs divmod
@docs unsafeDivmod
@docs abs
@docs sign

# Comparison
@docs compare
@docs gt
@docs gte
@docs lt
@docs lte
@docs eq
@docs neq
@docs max
@docs min

# Common numbers
@docs zero
@docs one
@docs minusOne

# Internals
@docs max_digit_value

-}

import String
import Maybe exposing (Maybe)
import Result exposing (Result)
import Char
import Basics
import Debug

{-| The sign of the integer -}
type Sign
= Positive
| Negative

type alias Digit = Int

{- From smallest to largest digit, all the digits are positive, no leading zeros -}
type Magnitude = Magnitude (List Digit)

type MagnitudeNotNormalised = MagnitudeNotNormalised (List Digit)

{-| Integer type -}
type Integer = Integer (Sign, Magnitude)

type IntegerNotNormalised = IntegerNotNormalised (Sign, MagnitudeNotNormalised)

{-| Enough to hold digit * digit without overflowing to double -}
max_digit_value : Int
max_digit_value = 1000000

{-| Makes an Integer from an Int -}
fromInt : Int -> Integer
fromInt x =
let sign = if x < 0 then Negative else Positive in
normalise <| IntegerNotNormalised (sign, MagnitudeNotNormalised [Basics.abs x])

{-| Makes an Integer from a String -}
fromString : String -> Maybe Integer
fromString x =
case String.toList x of
[] -> Just (fromInt 0)
'-'::xs ->
case fromString' xs of
Nothing -> Nothing
(Just a) -> Just (Integer (Negative, a))
'+'::xs ->
case fromString' xs of
Nothing -> Nothing
(Just a) -> Just (Integer (Positive, a))
xs ->
case fromString' xs of
Nothing -> Nothing
(Just a) -> Just (Integer (Positive, a))

fromString' : List Char -> Maybe Magnitude
fromString' x =
if not <| List.all Char.isDigit x
then Nothing
else
let rev_digits = List.reverse x
rev_group_digits = groups 6 rev_digits
group_digits = List.map List.reverse rev_group_digits
group_strings = List.map String.fromList group_digits
group_result_ints = List.map String.toInt group_strings
in
let result_to_maybe x =
case x of
Ok a -> Just a
Err _ -> Nothing
in
let group_maybe_ints = List.map result_to_maybe group_result_ints in
let gen_res x =
case x of
[] -> Just []
Nothing :: xs -> Nothing
(Just b) :: bx ->
case gen_res bx of
Nothing -> Nothing
Just xxs -> Just (b::xxs)
in
case gen_res group_maybe_ints of
Just x -> Just (Magnitude x)
Nothing -> Nothing

groups : Int -> List a -> List (List a)
groups n x =
let head = List.take n x
tail = List.drop n x in
if tail == []
else head :: groups n tail

type MagnitudePair = MagnitudePair (List (Digit, Digit))

sameSize : Magnitude -> Magnitude -> MagnitudePair
sameSize (Magnitude a) (Magnitude b) =
let sameSize' a b =
case (a, b) of
([], []) -> []
(a::xa, b::xb) ->
(a, b) :: sameSize' xa xb
(a::xa, []) ->
(a, 0) :: sameSize' xa []
([], b::xb) ->
(0, b) :: sameSize' [] xb
in
MagnitudePair (sameSize' a b)

sameSize' : MagnitudeNotNormalised -> MagnitudeNotNormalised -> MagnitudePair
sameSize' (MagnitudeNotNormalised a) (MagnitudeNotNormalised b) =
let sameSize'' a b =
case (a, b) of
([], []) -> []
(a::xa, b::xb) ->
(a, b) :: sameSize'' xa xb
(a::xa, []) ->
(a, 0) :: sameSize'' xa []
([], b::xb) ->
(0, b) :: sameSize'' [] xb
in
MagnitudePair (sameSize'' a b)

normalise : IntegerNotNormalised -> Integer
normalise (IntegerNotNormalised (sx, x)) =
let nmagnitude = normaliseMagnitude x in
let is_negative_magnitude (Magnitude x) =
case x of
[] -> False
[d] -> d < 0
x::xs -> is_negative_magnitude (Magnitude xs)
in
let reverse_magnitude (Magnitude xs) =
MagnitudeNotNormalised (List.map (\x -> 0-x) xs)
in
let reverse_sign s =
case s of
Positive -> Negative
Negative -> Positive
in
if is_negative_magnitude nmagnitude
then normalise (IntegerNotNormalised (reverse_sign sx, reverse_magnitude nmagnitude))
else Integer (sx, nmagnitude)

normaliseDigit : Int -> (Int, Digit)
normaliseDigit d =
if d < 0
then let (carry, d') = normaliseDigit (d + max_digit_value) in
(carry - 1, d')
else (d // max_digit_value, d `rem` max_digit_value)

normaliseDigitList : List Int -> List Digit
normaliseDigitList x =
case x of
[] -> []
d :: [] ->
let (c, d') = normaliseDigit d in
if c /= 0
then [d', c]
else [d']
d :: d2 :: xs ->
let (c, d') = normaliseDigit d in
d' :: normaliseDigitList (d2 + c :: xs)

dropWhile : (a -> Bool) -> List a -> List a
dropWhile f x =
case x of
[] -> []
a :: xs ->
if f a
then dropWhile f xs
else a :: xs

dropZeroes : List Digit -> List Digit
dropZeroes x =
let rev_list = List.reverse x
no_zeros = dropWhile (\x -> x == 0) rev_list in
List.reverse no_zeros

normaliseMagnitude : MagnitudeNotNormalised -> Magnitude
normaliseMagnitude (MagnitudeNotNormalised x) =
Magnitude (dropZeroes (normaliseDigitList x))

toPositiveSign : Integer -> IntegerNotNormalised
toPositiveSign (Integer (s, Magnitude m)) =
let reverse_magnitude (Magnitude xs) =
MagnitudeNotNormalised (List.map (\x -> -x) xs)
in
case s of
Positive -> IntegerNotNormalised (s, MagnitudeNotNormalised m)
Negative -> IntegerNotNormalised (Positive, reverse_magnitude (Magnitude m))

add : Integer -> Integer -> Integer
let (IntegerNotNormalised (_, ma)) = toPositiveSign a
(IntegerNotNormalised (_, mb)) = toPositiveSign b
(MagnitudePair (p)) = sameSize' ma mb
added = List.map (\(x, y) -> x+y) p
in

{-| Changes the sign of an Integer -}
negate : Integer -> Integer
negate (Integer (s, m)) =
let newsign = case s of
Positive -> Negative
Negative -> Positive
in
normalise (toPositiveSign (Integer (newsign, m)))

{-| Absolute value -}
abs : Integer -> Integer
abs (Integer (s, m)) = Integer (Positive, m)

{-| Substracts the second Integer from the first -}
sub : Integer -> Integer -> Integer
sub a b = add a (negate b)

{-| Multiplies two Integers -}
mul : Integer -> Integer -> Integer
mul (Integer (s1, m1)) (Integer (s2, m2)) =
let sign = case (s1, s2) of
(Positive, Positive) -> Positive
(Negative, Negative) -> Positive
_ -> Negative
in
Integer (sign, (mul_magnitudes m1 m2))

mul_magnitudes : Magnitude -> Magnitude -> Magnitude
mul_magnitudes (Magnitude m1) (Magnitude m2) =
case m1 of
[] ->
Magnitude []
[m] ->
mul_single_digit (Magnitude m2) m
m :: mx ->
let accum = mul_single_digit (Magnitude m2) m
(Magnitude rest) = mul_magnitudes (Magnitude mx) (Magnitude m2)
i1 = (Integer (Positive, accum))
i2 = (Integer (Positive, (Magnitude (0 :: rest))))
(Integer (_, result)) = i1 `add` i2
in
result

mul_single_digit : Magnitude -> Digit -> Magnitude
mul_single_digit (Magnitude m) d =
normaliseMagnitude (MagnitudeNotNormalised (List.map (\x -> d * x) m))

{-| Compares two Integers -}
compare : Integer -> Integer -> Order
compare (Integer (sa, a)) (Integer (sb, b)) =
let invert_order x =
case x of
LT -> GT
EQ -> EQ
GT -> LT
in
case (sa, sb) of
(Positive, Negative) -> GT
(Negative, Positive) -> LT
_ ->
let ss = sameSize a b
if sa == Positive
then cr
else invert_order cr

{-| Equals -}
eq : Integer -> Integer -> Bool
eq a b =
case compare a b of
EQ -> True
_ -> False

{-| Not equals -}
neq : Integer -> Integer -> Bool
neq a b = not (eq a b)

{-| Less than -}
lt : Integer -> Integer -> Bool
lt a b =
case compare a b of
LT -> True
_ -> False

{-| Greater than -}
gt : Integer -> Integer -> Bool
gt a b =
case compare a b of
GT -> True
_ -> False

{-| Greater than or equals -}
gte : Integer -> Integer -> Bool
gte a b =
case compare a b of
GT -> True
EQ -> True
_ -> False

{-| Less than or equals -}
lte : Integer -> Integer -> Bool
lte a b =
case compare a b of
LT -> True
EQ -> True
_ -> False

{-| Returns the largest of two Integers -}
max : Integer -> Integer -> Integer
max a b =
case compare a b of
GT -> a
EQ -> a
LT -> b

{-| Returns the smallest of two Integers -}
min : Integer -> Integer -> Integer
min a b =
case compare a b of
LT -> a
EQ -> a
GT -> b

type MagnitudePairReverseOrder = MagnitudePairReverseOrder (List (Digit, Digit))

reverseMagnitudePair : MagnitudePair -> MagnitudePairReverseOrder
reverseMagnitudePair (MagnitudePair x) = MagnitudePairReverseOrder <| List.reverse x

compareMagnitude : MagnitudePairReverseOrder -> Order
compareMagnitude (MagnitudePairReverseOrder m) =
case m of
[] -> EQ
(a, b) :: xs ->
if a == b
then compareMagnitude (MagnitudePairReverseOrder xs)
else Basics.compare a b

zeroes : Int -> String
zeroes n =
String.repeat n "0"

fillZeroes : Digit -> String
fillZeroes d =
let d_s = Basics.toString d in
let len = String.length d_s in
zeroes (6 - len) ++ d_s

revmagnitudeToString : List Digit -> String
revmagnitudeToString m =
case m of
[] ->
"0"
[x] ->
Basics.toString x
x :: xs ->
(Basics.toString x) ++ String.concat (List.map fillZeroes xs)

{-| Converts the Integer to a String -}
toString : Integer -> String
toString (Integer (s, Magnitude m)) =
let sign = if s == Positive then "" else "-" in
sign ++ revmagnitudeToString (List.reverse m)

range : Int -> Int -> List Int
range a b =
if a == b
then [a]
else a :: range (a+1) b

dividers : List Integer
dividers =
let log = Basics.logBase 2 (Basics.toFloat max_digit_value)
log_i = (Basics.truncate log) + 1
exp_values = List.reverse (range 0 log_i)
int_values = List.map (\x -> 2 ^ x) exp_values
in
List.map fromInt int_values

if n == 0
then fromInt 1
else (pad_digits (n-1)) `mul` (fromInt max_digit_value)

divmod_digit : Integer -> List Integer -> Integer -> Integer -> (Integer, Integer)
divmod_digit padding to_test a b =
case to_test of
[] ->
(fromInt 0, a)
x :: xs ->
let candidate = x `mul` b `mul` padding
(newdiv, newmod) = if candidate `lte` a
then (x `mul` padding, a `sub`candidate)
else (fromInt 0, a)
(restdiv, restmod) = divmod_digit padding xs newmod b
in

divmod' : Int -> Integer -> Integer -> (Integer, Integer)
divmod' n a b =
if n == 0
then divmod_digit (pad_digits n) dividers a b
else
let (cdiv, cmod) = divmod_digit (pad_digits n) dividers a b
(rdiv, rmod) = divmod' (n-1) cmod b
in

{-| Division and modulus -}
divmod : Integer -> Integer -> Maybe (Integer, Integer)
divmod a b =
if b `eq` zero
then Nothing
else
let (Integer (s1, Magnitude m1)) = a
(Integer (s2, Magnitude m2)) = b
cand_l = (List.length m1) - (List.length m2) + 1
l = if cand_l < 0 then 0 else cand_l
sign = case (s1, s2) of
(Positive, Positive) -> Positive
(Negative, Negative) -> Positive
_ -> Negative
(Integer (_, d), Integer (_, m)) = divmod' l (abs a) (abs b)
in
Just (Integer (sign, d), Integer (s1, m))

{-| divmod that returns the pair of values, or crashes if the divisor is zero -}
unsafeDivmod : Integer -> Integer -> (Integer, Integer)
unsafeDivmod a b =
let v = divmod a b in
case v of
Just r -> r
Nothing -> Debug.crash "Divide by zero"

{-| Get the sign of the integer -}
sign : Integer -> Sign
sign (Integer (x, _)) = x

{-| Number 0 -}
zero : Integer
zero = fromInt 0

{-| Number 1 -}
one : Integer
one = fromInt 1

{-| Number -1 -}
minusOne : Integer
minusOne = fromInt -1
```
```