Copyright	(c) David Llorens and Juan Miguel Vilar 2020
License	BSD-3-Clause
Stability	experimental
Safe Haskell	Safe-Inferred
Language	Haskell2010

HyloDP.Semiring

Contents

Type Classes
Semiring Helpers
Other functions

Description

This module declares the Semiring class and various instances.

Synopsis

class Semiring s where
- (<+>) :: s -> s -> s
- (<.>) :: s -> s -> s
- zero :: s
- one :: s
class Opt t where
- optimum :: t -> t -> t
newtype TMin v = TMin v
newtype TMax v = TMax v
newtype MinProd v = MinProd v
newtype MaxProd v = MaxProd v
newtype Count = Count Integer
data BestSolution d sc = BestSolution (Maybe [d]) sc
newtype AllSolutions d sc = AllSolutions [([d], sc)]
newtype AllBestSolutions d s = AllBestSolutions ([[d]], s)
decisions :: BestSolution d sc -> [d]

Type Classes

class Semiring s where Source #

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 Source #

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

zero :: s Source #

Neutral element for <+>.

one :: s Source #

Neutral element for <.>.

Instances

Instances details

Semiring Count Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Count -> Count -> Count Source # (<.>) :: Count -> Count -> Count Source # zero :: Count Source # one :: Count Source #
Semiring Integer Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Integer -> Integer -> Integer Source # (<.>) :: Integer -> Integer -> Integer Source # zero :: Integer Source # one :: Integer Source #
Semiring Double Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Double -> Double -> Double Source # (<.>) :: Double -> Double -> Double Source # zero :: Double Source # one :: Double Source #
Semiring Float Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Float -> Float -> Float Source # (<.>) :: Float -> Float -> Float Source # zero :: Float Source # one :: Float Source #
Semiring Int Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Int -> Int -> Int Source # (<.>) :: Int -> Int -> Int Source # zero :: Int Source # one :: Int Source #
(Num v, Ord v, Bounded v) => Semiring (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: MaxProd v -> MaxProd v -> MaxProd v Source # (<.>) :: MaxProd v -> MaxProd v -> MaxProd v Source # zero :: MaxProd v Source # one :: MaxProd v Source #
(Num v, Ord v, Bounded v) => Semiring (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: MinProd v -> MinProd v -> MinProd v Source # (<.>) :: MinProd v -> MinProd v -> MinProd v Source # zero :: MinProd v Source # one :: MinProd v Source #
(Num v, Ord v, Bounded v) => Semiring (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: TMax v -> TMax v -> TMax v Source # (<.>) :: TMax v -> TMax v -> TMax v Source # zero :: TMax v Source # one :: TMax v Source #
(Num v, Ord v, Bounded v) => Semiring (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: TMin v -> TMin v -> TMin v Source # (<.>) :: TMin v -> TMin v -> TMin v Source # zero :: TMin v Source # one :: TMin v Source #
(Semiring sc, Opt sc, Eq sc) => Semiring (AllBestSolutions d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc Source # (<.>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc Source # zero :: AllBestSolutions d sc Source # one :: AllBestSolutions d sc Source #
Semiring sc => Semiring (AllSolutions d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc Source # (<.>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc Source # zero :: AllSolutions d sc Source # one :: AllSolutions d sc Source #
(Semiring sc, Opt sc, Eq sc) => Semiring (BestSolution d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc Source # (<.>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc Source # zero :: BestSolution d sc Source # one :: BestSolution d sc Source #
(Semiring s1, Semiring s2) => Semiring (s1, s2) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: (s1, s2) -> (s1, s2) -> (s1, s2) Source # (<.>) :: (s1, s2) -> (s1, s2) -> (s1, s2) Source # zero :: (s1, s2) Source # one :: (s1, s2) Source #

class Opt t where Source #

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

Methods

optimum :: t -> t -> t Source #

Instances

Instances details

Ord v => Opt (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: MaxProd v -> MaxProd v -> MaxProd v Source #
Ord v => Opt (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: MinProd v -> MinProd v -> MinProd v Source #
Ord v => Opt (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: TMax v -> TMax v -> TMax v Source #
Ord v => Opt (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: TMin v -> TMin v -> TMin v Source #

Semiring Helpers

Min tropical semiring

newtype TMin v Source #

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

Instances details

DPTypes sc d (TMin sc) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> TMin sc Source #
Ord v => Opt (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: TMin v -> TMin v -> TMin v Source #
(Num v, Ord v, Bounded v) => Semiring (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: TMin v -> TMin v -> TMin v Source # (<.>) :: TMin v -> TMin v -> TMin v Source # zero :: TMin v Source # one :: TMin v Source #
Show v => Show (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods showsPrec :: Int -> TMin v -> ShowS # show :: TMin v -> String # showList :: [TMin v] -> ShowS #
Eq v => Eq (TMin v) Source #
Instance details Defined in HyloDP.Semiring Methods (==) :: TMin v -> TMin v -> Bool # (/=) :: TMin v -> TMin v -> Bool #
Ord v => Ord (TMin v) Source #
Instance details 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 Source #

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

Instances details

DPTypes sc d (TMax sc) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> TMax sc Source #
Ord v => Opt (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: TMax v -> TMax v -> TMax v Source #
(Num v, Ord v, Bounded v) => Semiring (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: TMax v -> TMax v -> TMax v Source # (<.>) :: TMax v -> TMax v -> TMax v Source # zero :: TMax v Source # one :: TMax v Source #
Show v => Show (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods showsPrec :: Int -> TMax v -> ShowS # show :: TMax v -> String # showList :: [TMax v] -> ShowS #
Eq v => Eq (TMax v) Source #
Instance details Defined in HyloDP.Semiring Methods (==) :: TMax v -> TMax v -> Bool # (/=) :: TMax v -> TMax v -> Bool #
Ord v => Ord (TMax v) Source #
Instance details 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 Source #

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

Constructors

MinProd v

Instances

Instances details

Ord v => Opt (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: MinProd v -> MinProd v -> MinProd v Source #
(Num v, Ord v, Bounded v) => Semiring (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: MinProd v -> MinProd v -> MinProd v Source # (<.>) :: MinProd v -> MinProd v -> MinProd v Source # zero :: MinProd v Source # one :: MinProd v Source #
Show v => Show (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods showsPrec :: Int -> MinProd v -> ShowS # show :: MinProd v -> String # showList :: [MinProd v] -> ShowS #
Eq v => Eq (MinProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (==) :: MinProd v -> MinProd v -> Bool # (/=) :: MinProd v -> MinProd v -> Bool #
Ord v => Ord (MinProd v) Source #
Instance details 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 Source #

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

Constructors

MaxProd v

Instances

Instances details

DPTypes sc d (MaxProd sc) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> MaxProd sc Source #
Ord v => Opt (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods optimum :: MaxProd v -> MaxProd v -> MaxProd v Source #
(Num v, Ord v, Bounded v) => Semiring (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: MaxProd v -> MaxProd v -> MaxProd v Source # (<.>) :: MaxProd v -> MaxProd v -> MaxProd v Source # zero :: MaxProd v Source # one :: MaxProd v Source #
Show v => Show (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods showsPrec :: Int -> MaxProd v -> ShowS # show :: MaxProd v -> String # showList :: [MaxProd v] -> ShowS #
Eq v => Eq (MaxProd v) Source #
Instance details Defined in HyloDP.Semiring Methods (==) :: MaxProd v -> MaxProd v -> Bool # (/=) :: MaxProd v -> MaxProd v -> Bool #
Ord v => Ord (MaxProd v) Source #
Instance details 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 Source #

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

Constructors

Count Integer

Instances

Instances details

Semiring Count Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: Count -> Count -> Count Source # (<.>) :: Count -> Count -> Count Source # zero :: Count Source # one :: Count Source #
Show Count Source #
Instance details Defined in HyloDP.Semiring Methods showsPrec :: Int -> Count -> ShowS # show :: Count -> String # showList :: [Count] -> ShowS #
DPTypes sc d Count Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> Count Source #

Best solution semiring

data BestSolution d sc Source #

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

Instances details

DPTypes sc d sol => DPTypes sc d (BestSolution d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> BestSolution d sol Source #
DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (BestSolution d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> Maybe d -> BestSolution d sol Source #
(Semiring sc, Opt sc, Eq sc) => Semiring (BestSolution d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc Source # (<.>) :: BestSolution d sc -> BestSolution d sc -> BestSolution d sc Source # zero :: BestSolution d sc Source # one :: BestSolution d sc Source #
(Show d, Show sc) => Show (BestSolution d sc) Source #
Instance details 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) Source #
Instance details 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 Source #

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

Constructors

AllSolutions [([d], sc)]

Instances

Instances details

DPTypes sc d sol => DPTypes sc d (AllSolutions d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> AllSolutions d sol Source #
DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (AllSolutions d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> Maybe d -> AllSolutions d sol Source #
Semiring sc => Semiring (AllSolutions d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc Source # (<.>) :: AllSolutions d sc -> AllSolutions d sc -> AllSolutions d sc Source # zero :: AllSolutions d sc Source # one :: AllSolutions d sc Source #
(Show d, Show sc) => Show (AllSolutions d sc) Source #
Instance details 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 Source #

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

Instances details

DPTypes sc d sol => DPTypes sc d (AllBestSolutions d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> d -> AllBestSolutions d sol Source #
DPTypes sc (Maybe d) sol => DPTypes sc (Maybe d) (AllBestSolutions d sol) Source #
Instance details Defined in HyloDP.Base Methods combine :: sc -> Maybe d -> AllBestSolutions d sol Source #
(Semiring sc, Opt sc, Eq sc) => Semiring (AllBestSolutions d sc) Source #
Instance details Defined in HyloDP.Semiring Methods (<+>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc Source # (<.>) :: AllBestSolutions d sc -> AllBestSolutions d sc -> AllBestSolutions d sc Source # zero :: AllBestSolutions d sc Source # one :: AllBestSolutions d sc Source #
(Show d, Show s) => Show (AllBestSolutions d s) Source #
Instance details 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] Source #

Auxiliary function to recover the sequence of decisions from a BestSolution