Tropical algebra overloading

Tropical algebra overloading is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

In algebra, a max tropical semiring (also called a max-plus algebra) is the semiring (ℝ ∪ -Inf, ⊕, ⊗) containing the ring of real numbers ℝ augmented by negative infinity, the max function (returns the greater of two real numbers), and addition.

In max tropical algebra, x ⊕ y = max(x, y) and x ⊗ y = x + y. The identity for ⊕ is -Inf (the max of any number with -infinity is that number), and the identity for ⊗ is 0.

Task

• Define functions or, if the language supports the symbols as operators, operators for ⊕ and ⊗ that fit the above description. If the language does not support ⊕ and ⊗ as operators but allows overloading operators for a new object type, you may instead overload + and * for a new min tropical albrbraic type. If you cannot overload operators in the language used, define ordinary functions for the purpose.

Show that 2 ⊗ -2 is 0, -0.001 ⊕ -Inf is -0.001, 0 ⊗ -Inf is -Inf, 1.5 ⊕ -1 is 1.5, and -0.5 ⊗ 0 is -0.5.

• Define exponentiation as serial ⊗, and in general that a to the power of b is a * b, where a is a real number and b must be a positive integer. Use either ↑ or similar up arrow or the carat ^, as an exponentiation operator if this can be used to overload such "exponentiation" in the language being used. Calculate 5 ↑ 7 using this definition.

• Max tropical algebra is distributive, so that

  a ⊗ (b ⊕ c) equals a ⊗ b ⊕ b ⊗ c, 

where ⊗ has precedence over ⊕. Demonstrate that 5 ⊗ (8 ⊕ 7) equals 5 ⊗ 8 ⊕ 5 ⊗ 7.

• If the language used does not support operator overloading, you may use ordinary function names such as tropicalAdd(x, y) and tropicalMul(x, y).

See also

• [Tropical algebra]
• [Tropical geometry review article]
• [Operator overloading]

Factor

Works with: Factor version 0.99 2021-06-02

<lang factor>USING: io kernel math math.order present prettyprint sequences typed ;

ALIAS: ⊕ max ALIAS: ⊗ + PREDICATE: posint < integer 0 > ; TYPED: ↑ ( x: real n: posint -- y: real ) * ;

show ( quot -- )

   dup present rest but-last "⟶ " append write call . ; inline

{

   [ 2 -2 ⊗ ]
   [ -0.001 -1/0. ⊕ ]
   [ 0 -1/0. ⊗ ]
   [ 1.5 -1 ⊕ ]
   [ -0.5 0 ⊗ ]
   [ 5 7 ↑ ]
   [ 8 7 ⊕ 5 ⊗ ]
   [ 5 8 ⊗ 5 7 ⊗ ⊕ ]
   [ 8 7 ⊕ 5 ⊗   5 8 ⊗ 5 7 ⊗ ⊕   = ]

} [ show ] each</lang>

Output:

 2 -2 ⊗ ⟶ 0
 -0.001 -1/0. ⊕ ⟶ -0.001
 0 -1/0. ⊗ ⟶ -1/0.
 1.5 -1 ⊕ ⟶ 1.5
 -0.5 0 ⊗ ⟶ -0.5
 5 7 ↑ ⟶ 35
 8 7 ⊕ 5 ⊗ ⟶ 13
 5 8 ⊗ 5 7 ⊗ ⊕ ⟶ 13
 8 7 ⊕ 5 ⊗ 5 8 ⊗ 5 7 ⊗ ⊕ = ⟶ t

Go

Translation of: Wren

Go doesn't support operator overloading so we need to use functions instead. <lang go>package main

import (

   "fmt"
   "log"
   "math"

)

var MinusInf = math.Inf(-1)

type MaxTropical struct{ r float64 }

func newMaxTropical(r float64) MaxTropical {

   if math.IsInf(r, 1) || math.IsNaN(r) {
       log.Fatal("Argument must be a real number or negative infinity.")
   }
   return MaxTropical{r}

}

func (t MaxTropical) eq(other MaxTropical) bool {

   return t.r == other.r

}

