Ring Structures

/**
 * Additive semigroup providing plus operation
 */
trait AdditiveSemigroup[A] {
  /** Get the underlying semigroup for addition */
  def additive: Semigroup[A]
  /** Addition operation */
  def plus(x: A, y: A): A
  /** Sum n copies of a value */
  def sumN(a: A, n: Int): A
  /** Sum n copies where n > 0 */
  def positiveSumN(a: A, n: Int): A
  /** Safely sum a collection of values */
  def trySum(as: TraversableOnce[A]): Option[A]
}

/**
 * Additive monoid with zero element
 */  
trait AdditiveMonoid[A] extends AdditiveSemigroup[A] {
  /** Additive identity */
  def zero: A
  /** Test if value equals zero */
  def isZero(a: A)(implicit ev: Eq[A]): Boolean
  /** Sum all elements in a collection */
  def sum(as: TraversableOnce[A]): A
}

/**
 * Additive group with subtraction (additive inverse)
 */
trait AdditiveGroup[A] extends AdditiveMonoid[A] {
  /** Additive inverse (negation) */
  def negate(x: A): A  
  /** Subtraction operation */
  def minus(x: A, y: A): A
}

/**
 * Multiplicative semigroup providing times operation
 */
trait MultiplicativeSemigroup[A] {
  /** Get the underlying semigroup for multiplication */
  def multiplicative: Semigroup[A]
  /** Multiplication operation */
  def times(x: A, y: A): A
  /** Exponentiation */
  def pow(a: A, n: Int): A
  /** Positive exponentiation */ 
  def positivePow(a: A, n: Int): A
  /** Safely compute product of a collection */
  def tryProduct(as: TraversableOnce[A]): Option[A]
}

/**
 * Multiplicative monoid with one element
 */
trait MultiplicativeMonoid[A] extends MultiplicativeSemigroup[A] {
  /** Multiplicative identity */
  def one: A
  /** Test if value equals one */
  def isOne(a: A)(implicit ev: Eq[A]): Boolean
  /** Product of all elements in a collection */
  def product(as: TraversableOnce[A]): A
}

/**
 * Multiplicative group with division (multiplicative inverse)
 */
trait MultiplicativeGroup[A] extends MultiplicativeMonoid[A] {
  /** Multiplicative inverse (reciprocal) */
  def reciprocal(x: A): A
  /** Division operation */
  def div(x: A, y: A): A
}

/**
 * Semiring: additive commutative monoid + multiplicative semigroup + distributivity
 * Distributivity: times(a, plus(b, c)) == plus(times(a, b), times(a, c))
 */
trait Semiring[A] extends AdditiveCommutativeMonoid[A] with MultiplicativeSemigroup[A]

/**
 * Rig: semiring with multiplicative identity
 * Sometimes called "semiring with one" or "ring without negation"
 */
trait Rig[A] extends Semiring[A] with MultiplicativeMonoid[A]

/**
 * Rng: semiring with additive inverse 
 * Sometimes called "ring without one" or "pseudo-ring"
 */
trait Rng[A] extends Semiring[A] with AdditiveCommutativeGroup[A]

/**
 * Ring: combines rig and rng (full ring structure)
 * Has additive group + multiplicative monoid + distributivity
 */
trait Ring[A] extends Rig[A] with Rng[A] {
  /** Convert integer to ring element */
  def fromInt(n: Int): A
  /** Convert BigInt to ring element */
  def fromBigInt(n: BigInt): A
}

object Ring {
  /** Get Ring instance for type A */
  def apply[A](implicit ev: Ring[A]): Ring[A] = ev
}

import algebra.ring._
import algebra.instances.all._

val intRing = Ring[Int]
val sum = intRing.plus(3, 4)  // 7
val product = intRing.times(3, 4)  // 12
val fromInt = intRing.fromInt(42)  // 42

// Distributivity: a * (b + c) == (a * b) + (a * c)
val a = 2
val b = 3 
val c = 5
val left = intRing.times(a, intRing.plus(b, c))  // 2 * (3 + 5) = 16
val right = intRing.plus(intRing.times(a, b), intRing.times(a, c))  // 2*3 + 2*5 = 16
// left == right (distributivity holds)

/**
 * Ring where multiplication is commutative
 * times(a, b) == times(b, a) for all a, b
 */
trait CommutativeRing[A] extends Ring[A] with CommutativeRig[A] with CommutativeRng[A]

/**
 * Ring with multiplicative inverse (division)
 * Every non-zero element has a multiplicative inverse
 */
trait DivisionRing[A] extends Ring[A] with Semifield[A] {
  /** Convert Double to ring element */
  def fromDouble(a: Double): A
}

/**
 * Field: commutative division ring
 * Every non-zero element has multiplicative inverse and multiplication is commutative
 */
trait Field[A] extends EuclideanRing[A] with DivisionRing[A] with CommutativeSemifield[A] {
  // Provides default field implementations for Euclidean operations:
  // - euclideanFunction(a: A): BigInt = BigInt(0)
  // - equot(a: A, b: A): A = div(a, b)  
  // - emod(a: A, b: A): A = zero
  // - gcd(a: A, b: A): A = if both zero then zero else one
  // - lcm(a: A, b: A): A = times(a, b)
}

