0
# Algebra
1

2
Algebra is a comprehensive Scala library providing type classes for representing algebraic structures in functional programming. It enables developers to abstract over mathematical structures like semigroups, monoids, groups, rings, fields, and lattices through a systematic type class hierarchy. The library offers basic algebraic structures with properties like associativity and commutativity, ring-like structures combining additive and multiplicative operations with proper mathematical laws, and lattice-like structures for representing bounded partially ordered sets with meet and join operations.
3

4
## Package Information
5

6
- **Package Name**: org.typelevel:algebra_2.13
7
- **Package Type**: Maven
8
- **Language**: Scala
9
- **Installation**: `libraryDependencies += "org.typelevel" %% "algebra" % "2.13.0"`
10

11
## Core Imports
12

13
Basic algebraic structures (re-exported from cats-kernel):
14

15
```scala
16
import algebra._
17
// Imports: Semigroup, Monoid, Group, CommutativeGroup, etc.
18
```
19

20
Ring structures:
21

22
```scala
23
import algebra.ring._
24
// Imports: Ring, Field, Semiring, etc.
25
```
26

27
Lattice structures:
28

29
```scala
30
import algebra.lattice._
31
// Imports: Lattice, Bool, Heyting, etc.
32
```
33

34
Type class instances:
35

36
```scala
37
import algebra.instances.all._
38
// Imports all standard type instances
39
```
40

41
## Basic Usage
42

43
```scala
44
import algebra._
45
import algebra.ring._
46
import algebra.lattice._
47
import algebra.instances.all._
48

49
// Using basic algebraic structures
50
val intMonoid = Monoid[Int]
51
val sum = intMonoid.combine(5, 3)  // 8
52

53
// Using ring operations
54
val intRing = Ring[Int]
55
val result = intRing.plus(intRing.times(3, 4), 2)  // 14
56
val fromInt = intRing.fromInt(42)  // 42
57

58
// Using field operations for rational numbers
59
import spire.math.Rational
60
val ratField = Field[Rational]
61
val quotient = ratField.div(Rational(3, 4), Rational(1, 2))  // 3/2
62

63
// Using lattice operations
64
val boolLattice = Bool[Boolean]
65
val conjunction = boolLattice.and(true, false)  // false
66
val disjunction = boolLattice.or(true, false)   // true
67
```
68

69
## Architecture
70

71
Algebra is built around several key type class hierarchies:
72

73
- **Basic Structures**: Core algebraic concepts (Semigroup, Monoid, Group) re-exported from cats-kernel
74
- **Ring Hierarchy**: Additive and multiplicative structures combined with distributivity laws
75
- **Lattice Hierarchy**: Order-theoretic structures with meet and join operations
76
- **Instances System**: Comprehensive type class instances for Scala's standard types
77
- **Priority System**: Advanced implicit resolution for composable type class derivation
78

79
The library follows mathematical conventions and laws, ensuring type-safe abstractions over algebraic structures.
80

81
## Capabilities
82

83
### Basic Algebraic Structures
84

85
Core algebraic type classes re-exported from cats-kernel, including semigroups, monoids, and groups with their commutative variants.
86

87
```scala { .api }
88
// Type aliases to cats-kernel structures
89
type Semigroup[A] = cats.kernel.Semigroup[A]
90
val Semigroup = cats.kernel.Semigroup
91

92
type Monoid[A] = cats.kernel.Monoid[A]  
93
val Monoid = cats.kernel.Monoid
94

95
type Group[A] = cats.kernel.Group[A]
96
val Group = cats.kernel.Group
97

98
type CommutativeGroup[A] = cats.kernel.CommutativeGroup[A]
99
val CommutativeGroup = cats.kernel.CommutativeGroup
100
```
101

102
[Basic Structures](./basic-structures.md)
103

104
### Ring Structures
105

106
Ring-like algebraic structures combining additive and multiplicative operations with distributivity laws, from basic semirings to advanced structures like fields and Euclidean rings.
107

