Tropical algebra overloading
You are encouraged to solve this task according to the task description, using any language you may know.
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.
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- 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#
using System;
public class Program
{
public static void Main(string[] args)
{
var a = new Tropical(-2);
var b = new Tropical(-1);
var c = new Tropical(-0.5);
var d = new Tropical(-0.001);
var e = new Tropical(0);
var f = new Tropical(1.5);
var g = new Tropical(2);
var h = new Tropical(5);
var i = new Tropical(7);
var j = new Tropical(8);
var k = new Tropical(); // Represents -Inf
Console.WriteLine("2 x -2 = " + g.Multiply(a));
Console.WriteLine("-0.001 + -Inf = " + d.Add(k));
Console.WriteLine("0 x -Inf = " + e.Multiply(k));
Console.WriteLine("1.5 + -1 = " + f.Add(b));
Console.WriteLine("-0.5 x 0 = " + c.Multiply(e));
Console.WriteLine();
Console.WriteLine("5^7 = " + h.Power(7));
Console.WriteLine();
Console.WriteLine("5 * ( 8 + 7 ) = " + h.Multiply(j.Add(i)));
Console.WriteLine("5 * 8 + 5 * 7 = " + h.Multiply(j).Add(h.Multiply(i)));
}
}
public class Tropical
{
private double? number;
public Tropical(double number)
{
this.number = number;
}
public Tropical()
{
this.number = null; // Represents -Inf
}
public override string ToString()
{
return number.HasValue ? ((int)number.Value).ToString() : "-Inf";
}
public Tropical Add(Tropical other)
{
if (!number.HasValue) return other;
if (!other.number.HasValue) return this;
return number > other.number ? this : other;
}
public Tropical Multiply(Tropical other)
{
if (number.HasValue && other.number.HasValue)
{
return new Tropical(number.Value + other.number.Value);
}
return new Tropical();
}
public Tropical Power(int exponent)
{
if (exponent <= 0)
{
throw new ArgumentException("Power must be positive", nameof(exponent));
}
Tropical result = this;
for (int i = 1; i < exponent; i++)
{
result = result.Multiply(this);
}
return result;
}
}
- Output:
2 x -2 = 0 -0.001 + -Inf = 0 0 x -Inf = -Inf 1.5 + -1 = 1 -0.5 x 0 = 0 5^7 = 35 5 * ( 8 + 7 ) = 13 5 * 8 + 5 * 7 = 13
C++
#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;
}
- 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
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
- 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.
#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
Go
Go doesn't support operator overloading so we need to use functions instead.
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))
}
- 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.
{-# 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"
- 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 ✔
Java
import java.util.Optional;
public final class TropicalAlgebra {
public static void main(String[] aArgs) {
final Tropical a = new Tropical(-2);
final Tropical b = new Tropical(-1);
final Tropical c = new Tropical(-0.5);
final Tropical d = new Tropical(-0.001);
final Tropical e = new Tropical(0);
final Tropical f = new Tropical(1.5);
final Tropical g = new Tropical(2);
final Tropical h = new Tropical(5);
final Tropical i = new Tropical(7);
final Tropical j = new Tropical(8);
final Tropical k = new Tropical();
System.out.println("2 x -2 = " + g.multiply(a));
System.out.println("-0.001 + -Inf = " + d.add(k));
System.out.println("0 x -Inf = " + e.multiply(k));
System.out.println("1.5 + -1 = " + f.add(b));
System.out.println("-0.5 x 0 = " + c.multiply(e));
System.out.println();
System.out.println("5^7 = " + h.power(7));
System.out.println();
System.out.println("5 * ( 8 + 7 ) = " + h.multiply(j.add(i)));
System.out.println("5 * 8 + 5 * 7 = " + h.multiply(j).add(h.multiply(i)));
}
}
final class Tropical {
public Tropical(Number aNumber) {
if ( aNumber == null ) {
throw new IllegalArgumentException("Number cannot be null");
}
optional = Optional.of(aNumber);
}
public Tropical() {
optional = Optional.empty();
}
@Override
public String toString() {
if ( optional.isEmpty() ) {
return "-Inf";
}
String value = String.valueOf(optional.get());
final int index = value.indexOf(".");
if ( index >= 0 ) {
value = value.substring(0, index);
}
return value;
}
public Tropical add(Tropical aOther) {
if ( aOther.optional.isEmpty() ) {
return this;
}
if ( optional.isEmpty() ) {
return aOther;
}
if ( optional.get().doubleValue() > aOther.optional.get().doubleValue() ) {
return this;
}
return aOther;
}
public Tropical multiply(Tropical aOther) {
if ( optional.isPresent() && aOther.optional.isPresent() ) {
double result = optional.get().doubleValue() + aOther.optional.get().doubleValue();
return new Tropical(result);
}
return new Tropical();
}
public Tropical power(int aExponent) {
if ( aExponent <= 0 ) {
throw new IllegalArgumentException("Power must be positive");
}
Tropical result = this;;
for ( int i = 1; i < aExponent; i++ ) {
result = result.multiply(this);
}
return result;
}
private Optional<Number> optional;
}
- Output:
2 x -2 = 0 -0.001 + -Inf = -0 0 x -Inf = -Inf 1.5 + -1 = 1 -0.5 x 0 = -0 5^7 = 35 5 * ( 8 + 7 ) = 13 5 * 8 + 5 * 7 = 13
jq
Also work with gojq subject to the qualifications described below.
In this entry, jq's support for "::" in definitions is used. This feature is not supported by gojq, so to adapt the following for gojq, one could either modify the names, or place the definitions in a module named `Tropical` and delete the "Tropical::" prefix within the module itself.
Since the jq values for plus and minus infinity are `infinite` and `-infinite` respectively, no special constructor for Tropical numbers is needed.
Note that in the following, no checks for the validity of inputs are included.
# ⊕ operator
def Tropical::add($other):
[., $other] | max;
# ⊗ operator
def Tropical::mul($other):
. + $other;
# Tropical exponentiation
def Tropical::exp($e):
if ($e|type) == "number" and ($e | . == floor)
then if ($e == 1) then .
else . as $in
| reduce range (2;1+$e) as $i (.; Tropical::mul($in))
end
else "Tropical::exp(\($e)): argument must be a positive integer." | error
end ;
# pretty print a number as a Tropical number
def pp:
if isinfinite then if . > 0 then "infinity" else "-infinity" end
else .
end;
def data: [
[2, -2, "⊗"],
[-0.001, -infinite, "⊕"],
[0, -infinite, "⊗"],
[1.5, -1, "⊕"],
[-0.5, 0, "⊗"]
];
def task1:
data[] as [$a, $b, $op]
| if $op == "⊕"
then "\($a|pp) ⊕ \($b|pp) = \($a | Tropical::add($b) | pp)"
else
"\($a|pp) ⊗ \($b|pp) = \($a | Tropical::mul($b) | pp)"
end;
def task2:
5 as $c
| "\($c|pp) ^ 7 = \($c | Tropical::exp(7) | pp)";
def task3:
5 as $c
| 8 as $d
| 7 as $e
| ($c | Tropical::mul($d) | Tropical::add($e)) as $f
| ($c | Tropical::mul($d) | Tropical::add( $c | Tropical::mul($e))) as $g
| "\($c) ⊗ (\($d) ⊕ \($e)) = \($f | pp)",
"\($c) ⊗ \($d) ⊕ \($c) ⊗ \($e) = \($g | pp)",
"\($c) ⊗ (\($d) ⊕ \($e)) == \($c) ⊗ \($d) ⊕ \($c) ⊗ \($e) is \($f == $g)" ;
task1, task2, task3- Output:
See e.g. Wren.
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
- 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.
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}."
- 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
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)
- 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.
"%+%"<- 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")
- 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.
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');
- 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.
/*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.*/
- 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
RPL
RPL does not support operator overloading so we need to use functions instead. As all stack-driven languages, RPL requires the user to deal with operator precedence.
MAXR EVAL 'Inf' STO ≪ 1 3 START ROT EVAL NEXT IF DUP ABS Inf == THEN SIGN 'Inf' * END ≫ ‘TropOp’ STO ≪ ≪ MAX ≫ TropOp ≫ ‘TPLUS’ STO ≪ ≪ + ≫ TropOp ≫ ‘TMULT’ STO ≪ ≪ * ≫ TropOp ≫ ‘TPOWR’ STO
2 -2 TMULT -0.001 -Inf TPLUS 0 -Inf TMULT 1.5 -1 TPLUS 0.5 0 TMULT 5 7 TPOWR 8 7 TPLUS 5 TMULT 5 8 TMULT 5 7 TMULT TPLUS
- Output:
8: 0 7: -0.001 6: '-Inf' 5: 1.5 4: -0.5 3: 35 2: 13 1: 13
V (Vlang)
Vlang doesn't support operator overloading so we need to use functions instead.
import math
const (
minus_inf = math.inf(-1)
)
struct MaxTropical { r f64 }
fn new_max_tropical(r f64) ?MaxTropical {
if math.is_inf(r, 1) || math.is_nan(r) {
return error("Argument must be a real number or negative infinity.")
}
return MaxTropical{r}
}
fn (t MaxTropical) eq(other MaxTropical) bool {
return t.r == other.r
}
// equivalent to ⊕ operator
fn (t MaxTropical) add(other MaxTropical) ?MaxTropical {
if t.r == minus_inf {
return other
}
if other.r == minus_inf {
return t
}
return new_max_tropical(math.max(t.r, other.r))
}
// equivalent to ⊗ operator
fn (t MaxTropical) mul(other MaxTropical) ?MaxTropical {
if t.r == 0 {
return other
}
if other.r == 0 {
return t
}
return new_max_tropical(t.r + other.r)
}
// exponentiation fntion
fn (t MaxTropical) pow(e int) ?MaxTropical {
if e < 1 {
return error("Exponent must be a positive integer.")
}
if e == 1 {
return t
}
mut p := t
for i := 2; i <= e; i++ {
p = p.mul(t)?
}
return p
}
fn (t MaxTropical) str() string {
return '${t.r}'
}
fn main() {
// 0 denotes ⊕ and 1 denotes ⊗
data := [
[2.0, -2, 1],
[-0.001, minus_inf, 0],
[0.0, minus_inf, 1],
[1.5, -1, 0],
[-0.5, 0, 1],
]
for d in data {
a := new_max_tropical(d[0])?
b := new_max_tropical(d[1])?
c := a.add(b)?
m := a.mul(b)?
if d[2] == 0 {
println("$a ⊕ $b = $c")
} else {
println("$a ⊗ $b = $m")
}
}
c := new_max_tropical(5)?
println("$c ^ 7 = ${c.pow(7)}")
d := new_max_tropical(8)?
e := new_max_tropical(7)?
f := c.mul(d.add(e)?)?
g := c.mul(d)?.add(c.mul(e)?)?
println("$c ⊗ ($d ⊕ $e) = $f")
println("$c ⊗ $d ⊕ $c ⊗ $e = $g")
println("$c ⊗ ($d ⊕ $e) == $c ⊗ $d ⊕ $c ⊗ $e is ${f.eq(g)}")
}- Output:
2 ⊗ -2 = 0 -0.001 ⊕ -inf = -0.001 0 ⊗ -inf = -inf 1.5 ⊕ -1 = 1.5 -0.5 ⊗ 0 = -0.5 5 ^ 7 = Option(35) 5 ⊗ (8 ⊕ 7) = 13 5 ⊗ 8 ⊕ 5 ⊗ 7 = 13 5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 is true
Wren
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)")
- 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