{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE NoRebindableSyntax #-}

-- | Concrete semiring carriers useful for demonstrating
-- 'NumHask.Algebra.Ring.StarSemiring'.
--
-- These four carriers are the classic examples of the closed-semiring /
-- algebraic-path-problem literature. They are still, fifty years on, the
-- canonical trio plus the probabilistic addition:
--
-- * Boolean semiring — reachability / transitive closure (Warshall 1962).
-- * Min-plus semiring — shortest paths (Floyd 1962, Roy 1959, Warshall 1962).
-- * Field semiring — matrix inversion via the Neumann series.
-- * Viterbi semiring — maximum-probability paths.
--
-- The unification of path problems over semirings was introduced by
-- Aho, Hopcroft and Ullman in /The Design and Analysis of Computer
-- Algorithms/ (1974) and elaborated by Tarjan in
-- "A Unified Approach to Path Problems" (JACM, 1981).
-- A modern categorical treatment is given by Höfner and Möller in
-- "Dijkstra, Floyd and Warshall Meet Kleene" (2012).
module NumHask.Free.Carriers
  ( -- * Boolean semiring
    Warshall (..),

    -- * Tropical semiring
    MinPlus (..),

    -- * Field semiring
    FieldStar (..),

    -- * Viterbi semiring
    Viterbi (..),
  )
where

import NumHask.Algebra.Additive qualified as NHA
import NumHask.Algebra.Group (Idempotent, Magma (..))
import NumHask.Algebra.Lattice qualified as NHAL
import NumHask.Algebra.Multiplicative qualified as NHM
import NumHask.Algebra.Ring qualified as NHR
import Prelude (Bool, Double, Eq, Fractional, Num, Ord, Show)
import Prelude qualified as P

-- $setup
--
-- >>> :m -Prelude
-- >>> :set -XRebindableSyntax
-- >>> import NumHask.Prelude
-- >>> import NumHask.Free.Carriers

-- | Boolean semiring for Warshall's transitive closure.
--
-- 'plus' is '||', 'times' is '&&', 'star' is constantly 'True'.
--
-- >>> Warshall True + Warshall False
-- Warshall True
newtype Warshall = Warshall Bool
  deriving (Warshall -> Warshall -> Bool
(Warshall -> Warshall -> Bool)
-> (Warshall -> Warshall -> Bool) -> Eq Warshall
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Warshall -> Warshall -> Bool
== :: Warshall -> Warshall -> Bool
$c/= :: Warshall -> Warshall -> Bool
/= :: Warshall -> Warshall -> Bool
Eq, Eq Warshall
Eq Warshall =>
(Warshall -> Warshall -> Ordering)
-> (Warshall -> Warshall -> Bool)
-> (Warshall -> Warshall -> Bool)
-> (Warshall -> Warshall -> Bool)
-> (Warshall -> Warshall -> Bool)
-> (Warshall -> Warshall -> Warshall)
-> (Warshall -> Warshall -> Warshall)
-> Ord Warshall
Warshall -> Warshall -> Bool
Warshall -> Warshall -> Ordering
Warshall -> Warshall -> Warshall
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Warshall -> Warshall -> Ordering
compare :: Warshall -> Warshall -> Ordering
$c< :: Warshall -> Warshall -> Bool
< :: Warshall -> Warshall -> Bool
$c<= :: Warshall -> Warshall -> Bool
<= :: Warshall -> Warshall -> Bool
$c> :: Warshall -> Warshall -> Bool
> :: Warshall -> Warshall -> Bool
$c>= :: Warshall -> Warshall -> Bool
>= :: Warshall -> Warshall -> Bool
$cmax :: Warshall -> Warshall -> Warshall
max :: Warshall -> Warshall -> Warshall
$cmin :: Warshall -> Warshall -> Warshall
min :: Warshall -> Warshall -> Warshall
Ord, Int -> Warshall -> ShowS
[Warshall] -> ShowS
Warshall -> String
(Int -> Warshall -> ShowS)
-> (Warshall -> String) -> ([Warshall] -> ShowS) -> Show Warshall
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Warshall -> ShowS
showsPrec :: Int -> Warshall -> ShowS
$cshow :: Warshall -> String
show :: Warshall -> String
$cshowList :: [Warshall] -> ShowS
showList :: [Warshall] -> ShowS
Show)

instance NHM.Multiplicative Warshall where
  one :: Warshall
one = Bool -> Warshall
Warshall Bool
P.True
  Warshall Bool
a * :: Warshall -> Warshall -> Warshall
* Warshall Bool
b = Bool -> Warshall
Warshall (Bool
a Bool -> Bool -> Bool
P.&& Bool
b)

instance NHA.Additive Warshall where
  zero :: Warshall
zero = Bool -> Warshall
Warshall Bool
P.False
  Warshall Bool
a + :: Warshall -> Warshall -> Warshall
+ Warshall Bool
b = Bool -> Warshall
Warshall (Bool
a Bool -> Bool -> Bool
P.|| Bool
b)

instance Magma Warshall where
  Warshall
a ⊕ :: Warshall -> Warshall -> Warshall
⊕ Warshall
b = Warshall
a Warshall -> Warshall -> Warshall
forall a. Additive a => a -> a -> a
NHA.+ Warshall
b

instance Idempotent Warshall

-- | Boolean star is constantly true.
--
-- >>> star (Warshall False :: Warshall)
-- Warshall True
instance NHR.StarSemiring Warshall where
  star :: Warshall -> Warshall
star Warshall
_ = Bool -> Warshall
Warshall Bool
P.True

instance NHR.KleeneAlgebra Warshall

-- | Boolean join-semilattice structure: join is '||', bottom is 'False'.
instance NHAL.JoinSemiLattice Warshall where
  Warshall Bool
a \/ :: Warshall -> Warshall -> Warshall
\/ Warshall Bool
b = Bool -> Warshall
Warshall (Bool
a Bool -> Bool -> Bool
P.|| Bool
b)

instance NHAL.LowerBounded Warshall where
  bottom :: Warshall
bottom = Bool -> Warshall
Warshall Bool
P.False

instance NHAL.CompleteJoinSemiLattice Warshall

-- | Tropical (min-plus) semiring for Floyd–Warshall shortest paths.
--
-- Addition is 'min', multiplication is ordinary addition, the additive unit
-- is positive infinity, and the multiplicative unit is zero.
--
-- >>> MinPlus 3 + MinPlus 2 :: MinPlus Double
-- MinPlus {getMinPlus = 2.0}
--
-- >>> MinPlus 3 * MinPlus 2 :: MinPlus Double
-- MinPlus {getMinPlus = 5.0}
newtype MinPlus a = MinPlus
  { forall a. MinPlus a -> a
getMinPlus :: a
  }
  deriving (MinPlus a -> MinPlus a -> Bool
(MinPlus a -> MinPlus a -> Bool)
-> (MinPlus a -> MinPlus a -> Bool) -> Eq (MinPlus a)
forall a. Eq a => MinPlus a -> MinPlus a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => MinPlus a -> MinPlus a -> Bool
== :: MinPlus a -> MinPlus a -> Bool
$c/= :: forall a. Eq a => MinPlus a -> MinPlus a -> Bool
/= :: MinPlus a -> MinPlus a -> Bool
Eq, Eq (MinPlus a)
Eq (MinPlus a) =>
(MinPlus a -> MinPlus a -> Ordering)
-> (MinPlus a -> MinPlus a -> Bool)
-> (MinPlus a -> MinPlus a -> Bool)
-> (MinPlus a -> MinPlus a -> Bool)
-> (MinPlus a -> MinPlus a -> Bool)
-> (MinPlus a -> MinPlus a -> MinPlus a)
-> (MinPlus a -> MinPlus a -> MinPlus a)
-> Ord (MinPlus a)
MinPlus a -> MinPlus a -> Bool
MinPlus a -> MinPlus a -> Ordering
MinPlus a -> MinPlus a -> MinPlus a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (MinPlus a)
forall a. Ord a => MinPlus a -> MinPlus a -> Bool
forall a. Ord a => MinPlus a -> MinPlus a -> Ordering
forall a. Ord a => MinPlus a -> MinPlus a -> MinPlus a
$ccompare :: forall a. Ord a => MinPlus a -> MinPlus a -> Ordering
compare :: MinPlus a -> MinPlus a -> Ordering
$c< :: forall a. Ord a => MinPlus a -> MinPlus a -> Bool
< :: MinPlus a -> MinPlus a -> Bool
$c<= :: forall a. Ord a => MinPlus a -> MinPlus a -> Bool
<= :: MinPlus a -> MinPlus a -> Bool
$c> :: forall a. Ord a => MinPlus a -> MinPlus a -> Bool
> :: MinPlus a -> MinPlus a -> Bool
$c>= :: forall a. Ord a => MinPlus a -> MinPlus a -> Bool
>= :: MinPlus a -> MinPlus a -> Bool
$cmax :: forall a. Ord a => MinPlus a -> MinPlus a -> MinPlus a
max :: MinPlus a -> MinPlus a -> MinPlus a
$cmin :: forall a. Ord a => MinPlus a -> MinPlus a -> MinPlus a
min :: MinPlus a -> MinPlus a -> MinPlus a
Ord, Int -> MinPlus a -> ShowS
[MinPlus a] -> ShowS
MinPlus a -> String
(Int -> MinPlus a -> ShowS)
-> (MinPlus a -> String)
-> ([MinPlus a] -> ShowS)
-> Show (MinPlus a)
forall a. Show a => Int -> MinPlus a -> ShowS
forall a. Show a => [MinPlus a] -> ShowS
forall a. Show a => MinPlus a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> MinPlus a -> ShowS
showsPrec :: Int -> MinPlus a -> ShowS
$cshow :: forall a. Show a => MinPlus a -> String
show :: MinPlus a -> String
$cshowList :: forall a. Show a => [MinPlus a] -> ShowS
showList :: [MinPlus a] -> ShowS
Show)

instance NHM.Multiplicative (MinPlus Double) where
  MinPlus Double
a * :: MinPlus Double -> MinPlus Double -> MinPlus Double
* MinPlus Double
b = Double -> MinPlus Double
forall a. a -> MinPlus a
MinPlus (Double
a Double -> Double -> Double
forall a. Num a => a -> a -> a
P.+ Double
b)
  one :: MinPlus Double
one = Double -> MinPlus Double
forall a. a -> MinPlus a
MinPlus Double
0

instance NHA.Additive (MinPlus Double) where
  zero :: MinPlus Double
zero = Double -> MinPlus Double
forall a. a -> MinPlus a
MinPlus (Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
P./ Double
0)
  MinPlus Double
a + :: MinPlus Double -> MinPlus Double -> MinPlus Double
+ MinPlus Double
b = Double -> MinPlus Double
forall a. a -> MinPlus a
MinPlus (Double -> Double -> Double
forall a. Ord a => a -> a -> a
P.min Double
a Double
b)

instance Magma (MinPlus Double) where
  MinPlus Double
a ⊕ :: MinPlus Double -> MinPlus Double -> MinPlus Double
⊕ MinPlus Double
b = MinPlus Double
a MinPlus Double -> MinPlus Double -> MinPlus Double
forall a. Additive a => a -> a -> a
NHA.+ MinPlus Double
b

instance Idempotent (MinPlus Double)

-- | Star is zero in a min-plus semiring: the cheapest repeated traversal is
-- to stay put.
--
-- >>> star (MinPlus 2 :: MinPlus Double)
-- MinPlus {getMinPlus = 0.0}
--
-- Conway equations for 'MinPlus Double'.
--
-- >>> let a = MinPlus 2 :: MinPlus Double; b = MinPlus 3 :: MinPlus Double in star (a * b) == one + a * star (b * a) * b
-- True
--
-- >>> let a = MinPlus 2 :: MinPlus Double; b = MinPlus 3 :: MinPlus Double in star (a + b) == star (star a * b) * star a
-- True
instance NHR.StarSemiring (MinPlus Double) where
  star :: MinPlus Double -> MinPlus Double
star MinPlus Double
_ = MinPlus Double
forall a. Multiplicative a => a
NHM.one

instance NHR.KleeneAlgebra (MinPlus Double)

-- | Tropical join-semilattice structure: join is 'min', bottom is positive
-- infinity.
instance (P.Ord a) => NHAL.JoinSemiLattice (MinPlus a) where
  MinPlus a
a \/ :: MinPlus a -> MinPlus a -> MinPlus a
\/ MinPlus a
b = a -> MinPlus a
forall a. a -> MinPlus a
MinPlus (a -> a -> a
forall a. Ord a => a -> a -> a
P.min a
a a
b)

instance NHAL.LowerBounded (MinPlus Double) where
  bottom :: MinPlus Double
bottom = Double -> MinPlus Double
forall a. a -> MinPlus a
MinPlus (Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
P./ Double
0)

instance NHAL.CompleteJoinSemiLattice (MinPlus Double)

-- | Field semiring for matrix inversion @(I − A)⁻¹@.
--
-- 'star' is the closed Neumann series: @star a = recip (1 − a)@.
newtype FieldStar = FieldStar {FieldStar -> Double
unFieldStar :: Double}
  deriving (FieldStar -> FieldStar -> Bool
(FieldStar -> FieldStar -> Bool)
-> (FieldStar -> FieldStar -> Bool) -> Eq FieldStar
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: FieldStar -> FieldStar -> Bool
== :: FieldStar -> FieldStar -> Bool
$c/= :: FieldStar -> FieldStar -> Bool
/= :: FieldStar -> FieldStar -> Bool
Eq, Eq FieldStar
Eq FieldStar =>
(FieldStar -> FieldStar -> Ordering)
-> (FieldStar -> FieldStar -> Bool)
-> (FieldStar -> FieldStar -> Bool)
-> (FieldStar -> FieldStar -> Bool)
-> (FieldStar -> FieldStar -> Bool)
-> (FieldStar -> FieldStar -> FieldStar)
-> (FieldStar -> FieldStar -> FieldStar)
-> Ord FieldStar
FieldStar -> FieldStar -> Bool
FieldStar -> FieldStar -> Ordering
FieldStar -> FieldStar -> FieldStar
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: FieldStar -> FieldStar -> Ordering
compare :: FieldStar -> FieldStar -> Ordering
$c< :: FieldStar -> FieldStar -> Bool
< :: FieldStar -> FieldStar -> Bool
$c<= :: FieldStar -> FieldStar -> Bool
<= :: FieldStar -> FieldStar -> Bool
$c> :: FieldStar -> FieldStar -> Bool
> :: FieldStar -> FieldStar -> Bool
$c>= :: FieldStar -> FieldStar -> Bool
>= :: FieldStar -> FieldStar -> Bool
$cmax :: FieldStar -> FieldStar -> FieldStar
max :: FieldStar -> FieldStar -> FieldStar
$cmin :: FieldStar -> FieldStar -> FieldStar
min :: FieldStar -> FieldStar -> FieldStar
Ord, Int -> FieldStar -> ShowS
[FieldStar] -> ShowS
FieldStar -> String
(Int -> FieldStar -> ShowS)
-> (FieldStar -> String)
-> ([FieldStar] -> ShowS)
-> Show FieldStar
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FieldStar -> ShowS
showsPrec :: Int -> FieldStar -> ShowS
$cshow :: FieldStar -> String
show :: FieldStar -> String
$cshowList :: [FieldStar] -> ShowS
showList :: [FieldStar] -> ShowS
Show, Integer -> FieldStar
FieldStar -> FieldStar
FieldStar -> FieldStar -> FieldStar
(FieldStar -> FieldStar -> FieldStar)
-> (FieldStar -> FieldStar -> FieldStar)
-> (FieldStar -> FieldStar -> FieldStar)
-> (FieldStar -> FieldStar)
-> (FieldStar -> FieldStar)
-> (FieldStar -> FieldStar)
-> (Integer -> FieldStar)
-> Num FieldStar
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
$c+ :: FieldStar -> FieldStar -> FieldStar
+ :: FieldStar -> FieldStar -> FieldStar
$c- :: FieldStar -> FieldStar -> FieldStar
- :: FieldStar -> FieldStar -> FieldStar
$c* :: FieldStar -> FieldStar -> FieldStar
* :: FieldStar -> FieldStar -> FieldStar
$cnegate :: FieldStar -> FieldStar
negate :: FieldStar -> FieldStar
$cabs :: FieldStar -> FieldStar
abs :: FieldStar -> FieldStar
$csignum :: FieldStar -> FieldStar
signum :: FieldStar -> FieldStar
$cfromInteger :: Integer -> FieldStar
fromInteger :: Integer -> FieldStar
Num, Num FieldStar
Num FieldStar =>
(FieldStar -> FieldStar -> FieldStar)
-> (FieldStar -> FieldStar)
-> (Rational -> FieldStar)
-> Fractional FieldStar
Rational -> FieldStar
FieldStar -> FieldStar
FieldStar -> FieldStar -> FieldStar
forall a.
Num a =>
(a -> a -> a) -> (a -> a) -> (Rational -> a) -> Fractional a
$c/ :: FieldStar -> FieldStar -> FieldStar
/ :: FieldStar -> FieldStar -> FieldStar
$crecip :: FieldStar -> FieldStar
recip :: FieldStar -> FieldStar
$cfromRational :: Rational -> FieldStar
fromRational :: Rational -> FieldStar
Fractional)

instance NHM.Multiplicative FieldStar where
  one :: FieldStar
one = Double -> FieldStar
FieldStar Double
1
  FieldStar Double
a * :: FieldStar -> FieldStar -> FieldStar
* FieldStar Double
b = Double -> FieldStar
FieldStar (Double
a Double -> Double -> Double
forall a. Num a => a -> a -> a
P.* Double
b)

instance NHA.Additive FieldStar where
  zero :: FieldStar
zero = Double -> FieldStar
FieldStar Double
0
  FieldStar Double
a + :: FieldStar -> FieldStar -> FieldStar
+ FieldStar Double
b = Double -> FieldStar
FieldStar (Double
a Double -> Double -> Double
forall a. Num a => a -> a -> a
P.+ Double
b)

instance NHA.Subtractive FieldStar where
  negate :: FieldStar -> FieldStar
negate (FieldStar Double
a) = Double -> FieldStar
FieldStar (Double -> Double
forall a. Num a => a -> a
P.negate Double
a)
  FieldStar Double
a - :: FieldStar -> FieldStar -> FieldStar
- FieldStar Double
b = Double -> FieldStar
FieldStar (Double
a Double -> Double -> Double
forall a. Num a => a -> a -> a
P.- Double
b)

instance NHR.StarSemiring FieldStar where
  star :: FieldStar -> FieldStar
star (FieldStar Double
a) = Double -> FieldStar
FieldStar (Double -> Double
forall a. Fractional a => a -> a
P.recip (Double
1 Double -> Double -> Double
forall a. Num a => a -> a -> a
P.- Double
a))

-- | Viterbi semiring for maximum-probability paths.
--
-- 'plus' is 'max', 'times' is ordinary multiplication, the additive unit is
-- @0@ and the multiplicative unit is @1@. The star of any value is @1@,
-- because the empty path has probability 1 and no repeated path can improve
-- on that.
newtype Viterbi a = Viterbi {forall a. Viterbi a -> a
getViterbi :: a}
  deriving (Viterbi a -> Viterbi a -> Bool
(Viterbi a -> Viterbi a -> Bool)
-> (Viterbi a -> Viterbi a -> Bool) -> Eq (Viterbi a)
forall a. Eq a => Viterbi a -> Viterbi a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Viterbi a -> Viterbi a -> Bool
== :: Viterbi a -> Viterbi a -> Bool
$c/= :: forall a. Eq a => Viterbi a -> Viterbi a -> Bool
/= :: Viterbi a -> Viterbi a -> Bool
Eq, Eq (Viterbi a)
Eq (Viterbi a) =>
(Viterbi a -> Viterbi a -> Ordering)
-> (Viterbi a -> Viterbi a -> Bool)
-> (Viterbi a -> Viterbi a -> Bool)
-> (Viterbi a -> Viterbi a -> Bool)
-> (Viterbi a -> Viterbi a -> Bool)
-> (Viterbi a -> Viterbi a -> Viterbi a)
-> (Viterbi a -> Viterbi a -> Viterbi a)
-> Ord (Viterbi a)
Viterbi a -> Viterbi a -> Bool
Viterbi a -> Viterbi a -> Ordering
Viterbi a -> Viterbi a -> Viterbi a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Viterbi a)
forall a. Ord a => Viterbi a -> Viterbi a -> Bool
forall a. Ord a => Viterbi a -> Viterbi a -> Ordering
forall a. Ord a => Viterbi a -> Viterbi a -> Viterbi a
$ccompare :: forall a. Ord a => Viterbi a -> Viterbi a -> Ordering
compare :: Viterbi a -> Viterbi a -> Ordering
$c< :: forall a. Ord a => Viterbi a -> Viterbi a -> Bool
< :: Viterbi a -> Viterbi a -> Bool
$c<= :: forall a. Ord a => Viterbi a -> Viterbi a -> Bool
<= :: Viterbi a -> Viterbi a -> Bool
$c> :: forall a. Ord a => Viterbi a -> Viterbi a -> Bool
> :: Viterbi a -> Viterbi a -> Bool
$c>= :: forall a. Ord a => Viterbi a -> Viterbi a -> Bool
>= :: Viterbi a -> Viterbi a -> Bool
$cmax :: forall a. Ord a => Viterbi a -> Viterbi a -> Viterbi a
max :: Viterbi a -> Viterbi a -> Viterbi a
$cmin :: forall a. Ord a => Viterbi a -> Viterbi a -> Viterbi a
min :: Viterbi a -> Viterbi a -> Viterbi a
Ord, Int -> Viterbi a -> ShowS
[Viterbi a] -> ShowS
Viterbi a -> String
(Int -> Viterbi a -> ShowS)
-> (Viterbi a -> String)
-> ([Viterbi a] -> ShowS)
-> Show (Viterbi a)
forall a. Show a => Int -> Viterbi a -> ShowS
forall a. Show a => [Viterbi a] -> ShowS
forall a. Show a => Viterbi a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Viterbi a -> ShowS
showsPrec :: Int -> Viterbi a -> ShowS
$cshow :: forall a. Show a => Viterbi a -> String
show :: Viterbi a -> String
$cshowList :: forall a. Show a => [Viterbi a] -> ShowS
showList :: [Viterbi a] -> ShowS
Show)