108
```scala { .api }
109
trait Ring[A] extends Rig[A] with Rng[A] {
110
  def fromInt(n: Int): A
111
  def fromBigInt(n: BigInt): A
112
}
113

114
trait Field[A] extends EuclideanRing[A] with DivisionRing[A] with CommutativeSemifield[A] {
115
  def fromDouble(a: Double): A
116
  def gcd(a: A, b: A)(implicit eqA: Eq[A]): A
117
  def lcm(a: A, b: A)(implicit eqA: Eq[A]): A
118
}
119
```
120

121
[Ring Structures](./ring-structures.md)
122

123
### Lattice Structures
124

125
Lattice-like structures for representing bounded partially ordered sets with meet and join operations, including Boolean algebras and Heyting algebras for logical operations.
126

127
```scala { .api }
128
trait Lattice[A] extends JoinSemilattice[A] with MeetSemilattice[A] {
129
  def dual: Lattice[A]
130
}
131

132
trait Bool[A] extends Heyting[A] with GenBool[A] {
133
  def and(a: A, b: A): A
134
  def or(a: A, b: A): A
135
  def not(a: A): A
136
  def xor(a: A, b: A): A
137
}
138
```
139

140
[Lattice Structures](./lattice-structures.md)
141

142
### Type Class Instances
143

144
Comprehensive type class instances for Scala's standard types, providing algebraic structure implementations for primitives, collections, and other common types.
145

146
```scala { .api }
147
// Instance aggregation trait
148
trait AllInstances extends 
149
  ArrayInstances with BigDecimalInstances with BigIntInstances with
150
  BooleanInstances with ByteInstances with CharInstances with
151
  DoubleInstances with FloatInstances with IntInstances with
152
  ListInstances with LongInstances with MapInstances with
153
  OptionInstances with SetInstances with ShortInstances with
154
  StringInstances with TupleInstances with UnitInstances
155
```
156

157
[Type Class Instances](./instances.md)
158

159
### Priority System
160

161
Advanced implicit resolution system for composable type class derivation, allowing fine-grained control over instance selection and fallback behavior.
162

163
```scala { .api }
164
sealed trait Priority[+P, +F] {
165
  def fold[Z](f: P => Z, g: F => Z): Z
166
  def toEither: Either[F, P]
167
  def isPreferred: Boolean
168
  def isFallback: Boolean
169
}
170

171
case class Preferred[P](get: P) extends Priority[P, Nothing]
172
case class Fallback[F](get: F) extends Priority[Nothing, F]
173
```
174

175
[Priority System](./priority-system.md)
176

177
## Types
178

179
### Core Type Aliases
180

181
```scala { .api }
182
// Basic algebraic structures (re-exported from cats-kernel)
183
type Band[A] = cats.kernel.Band[A]
184
type BoundedSemilattice[A] = cats.kernel.BoundedSemilattice[A]
185
type CommutativeGroup[A] = cats.kernel.CommutativeGroup[A]
186
type CommutativeMonoid[A] = cats.kernel.CommutativeMonoid[A]
187
type CommutativeSemigroup[A] = cats.kernel.CommutativeSemigroup[A]
188
type Eq[A] = cats.kernel.Eq[A]
189
type Group[A] = cats.kernel.Group[A]
190
type Monoid[A] = cats.kernel.Monoid[A]
191
type Order[A] = cats.kernel.Order[A]
192
type PartialOrder[A] = cats.kernel.PartialOrder[A]
193
type Semigroup[A] = cats.kernel.Semigroup[A]
194
type Semilattice[A] = cats.kernel.Semilattice[A]
195
```
196

197
### Sign Type
198

199
```scala { .api }
200
// Sign enumeration for signed types
201
object Sign {
202
  case object Zero extends Sign
203
  case object Positive extends Sign  
204
  case object Negative extends Sign
205
}
206
```