// equivalent to ⊕ operator func (t MaxTropical) add(other MaxTropical) MaxTropical {

   if t.r == MinusInf {
       return other
   }
   if other.r == MinusInf {
       return t
   }
   return newMaxTropical(math.Max(t.r, other.r))

}

// equivalent to ⊗ operator func (t MaxTropical) mul(other MaxTropical) MaxTropical {

   if t.r == 0 {
       return other
   }
   if other.r == 0 {
       return t
   }
   return newMaxTropical(t.r + other.r)

}

// exponentiation function func (t MaxTropical) pow(e int) MaxTropical {

   if e < 1 {
       log.Fatal("Exponent must be a positive integer.")
   }
   if e == 1 {
       return t
   }
   p := t
   for i := 2; i <= e; i++ {
       p = p.mul(t)
   }
   return p

}

func (t MaxTropical) String() string {

   return fmt.Sprintf("%g", t.r)

}

func main() {

   // 0 denotes ⊕ and 1 denotes ⊗
   data := [][]float64{
       {2, -2, 1},
       {-0.001, MinusInf, 0},
       {0, MinusInf, 1},
       {1.5, -1, 0},
       {-0.5, 0, 1},
   }
   for _, d := range data {
       a := newMaxTropical(d[0])
       b := newMaxTropical(d[1])
       if d[2] == 0 {
           fmt.Printf("%s ⊕ %s = %s\n", a, b, a.add(b))
       } else {
           fmt.Printf("%s ⊗ %s = %s\n", a, b, a.mul(b))
       }
   }

   c := newMaxTropical(5)
   fmt.Printf("%s ^ 7 = %s\n", c, c.pow(7))

   d := newMaxTropical(8)
   e := newMaxTropical(7)
   f := c.mul(d.add(e))
   g := c.mul(d).add(c.mul(e))
   fmt.Printf("%s ⊗ (%s ⊕ %s) = %s\n", c, d, e, f)
   fmt.Printf("%s ⊗ %s ⊕ %s ⊗ %s = %s\n", c, d, c, e, g)
   fmt.Printf("%s ⊗ (%s ⊕ %s) == %s ⊗ %s ⊕ %s ⊗ %s is %t\n", c, d, e, c, d, c, e, f.eq(g))

}</lang>

Output:

2 ⊗ -2 = 0
-0.001 ⊕ -Inf = -0.001
0 ⊗ -Inf = -Inf
1.5 ⊕ -1 = 1.5
-0.5 ⊗ 0 = -0.5
5 ^ 7 = 35
5 ⊗ (8 ⊕ 7) = 13
5 ⊗ 8 ⊕ 5 ⊗ 7 = 13
5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 is true

Julia

<lang julia>⊕(x, y) = max(x, y) ⊗(x, y) = x + y ↑(x, y) = (@assert round(y) == y && y > 0; x * y)

@show 2 ⊗ -2 @show -0.001 ⊕ -Inf @show 0 ⊗ -Inf @show 1.5 ⊕ -1 @show -0.5 ⊗ 0 @show 5↑7 @show 5 ⊗ (8 ⊕ 7) @show 5 ⊗ 8 ⊕ 5 ⊗ 7 @show 5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7

</lang>

Output:

2 ⊗ -2 = 0
-0.001 ⊕ -Inf = -0.001
0 ⊗ -Inf = -Inf
1.5 ⊕ -1 = 1.5
-0.5 ⊗ 0 = -0.5
5 ↑ 7 = 35
5 ⊗ (8 ⊕ 7) = 13
5 ⊗ 8 ⊕ 5 ⊗ 7 = 13
5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 = true

Phix

Phix does not support operator overloading. I trust max is self-evident, sq_add and sq_mul are existing wrappers to the + and * operators, admittedly with extra (sequence) functionality we don't really need here, but they'll do just fine.

with javascript_semantics
requires("1.0.1") -- (minor/backportable bugfix rqd to handling of -inf in printf[1])
constant tropicalAdd = max,
         tropicalMul = sq_add,
         tropicalExp = sq_mul,
         inf = 1e300*1e300

printf(1,"tropicalMul(2,-2) = %g\n",
         {tropicalMul(2,-2)})