instance NHM.Multiplicative (Viterbi Double) where
  one :: Viterbi Double
one = Double -> Viterbi Double
forall a. a -> Viterbi a
Viterbi Double
1
  Viterbi Double
a * :: Viterbi Double -> Viterbi Double -> Viterbi Double
* Viterbi Double
b = Double -> Viterbi Double
forall a. a -> Viterbi a
Viterbi (Double
a Double -> Double -> Double
forall a. Num a => a -> a -> a
P.* Double
b)

instance NHA.Additive (Viterbi Double) where
  zero :: Viterbi Double
zero = Double -> Viterbi Double
forall a. a -> Viterbi a
Viterbi Double
0
  Viterbi Double
a + :: Viterbi Double -> Viterbi Double -> Viterbi Double
+ Viterbi Double
b = Double -> Viterbi Double
forall a. a -> Viterbi a
Viterbi (Double -> Double -> Double
forall a. Ord a => a -> a -> a
P.max Double
a Double
b)

instance Magma (Viterbi Double) where
  Viterbi Double
a ⊕ :: Viterbi Double -> Viterbi Double -> Viterbi Double
⊕ Viterbi Double
b = Viterbi Double
a Viterbi Double -> Viterbi Double -> Viterbi Double
forall a. Additive a => a -> a -> a
NHA.+ Viterbi Double
b

instance Idempotent (Viterbi Double)

instance NHR.StarSemiring (Viterbi Double) where
  star :: Viterbi Double -> Viterbi Double
star Viterbi Double
_ = Viterbi Double
forall a. Multiplicative a => a
NHM.one

instance NHR.KleeneAlgebra (Viterbi Double)