--
--
-- Number
--
--

--
-- Natural Numbers
--
def nats : [Integer] :=
  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
   11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
   21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
   31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
   41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
   51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
   61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
   71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
   81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
   91, 92, 93, 94, 95, 96, 97, 98, 99, 100] ++
    map (+ 100) nats

def nats0 : [Integer] := 0 :: nats

def odds : [Integer] := 1 :: map (+ 2) odds
def evens : [Integer] := 2 :: map (+ 2) evens

def fibs : [Integer] := [1, 1] ++ map2 (+) fibs (tail fibs)

def isPrime (n: Integer) : Bool :=
  if n < 2 then False else n = findFactor n

def primes : [Integer] := 2 :: filter isPrime (drop 2 nats)

def (%) (n: Integer) (d: Integer) : Integer := i.% n d

def divisor (n: Integer) (d: Integer) : Bool := 0 = n % d

def findFactor : Integer -> Integer :=
  memoizedLambda n ->
    match takeWhile (<= floor (f.sqrt (itof n))) primes as list integer with
      | _ ++ (?(divisor n) & $x) :: _ -> x
      | _ -> n

def primeFactorization : Integer -> [Integer] :=
  \match as integer with
    | #1 -> []
    | ?(< 0) & $n -> (-1) :: primeFactorization (i.neg n)
    | $n ->
      let p := findFactor n
       in p :: primeFactorization (i.quotient n p)

def pF : Integer -> [Integer] := primeFactorization

def isEven (n: Integer) : Bool := 0 = i.modulo n 2
def isOdd (n: Integer) : Bool := 1 = i.modulo n 2

def fact (n: Integer) : Integer := foldl (*) 1 [1..n]

def perm (n: Integer) (r: Integer) : Integer := foldl (*) 1 [(n - (r - 1))..n]

def comb (n: Integer) (r: Integer) : Integer := perm n r / fact r

def nAdic (n: Integer) (x: Integer) : [Integer] :=
  if x = 0
    then []
    else let q := i.quotient x n
             r := i.modulo x n
          in nAdic n q ++ [r]

--
-- Integers
--
def mod (m: Integer) : Matcher Integer :=
  matcher
    | #$n as () with
      | $tgt -> if i.modulo tgt m = i.modulo n m then [()] else []
    | $ as (something) with
      | $tgt -> [tgt]

--
-- Floats
--
def exp2 (x: Float) (y: Float) : Float := f.exp (f.log x * y)

--
-- Decimal Fractions
--
def rtodHelper (m: Integer) (n: Integer) : [(Integer, Integer)] :=
  let q := i.quotient (m * 10) n
      r := i.modulo (m * 10) n
   in (q, r) :: rtodHelper r n

def rtod (x: Integer) : (Integer, [Integer], [Integer]) :=
  let m := numerator x
      n := denominator x
      q := i.quotient m n
      r := i.modulo m n
      (s, c) := findCycle (rtodHelper r n)
   in (q, map fst s, map fst c)

--
-- Continued Fraction
--
def regularContinuedFraction (n: Integer) (xs: [Integer]) : Integer := n + foldr (\a r -> 1 / (a + r)) 0 xs

def continuedFraction (n: Integer) (xs: [Integer]) (ys: [Integer]) : Integer :=
  match (xs, ys) as (list integer, list integer) with
    | ($x :: $xs, $y :: $ys) -> n + y / continuedFraction x xs ys
    | ([], []) -> n

def regularContinuedFractionOfSqrtHelper (m: Integer) (a: Integer) (b: Integer) : [(Integer, Integer, Integer)] :=
  let n := floor (f.+ (rtof a) (f.* (rtof b) (f.sqrt (rtof m))))
      x := m - i.power n 2
   in if x = 0
        then [(a, b, n)]
        else let y := i.power (n - a) 2 - b * b * m
              in (a, b, n) :: regularContinuedFractionOfSqrtHelper
                                m
                                ((a - n) / y)
                                (i.neg (b / y))

def regularContinuedFractionOfSqrt (m: Integer) : (Integer, [Integer], [Integer]) :=
  let n := floor (f.sqrt (rtof m))
      x := m - i.power n 2
   in if x = 0
        then (n, [], [])
        else let (s, c) := findCycle
                             (regularContinuedFractionOfSqrtHelper
                                m
                                (n / x)
                                (1 / x))
              in (n, map (3)#$3 s, map (3)#$3 c)

def pi := f.pi