printf(1,"tropicalAdd(-0.001,-inf) = %g\n",
         {tropicalAdd(-0.001,-inf)})
printf(1,"tropicalMul(0,-inf) = %g\n",
         {tropicalMul(0,-inf)})
printf(1,"tropicalAdd(1.5,-1) = %g\n",
         {tropicalAdd(1.5,-1)})
printf(1,"tropicalMul(-0.5,0) = %g\n",
         {tropicalMul(-0.5,0)})
printf(1,"tropicalExp(5,7) = %g\n",
         {tropicalExp(5,7)})
printf(1,"tropicalMul(5,tropicalAdd(8,7)) = %g\n",
         {tropicalMul(5,tropicalAdd(8,7))})
printf(1,"tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = %g\n",
         {tropicalAdd(tropicalMul(5,8),tropicalMul(5,7))})
printf(1,"tropicalMul(5,tropicalAdd(8,7)) == tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = %t\n",
         {tropicalMul(5,tropicalAdd(8,7)) == tropicalAdd(tropicalMul(5,8),tropicalMul(5,7))})

[1]This task exposed a couple of "and o!=inf" that needed to become "and o!=inf and o!=-inf" in builtins\VM\pprintfN.e - thanks!

Output:

tropicalMul(2,-2) = 0
tropicalAdd(-0.001,-inf) = -0.001
tropicalMul(0,-inf) = -inf
tropicalAdd(1.5,-1) = 1.5
tropicalMul(-0.5,0) = -0.5
tropicalExp(5,7) = 35
tropicalMul(5,tropicalAdd(8,7)) = 13
tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = 13
tropicalMul(5,tropicalAdd(8,7)) == tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = true

Python

<lang python>from numpy import Inf

class MaxTropical:

   """
   Class for max tropical algebra.
   x + y is max(x, y) and X * y is x + y
   """
   def __init__(self, x=0):
       self.x = x

   def __str__(self):
       return str(self.x)

   def __add__(self, other):
       return MaxTropical(max(self.x, other.x))

   def __mul__(self, other):
       return MaxTropical(self.x + other.x)

   def __pow__(self, other):
       assert other.x // 1 == other.x and other.x > 0, "Invalid Operation" 
       return MaxTropical(self.x * other.x)

   def __eq__(self, other):
       return self.x == other.x

if __name__ == "__main__":

   a = MaxTropical(-2)
   b = MaxTropical(-1)
   c = MaxTropical(-0.5)
   d = MaxTropical(-0.001)
   e = MaxTropical(0)
   f = MaxTropical(0.5)
   g = MaxTropical(1)
   h = MaxTropical(1.5)
   i = MaxTropical(2)
   j = MaxTropical(5)
   k = MaxTropical(7)
   l = MaxTropical(8)
   m = MaxTropical(-Inf)

   print("2 * -2 == ", i * a)
   print("-0.001 + -Inf == ", d + m)
   print("0 * -Inf == ", e * m)
   print("1.5 + -1 == ", h + b)
   print("-0.5 * 0 == ", c * e)
   print("5**7 == ", j**k)
   print("5 * (8 + 7)) == ", j * (l + k))
   print("5 * 8 + 5 * 7 == ", j * l + j * k)
   print("5 * (8 + 7) == 5 * 8 + 5 * 7", j * (l + k) == j * l + j * k)

</lang>

Output:

2 * -2 ==  0
-0.001 + -Inf ==  -0.001
0 * -Inf ==  -inf
1.5 + -1 ==  1.5
-0.5 * 0 ==  -0.5
5 ** 7 ==  35
5 * (8 + 7)) ==  13
5 * 8 + 5 * 7 ==  13
5 * (8 + 7) == 5 * 8 + 5 * 7 True

R

R's overloaded operators, denoted by %_%, have different precedence order than + and *, so parentheses are needed for the distributive example. <lang r>"%+%"<- function(x, y) max(x, y)

"%*%" <- function(x, y) x + y

"%^%" <- function(x, y) {

 stopifnot(round(y) == y && y > 0)
 x * y

}

