lib/mlton/basic/euclidean-ring.sig

   1 (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   2  *    Jagannathan, and Stephen Weeks.
   3  *
   4  * MLton is released under a BSD-style license.
   5  * See the file MLton-LICENSE for details.
   6  *)
   7
   8 signature EUCLIDEAN_RING_STRUCTS =
   9    sig
  10       include RING_WITH_IDENTITY
  11
  12       (* Two elements a, b are "unit equivalent" if there is a unit element u
  13        * such that au = b.
  14        *)
  15
  16       val divMod: t * t -> t * t
  17       val metric: t -> Pervasive.IntInf.int
  18       (* Monics should be an (infinite) stream of all (except for zero and one)
  19        * the representatives of the unit equivalence classes in nondecreasing
  20        * order of metric.
  21        *)
  22       val monics: t Stream.t
  23       (* Map an element to the representative of its unit equivalence class. *)
  24       val unitEquivalent: t -> t
  25    end
  26
  27 signature EUCLIDEAN_RING =
  28    sig
  29       include EUCLIDEAN_RING_STRUCTS
  30
  31       val div: t * t -> t
  32       val divides: t * t -> bool
  33       val extendedEuclid: t * t -> t * t * t
  34       val extendedEuclidTerm: t * t * (t * t -> bool) -> t * t * t
  35       val factor: t -> (t * Pervasive.Int.int) list
  36       val gcd: t * t -> t
  37       val isComposite: t -> bool
  38       val isPrime: t -> bool
  39       val lcm: t * t -> t
  40       val primes: t Stream.t
  41       val mod: t * t -> t
  42    end