Tropical algebra overloading
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
ALGOL 68
Algol 68 allows operator overloading and even re-defining the built in operators (though the latter is probably frowned on).
Either existing symbols or new symbols or "bold" (normally uppercase) words can be used. Unfortunately, (X) and (+) can't be used as operator symbols, so X is used for (X), + for (+) and ^ for exponentiaion. The standard + and ^ operators are redefined.
<lang algol68>BEGIN # tropical algebra operator overloading #
REAL minus inf = - max real;
PROC real plus = ( REAL a, b )REAL: a + b;
BEGIN PRIO X = 7; # need to specify the precedence of a new dyadic # # operator, X now has the same precedence as * # OP X = ( REAL a, b )REAL: real plus( a, b ); OP + = ( REAL a, b )REAL: IF a < b THEN b ELSE a FI; OP ^ = ( REAL a, INT b )REAL: IF b < 1 THEN print( ( "0 or -ve right operand for ""^""", newline ) ); stop ELSE a * b FI; # additional operators for integer operands # OP X = ( INT a, REAL b )REAL: REAL(a) X b; OP X = ( REAL a, INT b )REAL: a X REAL(b); OP X = ( INT a, b )REAL: REAL(a) X REAL(b); OP + = ( INT a, REAL b )REAL: REAL(a) + b; OP + = ( REAL a, INT b )REAL: a + REAL(b); OP + = ( INT a, b )REAL: REAL(a) + REAL(b); OP ^ = ( INT a, b )REAL: REAL(a) ^ b; # task test cases #
PROC check = ( REAL result, STRING expr, REAL expected )VOID: print( ( expr, IF result = expected THEN " is TRUE" ELSE " is FALSE ****" FI, newline ) );
check( 2 X -2, "2 (X) -2 = 0 ", 0 ); check( -0.001 + minus inf, "-0.001 (+) -Inf = -0.001 ", -0.001 ); check( 0 X minus inf, "0 (X) -Inf = -Inf ", minus inf ); check( 1.5 + 1, "1.5 (+) -1 = 1.5 ", 1.5 ); check( -0.5 X 0, "-0.5 (X) 0 = -0.5 ", -0.5 ); print( ( "5 ^ 7: ", fixed( 5 ^ 7, -6, 1 ), newline ) ); check( 5 X ( 8 + 7 ), "5 (X) ( 8 (+) 7 ) = 5 (X) 8 (+) 5 (X) 7", 5 X 8 + 5 X 7 ) END
END</lang>
- Output:
2 (X) -2 = 0 is TRUE -0.001 (+) -Inf = -0.001 is TRUE 0 (X) -Inf = -Inf is TRUE 1.5 (+) -1 = 1.5 is TRUE -0.5 (X) 0 = -0.5 is TRUE 5 ^ 7: 35.0 5 (X) ( 8 (+) 7 ) = 5 (X) 8 (+) 5 (X) 7 is TRUE
C++
<lang cpp>#include <iostream>
- include <optional>
using namespace std;
class TropicalAlgebra {
// use an unset std::optional to represent -infinity optional<double> m_value;
public:
friend std::ostream& operator<<(std::ostream&, const TropicalAlgebra&); friend TropicalAlgebra pow(const TropicalAlgebra& base, unsigned int exponent) noexcept; // create a point that is initialized to -infinity TropicalAlgebra() = default;
// construct with a value explicit TropicalAlgebra(double value) noexcept : m_value{value} {}
// add a value to this one ( p+=q ). it is common to also overload // the += operator when overloading + TropicalAlgebra& operator+=(const TropicalAlgebra& rhs) noexcept { if(!m_value) { // this point is -infinity so the other point is max *this = rhs; } else if (!rhs.m_value) { // since rhs is -infinity this point is max } else { // both values are valid, find the max *m_value = max(*rhs.m_value, *m_value); }
return *this; } // multiply this value by another (p *= q) TropicalAlgebra& operator*=(const TropicalAlgebra& rhs) noexcept { if(!m_value) { // since this value is -infinity this point does not need to be // modified } else if (!rhs.m_value) { // the other point is -infinity, make this -infinity too *this = rhs; } else { *m_value += *rhs.m_value; }
return *this; }
};
// add values (p + q) inline TropicalAlgebra operator+(TropicalAlgebra lhs, const TropicalAlgebra& rhs) noexcept {
// implemented using the += operator defined above lhs += rhs; return lhs;
}
// multiply values (p * q) inline TropicalAlgebra operator*(TropicalAlgebra lhs, const TropicalAlgebra& rhs) noexcept {
lhs *= rhs; return lhs;
}
// pow is the idomatic way for exponentiation in C++ inline TropicalAlgebra pow(const TropicalAlgebra& base, unsigned int exponent) noexcept {
auto result = base; for(unsigned int i = 1; i < exponent; i++) { // compute the power by successive multiplication result *= base; } return result;
}
// print the point ostream& operator<<(ostream& os, const TropicalAlgebra& pt) {
if(!pt.m_value) cout << "-Inf\n"; else cout << *pt.m_value << "\n"; return os;
}
int main(void) {
const TropicalAlgebra a(-2); const TropicalAlgebra b(-1); const TropicalAlgebra c(-0.5); const TropicalAlgebra d(-0.001); const TropicalAlgebra e(0); const TropicalAlgebra h(1.5); const TropicalAlgebra i(2); const TropicalAlgebra j(5); const TropicalAlgebra k(7); const TropicalAlgebra l(8); const TropicalAlgebra m; // -Inf cout << "2 * -2 == " << i * a; cout << "-0.001 + -Inf == " << d + m; cout << "0 * -Inf == " << e * m; cout << "1.5 + -1 == " << h + b; cout << "-0.5 * 0 == " << c * e; cout << "pow(5, 7) == " << pow(j, 7); cout << "5 * (8 + 7)) == " << j * (l + k); cout << "5 * 8 + 5 * 7 == " << 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 pow(5, 7) == 35 5 * (8 + 7)) == 13 5 * 8 + 5 * 7 == 13
Factor
<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
FreeBASIC
Using preprocessor macros. <lang freebasic>#define Inf 9223372036854775807
- define tropicalAdd(x,y) iif((x > y), (x), (y))
- define tropicalMul(x,y) (x + y)
- define tropicalExp(x,y) iif(int(y) > 0, (x * y), 0)
Print "tropicalMul(2,-2) = "; tropicalMul(2,-2) Print "tropicalAdd(-0.001,-Inf) = "; tropicalAdd(-0.001,-Inf) Print "tropicalMul(0,-Inf) = "; tropicalMul(0,-Inf) Print "tropicalAdd(1.5,-1) = "; tropicalAdd(1.5,-1) Print "tropicalMul(-0.5,0) = "; tropicalMul(-0.5,0) Print "tropicalExp(5,7) = "; tropicalExp(5,7) Print "tropicalMul(5,tropicalAdd(8,7)) = "; tropicalMul(5,tropicalAdd(8,7)) Print "tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = "; tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) Print "tropicalMul(5,tropicalAdd(8,7)) = tropicalAdd(tropicalMul(5,8),tropicalMul(5,7)) = "; _ CBool(tropicalMul(5,tropicalAdd(8,7)) = tropicalAdd(tropicalMul(5,8),tropicalMul(5,7))) Sleep</lang>
Go
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
Haskell
Looks like the Haskell pretty printer thinks the single quote in 'Maxima begins a character constant. <lang haskell>{-# LANGUAGE DataKinds, DerivingVia, FlexibleInstances, StandaloneDeriving #-}
import Prelude hiding ((^)) import Data.Monoid (Sum(Sum)) import Data.Number.CReal (CReal) import Data.Semiring (Semiring, (^), plus, times) import Data.Semiring.Tropical (Tropical(..), Extrema(Maxima))
-- Create our max-plus semiring over the constructive reals (CReal), using the -- Tropical type from the semirings package. (We'll put all the boilerplate -- code after the main function.) -- -- 'Maxima indicates that our semiring is a max-plus semiring, where the plus -- function is maximum, the times function is addition, and the Infinity -- constructor is treated as -∞.
newtype MaxPlus = MaxPlus (Tropical 'Maxima CReal)
-- Symbolic aliases to satisfy the problem requirements.
(⊕), (⊗) :: MaxPlus -> MaxPlus -> MaxPlus (⊕) = plus (⊗) = times
infixl 6 ⊕ infixl 7 ⊗
(↑) :: Integral a => MaxPlus -> a -> MaxPlus (↑) = (^)
infixr 8 ↑
main :: IO () main = do
-- Description Equation Expected Value test "2 ⊗ (-2) == 0" (2 ⊗ (-2)) 0 test "-0.001 ⊕ -Inf == -0.001" (-0.001 ⊕ MaxPlus Infinity) (-0.001) test "0 ⊗ -Inf == -Inf" (0 ⊗ MaxPlus Infinity) (MaxPlus Infinity) test "1.5 ⊕ -1 == 1.5" (1.5 ⊕ (-1)) 1.5 test "-0.5 ⊗ 0 == -0.5" ((-0.5) ⊗ 0) (-0.5) test "5 ↑ 7 == 35" (5 ↑ 7) 35 test "5 ⊗ (8 ⊕ 7) == 13" (5 ⊗ (8 ⊕ 7)) 13 test "5 ⊗ 8 ⊕ 5 ⊗ 7 == 13" (5 ⊗ 8 ⊕ 5 ⊗ 7) 13
-- Boilerplate, utility functions, etc.
-- Bootstrap our way to having MaxPlus be a Semiring instance. Also, derive -- Eq and Ord instances. deriving via (Sum CReal) instance Semigroup CReal deriving via (Sum CReal) instance Monoid CReal deriving via Tropical 'Maxima CReal instance Semiring MaxPlus deriving via Tropical 'Maxima CReal instance Eq MaxPlus deriving via Tropical 'Maxima CReal instance Ord MaxPlus
-- Create a Num instance for MaxPlus mostly so that we can use fromInteger and -- negate. This lets us treat the numeric literal -2, for example, as a value -- in our semiring. instance Num MaxPlus where
(+) = plus (*) = times abs = opError "absolute value" signum (MaxPlus Infinity) = -1 signum x = wrap . signum . unwrap $ x fromInteger = wrap . fromInteger negate (MaxPlus Infinity) = opError "negation of -Inf" negate x = wrap . negate . unwrap $ x
-- Similar to Num, this will let us treat numeric literals, like 0.001, as -- MaxPlus values. instance Fractional MaxPlus where
fromRational = wrap . fromRational recip _ = opError "reciprocal"
instance Show MaxPlus where
show (MaxPlus Infinity) = "-Inf" show x = show . unwrap $ x
-- Test two expressions for equality. test :: String -> MaxPlus -> MaxPlus -> IO () test s actual expected = do
putStr $ "Expecting " ++ s ++ ". Got " ++ show actual ++ " " putStrLn $ if actual == expected then "✔" else "✘"
-- Utility functions.
wrap :: CReal -> MaxPlus wrap = MaxPlus . Tropical
unwrap :: MaxPlus -> CReal unwrap (MaxPlus (Tropical x)) = x unwrap (MaxPlus Infinity) = error "can't convert -Inf to a CReal"
opError :: String -> a opError op = error $ op ++ " is not defined on a max-plus semiring"</lang>
- Output:
Expecting 2 ⊗ (-2) == 0. Got 0.0 ✔ Expecting -0.001 ⊕ -Inf == -0.001. Got -0.001 ✔ Expecting 0 ⊗ -Inf == -Inf. Got -Inf ✔ Expecting 1.5 ⊕ -1 == 1.5. Got 1.5 ✔ Expecting -0.5 ⊗ 0 == -0.5. Got -0.5 ✔ Expecting 5 ↑ 7 == 35. Got 35.0 ✔ Expecting 5 ⊗ (8 ⊕ 7) == 13. Got 13.0 ✔ Expecting 5 ⊗ 8 ⊕ 5 ⊗ 7 == 13. Got 13.0 ✔
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
Nim
We could define ⊕ and ⊗ as procedures but would have to use ⊕(a, b)
and ⊗(a, b)
instead of the more natural a ⊕ b
and a ⊗ b
. We preferred to define a type MaxTropical distinct of float. In Nim, it is possible to borrow operations from the parent type, which we did for operator `<=` (required by the standard max function), operator `==` needed for comparison and for function `$` to convert a value to its string representation. The ⊕ operator is then defined by overloading of the `+` operator and the ⊗ operator by overloading of the `*` operator.
We also defined the -Inf value as a constant, MinusInfinity.
<lang Nim>import strformat
type MaxTropical = distinct float
const MinusInfinity = MaxTropical NegInf
- Borrowed functions.
func `<=`(a, b: MaxTropical): bool {.borrow.} # required by "max". func `==`(a, b: MaxTropical): bool {.borrow} func `$`(a: MaxTropical): string {.borrow.}
- ⊕ operator.
func `+`(a, b: MaxTropical): MaxTropical = max(a, b)
- ⊗ operator.
func `*`(a, b: MaxTropical): MaxTropical = MaxTropical float(a) + float(b)
- ⊗= operator, used here for exponentiation.
func `*=`(a: var MaxTropical; b: MaxTropical) =
float(a) += float(b)
- ↑ operator (this can be seen as an overloading of the ^ operator from math module).
func `^`(a: MaxTropical; b: Positive): MaxTropical =
case b of 1: return a of 2: return a * a of 3: return a * a * a else: result = a for n in 2..b: result *= a
echo &"2 ⊗ -2 = {MaxTropical(2) * MaxTropical(-2)}"
echo &"-0.001 ⊕ -Inf = {MaxTropical(-0.001) + MinusInfinity}"
echo &"0 ⊗ -Inf = {MaxTropical(0) * MinusInfinity}"
echo &"1.5 ⊕ -1 = {MaxTropical(1.5) + MaxTropical(-1)}"
echo &"-0.5 ⊗ 0 = {MaxTropical(-0.5) * MaxTropical(0)}"
echo &"5↑7 = {MaxTropical(5)^7}"
echo()
let x = MaxTropical(5) * (MaxTropical(8) + MaxTropical(7))
let y = MaxTropical(5) * MaxTropical(8) + MaxTropical(5) * MaxTropical(7)
echo &"5 ⊗ (8 ⊕ 7) = {x}"
echo &"5 ⊗ 8 ⊕ 5 ⊗ 7 = {y}"
echo &"So 5 ⊗ (8 ⊕ 7) equals 5 ⊗ 8 ⊕ 5 ⊗ 7 is {x == y}."</lang>
- Output:
2 ⊗ -2 = 0.0 -0.001 ⊕ -Inf = -0.001 0 ⊗ -Inf = -inf 1.5 ⊕ -1 = 1.5 -0.5 ⊗ 0 = -0.5 5↑7 = 35.0 5 ⊗ (8 ⊕ 7) = 13.0 5 ⊗ 8 ⊕ 5 ⊗ 7 = 13.0 So 5 ⊗ (8 ⊕ 7) equals 5 ⊗ 8 ⊕ 5 ⊗ 7 is 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
Raku
No need to overload, define our own operators with whatever precedence level we want. Here we're setting precedence equivalent to existing operators.
<lang perl6>sub infix:<⊕> (Real $a, Real $b) is equiv(&[+]) { $a max $b } sub infix:<⊗> (Real $a, Real $b) is equiv(&[×]) { $a + $b } sub infix:<↑> (Real $a, Int $b where * ≥ 0) is equiv(&[**]) { [⊗] $a xx $b }
use Test;
is-deeply( 2 ⊗ -2, 0, '2 ⊗ -2 == 0' ); is-deeply( -0.001 ⊕ -Inf, -0.001, '-0.001 ⊕ -Inf == -0.001' ); is-deeply( 0 ⊗ -Inf, -Inf, '0 ⊗ -Inf == -Inf' ); is-deeply( 1.5 ⊕ -1, 1.5, '1.5 ⊕ -1 == 1.5' ); is-deeply( -0.5 ⊗ 0, -0.5, '-0.5 ⊗ 0 == -0.5' ); is-deeply( 5 ↑ 7, 35, '5 ↑ 7 == 35' ); is-deeply( 5 ⊗ (8 ⊕ 7), 5 ⊗ 8 ⊕ 5 ⊗ 7, '5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7'); is-deeply( 5 ↑ 7 ⊕ 6 ↑ 6, 36, '5 ↑ 7 ⊕ 6 ↑ 6 == 36');</lang>
- Output:
ok 1 - 2 ⊗ -2 == 0 ok 2 - -0.001 ⊕ -Inf == -0.001 ok 3 - 0 ⊗ -Inf == -Inf ok 4 - 1.5 ⊕ -1 == 1.5 ok 5 - -0.5 ⊗ 0 == -0.5 ok 6 - 5 ↑ 7 == 35 ok 7 - 5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 ok 8 - 5 ↑ 7 ⊕ 6 ↑ 6 == 36
REXX
REXX doesn't support operator overloading, so functions are needed to be used instead. <lang rexx>/*REXX pgm demonstrates max tropical semi─ring with overloading: topAdd, topMul, topExp.*/ call negInf; @x= '(x)'; @a= '(+)'; @h= '(^)'; @e= 'expression'; @c= 'comparison' numeric digits 1000 /*be able to handle negative infinity. */ x= 2 ; y= -2 ; say is(@x) LS(x) RS(y) $Mul(x,y) x= -0.001 ; y= nInf ; say is(@a) LS(x) RS(y) $Add(x,y) x= 0 ; y= nInf ; say is(@x) LS(x) RS(y) $Mul(x,y) x= 1.5 ; y= -1 ; say is(@a) LS(x) RS(y) $Add(x,y) x= -0.5 ; y= 0 ; say is(@x) LS(x) RS(y) $Mul(x,y) x= 5 ; y= 7 ; say is(@h) LS(x) RS(y) $Exp(x,y) x= 5 ; y= $Add(8,7); say is(@e) LS(x @x) RS(@a"(8,7)") $Mul(x,y) x= $Mul(5,8); y= $Mul(5,7); say is(@e) LS(@x"(5,8)" @a) RS(@x'(5,7)') $Add(x,y) x= 5 ; y= $Add(8,7); blanks= left(, 26) a= $Mul(5,8); b= $Mul(5,7); say is(@c) LS(x @x) @a"(8,7)" ' compared to'
say blanks LS(@x"(5,8)") RS(@a @x'(5,7)') , $ToF( $Mul(x,y) == $Add(a,b) )
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ ABnInf: if b== then b=a; __= negInf(); _= nInf(); return a==__ | a==_ | b==__ | b==_ negInf: negInf= '-1e' || (digits()-1); call nInf; return negInf /*simulate a -∞ value.*/ nInf: nInf= '-∞'; return nInf /*return the "diagraph": -∞ */ notNum: call sayErr "argument isn't numeric or minus infinity:", arg(1) /*tell error.*/ is: return 'max tropical' center(arg(1), 10) "of" /*center what is to be shown*/ LS: return right( arg(1), 12) ' with ' /*pad left─side of equation*/ RS: return left( arg(1), 12) ' ───► ' /* " right─side " " */ sayErr: say; say '***error***' arg(1) arg(2); say; exit 13 /*issue error message──►term*/ $Add: procedure; parse arg a,b; return max(isRing(a),isRing(b)) /*simulate max add ƒ */ $ToF: procedure; parse arg ?; return word('false true',1+?) /*return true │ false.*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ $Exp: procedure; parse arg a,b; if ABnInf() then return _ /*return the "diagraph": -∞ */
return isRing(a) * isRing(b) /*simulate exponentiation ƒ */
/*──────────────────────────────────────────────────────────────────────────────────────*/ $Mul: procedure; parse arg a,b; if ABnInf() then return _ /*return the "diagraph": -∞ */
return isRing(a) + isRing(b) /*simulate multiplication ƒ */
/*──────────────────────────────────────────────────────────────────────────────────────*/ isNum: procedure; parse arg a,b; if ABnInf() then a= negInf() /*replace A with -∞? */
return datatype(a, 'Num') /*Arg numeric? Return 1 or 0*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ isRing: procedure; parse arg a,b; if ABnInf() then return negInf /*return -∞ */
if isNum(a) | a==negInf() then return a; call notNum a /*show error.*/</lang>
- output when using the internal default input:
max tropical (x) of 2 with -2 ───► 0 max tropical (+) of -0.001 with -∞ ───► -0.001 max tropical (x) of 0 with -∞ ───► -∞ max tropical (+) of 1.5 with -1 ───► 1.5 max tropical (x) of -0.5 with 0 ───► -0.5 max tropical (^) of 5 with 7 ───► 35 max tropical expression of 5 (x) with (+)(8,7) ───► 13 max tropical expression of (x)(5,8) (+) with (x)(5,7) ───► 13 max tropical comparison of 5 (x) with (+)(8,7) compared to (x)(5,8) with (+) (x)(5,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