Data.Semiring

Documentation

class Semigroup r => Semiring r where

Right pre-semirings and (non-unital and unital) right semirings.

A right pre-semiring (sometimes referred to as a bisemigroup) is a type R endowed with two associative binary (i.e. semigroup) operations: (<>) and (><), along with a right-distributivity property connecting them:

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

A non-unital right semiring (sometimes referred to as a bimonoid) is a pre-semiring with a mempty element that is neutral with respect to both addition and multiplication.

A unital right semiring is a pre-semiring with two distinct neutral elements, mempty and unit, such that mempty is right-neutral wrt addition, unit is right-neutral wrt multiplication, and mempty is right-annihilative wrt multiplication.

Note that unit needn't be distinct from mempty.

Instances also need not be commutative nor left-distributive.

See the properties module for a detailed specification of the laws.

Minimal complete definition

(><)

Methods

(><) :: r -> r -> r

fromBoolean :: Monoid r => Bool -> r

Instances

Semiring Bool

Defined in Data.Semiring

Methods

(><) :: Bool -> Bool -> Bool

fromBoolean :: Bool -> Bool

Semiring Int

Defined in Data.Semiring

Methods

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

fromBoolean :: Bool -> Int

Semiring Natural

Defined in Data.Semiring

Methods

(><) :: Natural -> Natural -> Natural

fromBoolean :: Bool -> Natural

Semiring Ordering

Defined in Data.Semiring

Methods

(><) :: Ordering -> Ordering -> Ordering

fromBoolean :: Bool -> Ordering

Semiring Word

Defined in Data.Semiring

Methods

(><) :: Word -> Word -> Word

fromBoolean :: Bool -> Word

Semiring ()

Defined in Data.Semiring

Methods

(><) :: () -> () -> ()

fromBoolean :: Bool -> ()

Semiring All

Defined in Data.Semiring

Methods

(><) :: All -> All -> All

fromBoolean :: Bool -> All

Semiring Any

Defined in Data.Semiring

Methods

(><) :: Any -> Any -> Any

fromBoolean :: Bool -> Any

Monoid a => Semiring [a]

Defined in Data.Semiring

Methods

(><) :: [a] -> [a] -> [a]

fromBoolean :: Bool -> [a]

(Monoid a, Semiring a) => Semiring (Maybe a)

Defined in Data.Semiring

Methods

(><) :: Maybe a -> Maybe a -> Maybe a

fromBoolean :: Bool -> Maybe a

(Monoid a, Semiring a) => Semiring (IO a)

Defined in Data.Semiring

Methods

(><) :: IO a -> IO a -> IO a

fromBoolean :: Bool -> IO a

Semiring (Predicate a)

Defined in Data.Semiring

Methods

(><) :: Predicate a -> Predicate a -> Predicate a

fromBoolean :: Bool -> Predicate a

Semiring (Comparison a)

Defined in Data.Semiring

Methods

(><) :: Comparison a -> Comparison a -> Comparison a

fromBoolean :: Bool -> Comparison a

Semiring (Equivalence a)

Defined in Data.Semiring

Methods

(><) :: Equivalence a -> Equivalence a -> Equivalence a

fromBoolean :: Bool -> Equivalence a

Ord a => Semiring (Min a)

Defined in Data.Semiring

Methods

(><) :: Min a -> Min a -> Min a

fromBoolean :: Bool -> Min a

Ord a => Semiring (Max a)

Defined in Data.Semiring

Methods

(><) :: Max a -> Max a -> Max a

fromBoolean :: Bool -> Max a

Semigroup a => Semiring (First a)

'First a' forms a pre-semiring for any semigroup a.

>>> foldMap1 First $ 1 :| [2..(5 :: Int)] >< 1 :| [2..(5 :: Int)]
First {getFirst = 1}

>>> product1 First $ 1 :| [2..(5 :: Int)]
First {getFirst = 15}

>>> foldMap1 First $ Nothing :| [Just (5 :: Int), Just 6,  Nothing]
First {getFirst = Nothing}

>>> product1 First $ Nothing :| [Just (5 :: Int), Just 6,  Nothing]
First {getFirst = Just 11}

Defined in Data.Semiring

