HyloDP.Semiring

This module declares the Semiring class and various instances.

Type Classes

class Semiring s where

A Semiring is a type with two operations <+> and <.> and two distinguished elements, zero and one, which satisfy the following axioms:

• Conmutativity:

a <+> b == b <+> a
a <.> b == b <.> a

• Associativity:

a <+> (b <+> c) == (a <+> b) <+> c
a <.> (b <.> c) == (a <.> b) <.> c

• Identity:

a <+> zero = zero <+> a == a
a <.> one = one <.> a == a

• Distributive property:

a <.> (b<+>c) == (a<.>b) <+> (a<.>c)
(a<+>b) <.>c == (a<.>c) <+> (b<.>c)

• Anhiliation of multiplication by zero:

a <.> zero = zero <.> a = zero

Methods

(<+>) :: s -> s -> s infixl 6

(<.>) :: s -> s -> s infixl 7

zero :: s

Neutral element for <+>.

one :: s

Neutral element for <.>.

Instances

Semiring Count

Defined in HyloDP.Semiring

Methods

(<+>) :: Count -> Count -> Count

(<.>) :: Count -> Count -> Count

zero :: Count

one :: Count

Semiring Integer

Defined in HyloDP.Semiring

Methods

(<+>) :: Integer -> Integer -> Integer

(<.>) :: Integer -> Integer -> Integer

zero :: Integer

one :: Integer

Semiring Double

Defined in HyloDP.Semiring

Methods

(<+>) :: Double -> Double -> Double

(<.>) :: Double -> Double -> Double

zero :: Double

one :: Double

Semiring Float

Defined in HyloDP.Semiring

Methods

(<+>) :: Float -> Float -> Float

(<.>) :: Float -> Float -> Float

zero :: Float

one :: Float

Semiring Int

Defined in HyloDP.Semiring

Methods

(<+>) :: Int -> Int -> Int

(<.>) :: Int -> Int -> Int

zero :: Int

one :: Int

(Num v, Ord v, Bounded v) => Semiring (MaxProd v)

Defined in HyloDP.Semiring

Methods

(<+>) :: MaxProd v -> MaxProd v -> MaxProd v

(<.>) :: MaxProd v -> MaxProd v -> MaxProd v

zero :: MaxProd v

one :: MaxProd v

(Num v, Ord v, Bounded v) => Semiring (MinProd v)

Defined in HyloDP.Semiring

Methods

(<+>) :: MinProd v -> MinProd v -> MinProd v

(<.>) :: MinProd v -> MinProd v -> MinProd v

zero :: MinProd v

one :: MinProd v

(Num v, Ord v, Bounded v) => Semiring (TMax v)

Defined in HyloDP.Semiring

Methods

(<+>) :: TMax v -> TMax v -> TMax v

(<.>) :: TMax v -> TMax v -> TMax v

zero :: TMax v

one :: TMax v

(Num v, Ord v, Bounded v) => Semiring (TMin v)

Defined in HyloDP.Semiring

Methods

(<+>) :: TMin v -> TMin v -> TMin v

(<.>) :: TMin v -> TMin v -> TMin v

zero :: TMin v

one :: TMin v