object Field {
  /** Get Field instance for type A */
  def apply[A](implicit ev: Field[A]): Field[A] = ev
}

import algebra.ring._
import spire.math.Rational  // For exact rational arithmetic

val ratField = Field[Rational]
val a = Rational(3, 4)  // 3/4
val b = Rational(2, 5)  // 2/5

val sum = ratField.plus(a, b)  // 3/4 + 2/5 = 23/20
val product = ratField.times(a, b)  // 3/4 * 2/5 = 6/20 = 3/10
val quotient = ratField.div(a, b)  // (3/4) / (2/5) = 15/8
val inverse = ratField.reciprocal(a)  // 4/3

/**
 * Commutative ring with greatest common divisor operations
 */
trait GCDRing[A] extends CommutativeRing[A] {
  /** Greatest common divisor */
  def gcd(a: A, b: A)(implicit eqA: Eq[A]): A
  /** Least common multiple */  
  def lcm(a: A, b: A)(implicit eqA: Eq[A]): A
}

/**
 * Ring with Euclidean division algorithm
 * Examples: integers, Gaussian integers, polynomials over fields
 */
trait EuclideanRing[A] extends GCDRing[A] {
  /** Euclidean function (size/degree measure) */
  def euclideanFunction(a: A): BigInt
  /** Euclidean quotient */
  def equot(a: A, b: A): A  
  /** Euclidean remainder */
  def emod(a: A, b: A): A
  /** Combined quotient and remainder */
  def equotmod(a: A, b: A): (A, A)
}

object EuclideanRing {
  /** Euclidean algorithm for GCD */
  def euclid[A](a: A, b: A)(implicit ev: EuclideanRing[A], eqA: Eq[A]): A
}

import algebra.ring._
import algebra.instances.all._

val bigIntRing = EuclideanRing[BigInt]
val a = BigInt(48)
val b = BigInt(18)

val gcd = bigIntRing.gcd(a, b)  // 6
val lcm = bigIntRing.lcm(a, b)  // 144
val (quotient, remainder) = bigIntRing.equotmod(a, b)  // (2, 12)
// Verification: 48 = 18 * 2 + 12

/**
 * Boolean rng where every element equals its own negation
 * negate(x) == x for all x
 */
trait BoolRng[A] extends CommutativeRng[A] {
  override def negate(x: A): A = x
}

/**
 * Boolean ring where addition is XOR and multiplication is AND
 * Every element is idempotent: times(x, x) == x
 */
trait BoolRing[A] extends BoolRng[A] with CommutativeRing[A]

/**
 * Type class for signed types  
 */
trait Signed[A] {
  def additiveCommutativeMonoid: AdditiveCommutativeMonoid[A]
  def order: Order[A]
  /** Get the sign of a value */
  def sign(a: A): Sign
  /** Sign as integer (-1, 0, 1) */  
  def signum(a: A): Int
  /** Absolute value */
  def abs(a: A): A
  /** Test if zero */
  def isSignZero(a: A): Boolean
  /** Test if positive */
  def isSignPositive(a: A): Boolean  
  /** Test if negative */
  def isSignNegative(a: A): Boolean
  /** Test if non-zero */
  def isSignNonZero(a: A): Boolean
  /** Test if non-positive (≤ 0) */
  def isSignNonPositive(a: A): Boolean
  /** Test if non-negative (≥ 0) */
  def isSignNonNegative(a: A): Boolean
}

/** Sign enumeration */
object Sign {
  case object Zero extends Sign
  case object Positive extends Sign
  case object Negative extends Sign
}

/**
 * Division operations with truncation toward zero
 */
trait TruncatedDivision[A] extends Signed[A] {
  /** Truncated quotient */
  def tquot(a: A, b: A): A
  /** Truncated modulo */  
  def tmod(a: A, b: A): A
  /** Combined truncated operations */
  def tquotmod(a: A, b: A): (A, A)
  /** Floor quotient */
  def fquot(a: A, b: A): A
  /** Floor modulo */
  def fmod(a: A, b: A): A  
  /** Combined floor operations */
  def fquotmod(a: A, b: A): (A, A)
}

import algebra.ring._
import algebra.instances.all._

val signed = Signed[Int]
val value = -42

val sign = signed.sign(value)  // Sign.Negative
val signum = signed.signum(value)  // -1
val absolute = signed.abs(value)  // 42
val isNegative = signed.isSignNegative(value)  // true

// Function traits provide syntax methods
trait RingFunctions[R[T] <: Ring[T]] {
  def fromInt[A](n: Int)(implicit ev: R[A]): A
  def fromBigInt[A](n: BigInt)(implicit ev: R[A]): A
}

trait FieldFunctions[F[T] <: Field[T]] {
  def fromDouble[A](n: Double)(implicit ev: F[A]): A
}

// Companion objects provide apply methods and utilities
object Ring extends RingFunctions[Ring]
object Field extends FieldFunctions[Field]