Methods

(><) :: First a -> First a -> First a

fromBoolean :: Bool -> First a

Semigroup a => Semiring (Last a)

Defined in Data.Semiring

Methods

(><) :: Last a -> Last a -> Last a

fromBoolean :: Bool -> Last a

(Monoid a, Semiring a) => Semiring (Identity a)

Defined in Data.Semiring

Methods

(><) :: Identity a -> Identity a -> Identity a

fromBoolean :: Bool -> Identity a

(Monoid a, Semiring a) => Semiring (Dual a)

Defined in Data.Semiring

Methods

(><) :: Dual a -> Dual a -> Dual a

fromBoolean :: Bool -> Dual a

Semigroup a => Semiring (NonEmpty a)

Defined in Data.Semiring

Methods

(><) :: NonEmpty a -> NonEmpty a -> NonEmpty a

fromBoolean :: Bool -> NonEmpty a

Monoid a => Semiring (IntMap a)

Defined in Data.Semiring

Methods

(><) :: IntMap a -> IntMap a -> IntMap a

fromBoolean :: Bool -> IntMap a

Monoid a => Semiring (Seq a)

Defined in Data.Semiring

Methods

(><) :: Seq a -> Seq a -> Seq a

fromBoolean :: Bool -> Seq a

Ord a => Semiring (Set a)

Defined in Data.Semiring

Methods

(><) :: Set a -> Set a -> Set a

fromBoolean :: Bool -> Set a

(Monoid b, Semiring b) => Semiring (a -> b)

Defined in Data.Semiring

Methods

(><) :: (a -> b) -> (a -> b) -> a -> b

fromBoolean :: Bool -> a -> b

Semigroup a => Semiring (Either e a)

Defined in Data.Semiring

Methods

(><) :: Either e a -> Either e a -> Either e a

fromBoolean :: Bool -> Either e a

(Monoid a, Monoid b, Semiring a, Semiring b) => Semiring (a, b)

Defined in Data.Semiring

Methods

(><) :: (a, b) -> (a, b) -> (a, b)

fromBoolean :: Bool -> (a, b)

(Monoid a, Semiring a) => Semiring (Op a b)

Defined in Data.Semiring

Methods

(><) :: Op a b -> Op a b -> Op a b

fromBoolean :: Bool -> Op a b

(Ord k, Monoid k, Monoid a) => Semiring (Map k a)

Defined in Data.Semiring

Methods

(><) :: Map k a -> Map k a -> Map k a

fromBoolean :: Bool -> Map k a

(Monoid a, Semiring a) => Semiring (Const a b)

Defined in Data.Semiring

Methods

(><) :: Const a b -> Const a b -> Const a b

fromBoolean :: Bool -> Const a b

unit :: (Monoid r, Semiring r) => r

fromBooleanDef :: (Monoid r, Semiring r) => r -> Bool -> r

product :: (Foldable t, Monoid r, Semiring r) => (a -> r) -> t a -> r

Fold over a collection using the multiplicative operation of a semiring.

product f ≡ foldr' ((><) . f) unit

>>> (foldMap . product) id [[1, 2], [3, (4 :: Int)]] -- 1 >< 2 <> 3 >< 4
14

>>> (product . foldMap) id [[1, 2], [3, (4 :: Int)]] -- 1 <> 2 >< 3 <> 4
21

For semirings without a distinct multiplicative unit this is equivalent to const mempty:

>>> product Just [1..(5 :: Int)]
Just 0

In this situation you most likely want to use product1.

product1 :: (Foldable1 t, Semiring r) => (a -> r) -> t a -> r

Fold over a non-empty collection using the multiplicative operation of a semiring.

As the collection is non-empty this does not require a distinct multiplicative unit:

>>> product1 Just $ 1 :| [2..(5 :: Int)]
Just 120

cross :: (Foldable t, Applicative t, Monoid r, Semiring r) => t r -> t r -> r

Cross-multiply two collections.

>>> cross [1,2,3 ::Int] [1,2,3]
36

>>> cross [1,2,3 ::Int] []
0

cross1 :: (Foldable1 t, Apply t, Semiring r) => t r -> t r -> r