(Semiring sc, Opt sc, Eq sc) => Semiring (AllBestSolutions d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc

(<.>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc

zero :: AllBestSolutions d sc

one :: AllBestSolutions d sc

Semiring sc => Semiring (AllSolutions d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc

(<.>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc

zero :: AllSolutions d sc

one :: AllSolutions d sc

(Semiring sc, Opt sc, Eq sc) => Semiring (BestSolution d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc

(<.>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc

zero :: BestSolution d sc

one :: BestSolution d sc

(Semiring s1, Semiring s2) => Semiring (s1, s2)

Defined in HyloDP.Semiring

Methods

(<+>) :: (s1, s2) -> (s1, s2) -> (s1, s2)

(<.>) :: (s1, s2) -> (s1, s2) -> (s1, s2)

zero :: (s1, s2)

one :: (s1, s2)

class Opt t where

This typeclass is used in optimization semirings. It is expected that optimum a b returns either a or b.

Methods

optimum :: t -> t -> t

Instances

Ord v => Opt (MaxProd v)

Defined in HyloDP.Semiring

Methods

optimum :: MaxProd v -> MaxProd v -> MaxProd v

Ord v => Opt (MinProd v)

Defined in HyloDP.Semiring

Methods

optimum :: MinProd v -> MinProd v -> MinProd v

Ord v => Opt (TMax v)

Defined in HyloDP.Semiring

Methods

optimum :: TMax v -> TMax v -> TMax v

Ord v => Opt (TMin v)

Defined in HyloDP.Semiring

Methods

optimum :: TMin v -> TMin v -> TMin v

Semiring Helpers

Min tropical semiring

newtype TMin v

The tropical min semiring, a semiring that uses min as <+> and sum as <.>. It is used in problems that ask for minimizing a sum of values.

Constructors

TMin v

Instances

DPTypes sc d (TMin sc)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> TMin sc

Ord v => Opt (TMin v)

Defined in HyloDP.Semiring

Methods

optimum :: TMin v -> TMin v -> TMin v

(Num v, Ord v, Bounded v) => Semiring (TMin v)

Defined in HyloDP.Semiring

Methods

(<+>) :: TMin v -> TMin v -> TMin v

(<.>) :: TMin v -> TMin v -> TMin v

zero :: TMin v

one :: TMin v

Show v => Show (TMin v)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> TMin v -> ShowS

show :: TMin v -> String

showList :: [TMin v] -> ShowS

Eq v => Eq (TMin v)

Defined in HyloDP.Semiring

Methods

(==) :: TMin v -> TMin v -> Bool

(/=) :: TMin v -> TMin v -> Bool

Ord v => Ord (TMin v)

Defined in HyloDP.Semiring

Methods

compare :: TMin v -> TMin v -> Ordering

(<) :: TMin v -> TMin v -> Bool

(<=) :: TMin v -> TMin v -> Bool

(>) :: TMin v -> TMin v -> Bool

(>=) :: TMin v -> TMin v -> Bool

max :: TMin v -> TMin v -> TMin v

min :: TMin v -> TMin v -> TMin v

Max tropical semiring

newtype TMax v

The tropical max semiring, a semiring that uses max as <+> and sum as <.>. It is used in problems that ask for maximizing a sum of values.

Constructors

TMax v

Instances

DPTypes sc d (TMax sc)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> TMax sc

Ord v => Opt (TMax v)

Defined in HyloDP.Semiring

Methods

optimum :: TMax v -> TMax v -> TMax v

(Num v, Ord v, Bounded v) => Semiring (TMax v)

Defined in HyloDP.Semiring

Methods

(<+>) :: TMax v -> TMax v -> TMax v

(<.>) :: TMax v -> TMax v -> TMax v

zero :: TMax v

one :: TMax v

Show v => Show (TMax v)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> TMax v -> ShowS

show :: TMax v -> String

showList :: [TMax v] -> ShowS

Eq v => Eq (TMax v)

Defined in HyloDP.Semiring

Methods

(==) :: TMax v -> TMax v -> Bool

(/=) :: TMax v -> TMax v -> Bool

Ord v => Ord (TMax v)

Defined in HyloDP.Semiring

Methods

compare :: TMax v -> TMax v -> Ordering

(<) :: TMax v -> TMax v -> Bool

(<=) :: TMax v -> TMax v -> Bool

(>) :: TMax v -> TMax v -> Bool

(>=) :: TMax v -> TMax v -> Bool

max :: TMax v -> TMax v -> TMax v

min :: TMax v -> TMax v -> TMax v

Min product semiring

newtype MinProd v

The MinProd semiring is the analogous to the TMin semiring for minimizing products.

Constructors

MinProd v

Instances

Ord v => Opt (MinProd v)

Defined in HyloDP.Semiring

Methods

optimum :: MinProd v -> MinProd v -> MinProd v

(Num v, Ord v, Bounded v) => Semiring (MinProd v)

Defined in HyloDP.Semiring

Methods

(<+>) :: MinProd v -> MinProd v -> MinProd v

(<.>) :: MinProd v -> MinProd v -> MinProd v

zero :: MinProd v

one :: MinProd v

Show v => Show (MinProd v)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> MinProd v -> ShowS

show :: MinProd v -> String

showList :: [MinProd v] -> ShowS

Eq v => Eq (MinProd v)

Defined in HyloDP.Semiring

Methods

(==) :: MinProd v -> MinProd v -> Bool

(/=) :: MinProd v -> MinProd v -> Bool

Ord v => Ord (MinProd v)

Defined in HyloDP.Semiring

Methods

compare :: MinProd v -> MinProd v -> Ordering

(<) :: MinProd v -> MinProd v -> Bool

(<=) :: MinProd v -> MinProd v -> Bool

(>) :: MinProd v -> MinProd v -> Bool

(>=) :: MinProd v -> MinProd v -> Bool

max :: MinProd v -> MinProd v -> MinProd v

min :: MinProd v -> MinProd v -> MinProd v

Max product semiring

newtype MaxProd v

The MaxProd semiring is the analogous to the TMax semiring for maximizing products.

Constructors

MaxProd v

Instances

DPTypes sc d (MaxProd sc)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> MaxProd sc

Ord v => Opt (MaxProd v)

Defined in HyloDP.Semiring

Methods

optimum :: MaxProd v -> MaxProd v -> MaxProd v

(Num v, Ord v, Bounded v) => Semiring (MaxProd v)

Defined in HyloDP.Semiring

Methods

(<+>) :: MaxProd v -> MaxProd v -> MaxProd v

(<.>) :: MaxProd v -> MaxProd v -> MaxProd v

zero :: MaxProd v

one :: MaxProd v

Show v => Show (MaxProd v)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> MaxProd v -> ShowS

show :: MaxProd v -> String

showList :: [MaxProd v] -> ShowS

Eq v => Eq (MaxProd v)

Defined in HyloDP.Semiring

Methods

(==) :: MaxProd v -> MaxProd v -> Bool

(/=) :: MaxProd v -> MaxProd v -> Bool

Ord v => Ord (MaxProd v)

Defined in HyloDP.Semiring

Methods

compare :: MaxProd v -> MaxProd v -> Ordering

(<) :: MaxProd v -> MaxProd v -> Bool

(<=) :: MaxProd v -> MaxProd v -> Bool

(>) :: MaxProd v -> MaxProd v -> Bool

(>=) :: MaxProd v -> MaxProd v -> Bool

max :: MaxProd v -> MaxProd v -> MaxProd v

min :: MaxProd v -> MaxProd v -> MaxProd v

Count semiring

newtype Count

The Count semiring is used for counting the number of different solutions.

Constructors

Count Integer

Instances

Semiring Count

Defined in HyloDP.Semiring

Methods

(<+>) :: Count -> Count -> Count

(<.>) :: Count -> Count -> Count

zero :: Count

one :: Count

Show Count

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> Count -> ShowS

show :: Count -> String

showList :: [Count] -> ShowS

DPTypes sc d Count

Defined in HyloDP.Base

Methods

combine :: sc -> d -> Count

Best solution semiring

data BestSolution d sc

The BestSolution semiring is used for recovering the best sequence of decisions together with its score. The score must be an instance of Opt to be able to decide which is the best of two scores.

Constructors

BestSolution (Maybe [d]) sc

Instances

DPTypes sc d sol => DPTypes sc d (BestSolution d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> BestSolution d sol

DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (BestSolution d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> Maybe d -> BestSolution d sol

(Semiring sc, Opt sc, Eq sc) => Semiring (BestSolution d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc

(<.>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc

zero :: BestSolution d sc

one :: BestSolution d sc

(Show d, Show sc) => Show (BestSolution d sc)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> BestSolution d sc -> ShowS

show :: BestSolution d sc -> String

showList :: [BestSolution d sc] -> ShowS

(Eq d, Eq sc) => Eq (BestSolution d sc)

Defined in HyloDP.Semiring

Methods

(==) :: BestSolution d sc -> BestSolution d sc -> Bool

(/=) :: BestSolution d sc -> BestSolution d sc -> Bool

All solutions semiring

newtype AllSolutions d sc

With the AllSolutions semiring it is possible to recover all possible solutions to a problem, regardless of their scores.

Constructors

AllSolutions [([d], sc)]

Instances

DPTypes sc d sol => DPTypes sc d (AllSolutions d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> AllSolutions d sol

DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (AllSolutions d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> Maybe d -> AllSolutions d sol

Semiring sc => Semiring (AllSolutions d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc

(<.>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc

zero :: AllSolutions d sc

one :: AllSolutions d sc

(Show d, Show sc) => Show (AllSolutions d sc)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> AllSolutions d sc -> ShowS

show :: AllSolutions d sc -> String

showList :: [AllSolutions d sc] -> ShowS

All best solutions semiring

newtype AllBestSolutions d s

With the AllBestSolutions semiring it is possible to recover all the solutions to a problem that reach the optimum score.

Constructors

AllBestSolutions ([[d]], s)

Instances

DPTypes sc d sol => DPTypes sc d (AllBestSolutions d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> d -> AllBestSolutions d sol

DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (AllBestSolutions d sol)

Defined in HyloDP.Base

Methods

combine :: sc -> Maybe d -> AllBestSolutions d sol

(Semiring sc, Opt sc, Eq sc) => Semiring (AllBestSolutions d sc)

Defined in HyloDP.Semiring

Methods

(<+>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc

(<.>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc

zero :: AllBestSolutions d sc

one :: AllBestSolutions d sc

(Show d, Show s) => Show (AllBestSolutions d s)

Defined in HyloDP.Semiring

Methods

showsPrec :: Int -> AllBestSolutions d s -> ShowS

show :: AllBestSolutions d s -> String

showList :: [AllBestSolutions d s] -> ShowS

Other functions

decisions :: BestSolution d sc -> [d]

Auxiliary function to recover the sequence of decisions from a BestSolution