cat("2 %*% -2 ==", 2 %*% -2, "\n") cat("-0.001 %+% -Inf ==", 0.001 %+% -Inf, "\n") cat("0 %*% -Inf ==", 0 %*% -Inf, "\n") cat("1.5 %+% -1 ==", 1.5 %+% -1, "\n") cat("-0.5 %*% 0 ==", -0.5 %*% 0, "\n") cat("5^7 ==", 5 %^% 7, "\n") cat("5 %*% (8 %+% 7)) ==", 5 %*% (8 %+% 7), "\n") cat("5 %*% 8 %+% 5 %*% 7 ==", (5 %*% 8) %+% (5 %*% 7), "\n") cat("5 %*% 8 %+% 5 %*% 7 == 5 %*% (8 %+% 7))", 5 %*% (8 %+% 7) == (5 %*% 8) %+% (5 %*% 7), "\n")

</lang>

Output:

2 %*% -2 == 0
-0.001 %+% -Inf == 0.001
0 %*% -Inf == -Inf
1.5 %+% -1 == 1.5
-0.5 %*% 0 == -0.5
5^7 == 35
5 %*% (8 %+% 7)) == 13 
5 %*% 8 %+% 5 %*% 7 == 13
5 %*% 8 %+% 5 %*% 7 == 5 %*% (8 %+% 7)) TRUE

Wren

<lang ecmascript>var MinusInf = -1/0

class MaxTropical {

   construct new(r) {
       if (r.type != Num || r == 1/0 || r == 0/0) {
           Fiber.abort("Argument must be a real number or negative infinity.")
       }
       _r = r
   }

   r { _r }

   ==(other) {
       if (other.type != MaxTropical) Fiber.abort("Argument must be a MaxTropical object.")
       return _r == other.r
   }

   // equivalent to ⊕ operator
   +(other) {
       if (other.type != MaxTropical) Fiber.abort("Argument must be a MaxTropical object.")
       if (_r == MinusInf) return other
       if (other.r == MinusInf) return this
       return MaxTropical.new(_r.max(other.r))
   }

   // equivalent to ⊗ operator
   *(other) {
       if (other.type != MaxTropical) Fiber.abort("Argument must be a MaxTropical object.")
       if (_r == 0) return other
       if (other.r == 0) return this
       return MaxTropical.new(_r + other.r)
   }

   // exponentiation operator
   ^(e) {
       if (e.type != Num || !e.isInteger || e < 1) {
           Fiber.abort("Argument must be a positive integer.")
       }
       if (e == 1) return this
       var pow = MaxTropical.new(_r)
       for (i in 2..e) pow = pow * this
       return pow
   }

   toString { _r.toString }

}

var data = [

   [2, -2, "⊗"],
   [-0.001, MinusInf, "⊕"],
   [0, MinusInf, "⊗"],
   [1.5, -1, "⊕"],
   [-0.5, 0, "⊗"]

] for (d in data) {

   var a = MaxTropical.new(d[0])
   var b = MaxTropical.new(d[1])
   if (d[2] == "⊕") {
       System.print("%(a) ⊕ %(b) = %(a + b)")
   } else {
       System.print("%(a) ⊗ %(b) = %(a * b)")
   }

}

var c = MaxTropical.new(5) System.print("%(c) ^ 7 = %(c ^ 7)")

var d = MaxTropical.new(8) var e = MaxTropical.new(7) var f = c * (d + e) var g = c * d + c * e System.print("%(c) ⊗ (%(d) ⊕ %(e)) = %(f)") System.print("%(c) ⊗ %(d) ⊕ %(c) ⊗ %(e) = %(g)") System.print("%(c) ⊗ (%(d) ⊕ %(e)) == %(c) ⊗ %(d) ⊕ %(c) ⊗ %(e) is %(f == g)")</lang>

Output:

2 ⊗ -2 = 0
-0.001 ⊕ -infinity = -0.001
0 ⊗ -infinity = -infinity
1.5 ⊕ -1 = 1.5
-0.5 ⊗ 0 = -0.5
5 ^ 7 = 35
5 ⊗ (8 ⊕ 7) = 13
5 ⊗ 8 ⊕ 5 ⊗ 7 = 13
5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 is true