foldPresemiring :: Semiring r => (a -> r) -> NonEmpty (NonEmpty a) -> r

Fold with no additive or multiplicative unit.

foldNonunital :: (Monoid r, Semiring r) => (a -> r) -> [NonEmpty a] -> r

Fold with no multiplicative unit.

foldUnital :: (Monoid r, Semiring r) => (a -> r) -> [[a]] -> r

Fold with additive & multiplicative units.

This function will zero out if there is no multiplicative unit.

replicate :: Monoid r => Natural -> r -> r

A generalization of replicate to an arbitrary Monoid.

Adapted from http://augustss.blogspot.com/2008/07/lost-and-found-if-i-write-108-in.html.

replicate' :: (Monoid r, Semiring r) => Natural -> r -> r

(^) :: (Monoid r, Semiring r) => r -> Natural -> r infixr 8

powers :: (Monoid r, Semiring r) => Natural -> r -> r

newtype Prod a

Monoid under ><. Analogous to Product, but uses the Semiring constraint, rather than Num.

Constructors

Prod

Fields

• getProd :: a

Instances

Functor Prod

Defined in Data.Semiring

Methods

fmap :: (a -> b) -> Prod a -> Prod b

(<$) :: a -> Prod b -> Prod a

Applicative Prod

Defined in Data.Semiring

Methods

pure :: a -> Prod a

(<*>) :: Prod (a -> b) -> Prod a -> Prod b

liftA2 :: (a -> b -> c) -> Prod a -> Prod b -> Prod c

(*>) :: Prod a -> Prod b -> Prod b

(<*) :: Prod a -> Prod b -> Prod a

Bounded a => Bounded (Prod a)

Defined in Data.Semiring

Methods

minBound :: Prod a

maxBound :: Prod a

Eq a => Eq (Prod a)

Defined in Data.Semiring

Methods

(==) :: Prod a -> Prod a -> Bool

(/=) :: Prod a -> Prod a -> Bool

Ord a => Ord (Prod a)

Defined in Data.Semiring

Methods

compare :: Prod a -> Prod a -> Ordering

(<) :: Prod a -> Prod a -> Bool

(<=) :: Prod a -> Prod a -> Bool

(>) :: Prod a -> Prod a -> Bool

(>=) :: Prod a -> Prod a -> Bool

max :: Prod a -> Prod a -> Prod a

min :: Prod a -> Prod a -> Prod a

Show a => Show (Prod a)

Defined in Data.Semiring

Methods

showsPrec :: Int -> Prod a -> ShowS

show :: Prod a -> String

showList :: [Prod a] -> ShowS

Generic (Prod a)

Defined in Data.Semiring

Associated Types

type Rep (Prod a) :: Type -> Type

Methods

from :: Prod a -> Rep (Prod a) x

to :: Rep (Prod a) x -> Prod a

Semiring a => Semigroup (Prod a)

Defined in Data.Semiring

Methods

(<>) :: Prod a -> Prod a -> Prod a

sconcat :: NonEmpty (Prod a) -> Prod a

stimes :: Integral b => b -> Prod a -> Prod a

(Monoid a, Semiring a) => Monoid (Prod a)

Defined in Data.Semiring

Methods

mempty :: Prod a

mappend :: Prod a -> Prod a -> Prod a

mconcat :: [Prod a] -> Prod a

Generic1 Prod

Defined in Data.Semiring

Associated Types

type Rep1 Prod :: k -> Type

Methods

from1 :: Prod a -> Rep1 Prod a

to1 :: Rep1 Prod a -> Prod a

type Rep (Prod a)

Defined in Data.Semiring

type Rep (Prod a) = D1 (MetaData "Prod" "Data.Semiring" "rings-0.0.1-ENwDaj1sjwXLe2A9n0ZKRO" True) (C1 (MetaCons "Prod" PrefixI True) (S1 (MetaSel (Just "getProd") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

type Rep1 Prod

Defined in Data.Semiring

type Rep1 Prod = D1 (MetaData "Prod" "Data.Semiring" "rings-0.0.1-ENwDaj1sjwXLe2A9n0ZKRO" True) (C1 (MetaCons "Prod" PrefixI True) (S1 (MetaSel (Just "getProd") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1))