Markov

Three type classes for deterministically analyzing Markov chains with known parameters. Markov0 is intended to list possible outcomes, Markov should allow for more sophisticated analysis, and MultiMarkov is intended to make implementing hidden Markov models easier. See Examples for examples. See README for a detailed description.

Markov0

class Eq m => Markov0 m where

A basic implementation of Markov chains.

Minimal complete definition

transition0

Methods

transition0 :: m -> [m -> m]

The transition functions from a state.

step0 :: m -> [m]

chain0 :: [m] -> [[m]]

Iterated steps.

Instances

Markov0 Simple

Defined in Markov.Examples

Methods

transition0 :: Simple -> [Simple -> Simple]

step0 :: Simple -> [Simple]

chain0 :: [Simple] -> [[Simple]]

Markov

class (Combine t, Grouping t, Grouping m, Monoid t) => Markov t m where

An implementation of Markov chains. To speed up chain, try instead:

chain = DL.iterate' $ map summarize' . NE.group . DL.sort . concatMap step
    where summarize' xs@((_,b)NE.:|_) = (summarize . fmap fst $ xs, b)

Minimal complete definition

transition

Methods

transition :: m -> [(t, m -> m)]

step :: (t, m) -> [(t, m)]

chain :: [(t, m)] -> [[(t, m)]]

Instances

Markov (Product Double) FillBin

Defined in Markov.Examples

Methods

transition :: FillBin -> [(Product Double, FillBin -> FillBin)]

step :: (Product Double, FillBin) -> [(Product Double, FillBin)]

chain :: [(Product Double, FillBin)] -> [[(Product Double, FillBin)]]

Markov (Product Double) Tidal

Defined in Markov.Examples

Methods

transition :: Tidal -> [(Product Double, Tidal -> Tidal)]

step :: (Product Double, Tidal) -> [(Product Double, Tidal)]

chain :: [(Product Double, Tidal)] -> [[(Product Double, Tidal)]]

Markov (Product Double) Urn

Defined in Markov.Examples

Methods

transition :: Urn -> [(Product Double, Urn -> Urn)]

step :: (Product Double, Urn) -> [(Product Double, Urn)]

chain :: [(Product Double, Urn)] -> [[(Product Double, Urn)]]

Markov (Product Double) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Product Double, Simple -> Simple)]

step :: (Product Double, Simple) -> [(Product Double, Simple)]

chain :: [(Product Double, Simple)] -> [[(Product Double, Simple)]]

Markov (Product Double) FromMatrix

Defined in Markov.Examples

Methods

transition :: FromMatrix -> [(Product Double, FromMatrix -> FromMatrix)]

step :: (Product Double, FromMatrix) -> [(Product Double, FromMatrix)]

chain :: [(Product Double, FromMatrix)] -> [[(Product Double, FromMatrix)]]

Markov (Product Int) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Product Int, Simple -> Simple)]

step :: (Product Int, Simple) -> [(Product Int, Simple)]

chain :: [(Product Int, Simple)] -> [[(Product Int, Simple)]]

Markov (Sum Int) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Sum Int, Simple -> Simple)]

step :: (Sum Int, Simple) -> [(Sum Int, Simple)]

chain :: [(Sum Int, Simple)] -> [[(Sum Int, Simple)]]

Markov (Sum Int, Product Rational) Extinction

Defined in Markov.Examples

Methods

transition :: Extinction -> [((Sum Int, Product Rational), Extinction -> Extinction)]

step :: ((Sum Int, Product Rational), Extinction) -> [((Sum Int, Product Rational), Extinction)]

chain :: [((Sum Int, Product Rational), Extinction)] -> [[((Sum Int, Product Rational), Extinction)]]

MultiMarkov

randomProduct :: (Real a, MonadRandom m) => [(a, b)] -> m (a, b)

Randomly choose from a list by probability.

randomPath :: (Markov a b, Real a, RandomGen g) => (a, b) -> g -> [(a, b)]

Returns a single realization of a Markov chain.

class (Combine m, Grouping m, Semigroup m) => MultiMarkov m where

An implementation of Markov chains that allows multi-transition steps.

Minimal complete definition

multiTransition

Methods

multiTransition :: m -> [m -> [m]]

multiStep :: m -> [m]

multiChain :: [m] -> [[m]]

Instances

MultiMarkov ((Product Rational :* Merge String) :* Room)

Defined in Markov.Examples

Methods

multiTransition :: ((Product Rational :* Merge String) :* Room) -> [((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]]

multiStep :: ((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]

multiChain :: [(Product Rational :* Merge String) :* Room] -> [[(Product Rational :* Merge String) :* Room]]

MultiMarkov ((Sum Int :* Product Rational) :* Extinction)

Defined in Markov.Examples

Methods

multiTransition :: ((Sum Int :* Product Rational) :* Extinction) -> [((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]]

multiStep :: ((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]

multiChain :: [(Sum Int :* Product Rational) :* Extinction] -> [[(Sum Int :* Product Rational) :* Extinction]]

Combine

class Combine a where

Within equivalence classes, combine should be associative, commutative, and should be idempotent up to equivalence. I.e. if x == y == z,

(x `combine` y) `combine` z = x `combine` (y `combine` z)

x `combine` y = y `combine` x

x `combine` x == x

Minimal complete definition

combine

Methods

combine :: a -> a -> a

summarize :: NonEmpty a -> a

Instances

Combine Room

Defined in Markov.Examples

Methods

combine :: Room -> Room -> Room

summarize :: NonEmpty Room -> Room

Combine Extinction

Defined in Markov.Examples

Methods

combine :: Extinction -> Extinction -> Extinction

summarize :: NonEmpty Extinction -> Extinction

Num a => Combine (Product a)

Defined in Markov

Methods

combine :: Product a -> Product a -> Product a

summarize :: NonEmpty (Product a) -> Product a

Combine (Sum a)

Defined in Markov

Methods

combine :: Sum a -> Sum a -> Sum a

summarize :: NonEmpty (Sum a) -> Sum a

Combine (Merge a)

Defined in Markov

Methods

combine :: Merge a -> Merge a -> Merge a

summarize :: NonEmpty (Merge a) -> Merge a

(Combine a, Combine b) => Combine (a, b)

Defined in Markov

Methods

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

summarize :: NonEmpty (a, b) -> (a, b)

(Combine a, Combine b, Combine c) => Combine (a, b, c)

Defined in Markov

Methods

combine :: (a, b, c) -> (a, b, c) -> (a, b, c)

summarize :: NonEmpty (a, b, c) -> (a, b, c)

newtype Merge a

Values from a Monoid which have the respective binary operation applied each step. E.g., strings with concatenation.

Constructors

Merge a

Instances

Enum a => Enum (Merge a)

Defined in Markov

Methods

succ :: Merge a -> Merge a

pred :: Merge a -> Merge a

toEnum :: Int -> Merge a

fromEnum :: Merge a -> Int

enumFrom :: Merge a -> [Merge a]

enumFromThen :: Merge a -> Merge a -> [Merge a]

enumFromTo :: Merge a -> Merge a -> [Merge a]

enumFromThenTo :: Merge a -> Merge a -> Merge a -> [Merge a]

Eq a => Eq (Merge a)

Defined in Markov

Methods

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

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

Fractional a => Fractional (Merge a)

Defined in Markov

Methods

(/) :: Merge a -> Merge a -> Merge a

recip :: Merge a -> Merge a

fromRational :: Rational -> Merge a

Num a => Num (Merge a)

Defined in Markov

Methods

(+) :: Merge a -> Merge a -> Merge a

(-) :: Merge a -> Merge a -> Merge a

(*) :: Merge a -> Merge a -> Merge a

negate :: Merge a -> Merge a

abs :: Merge a -> Merge a

signum :: Merge a -> Merge a

fromInteger :: Integer -> Merge a

Show a => Show (Merge a)

Defined in Markov

Methods

showsPrec :: Int -> Merge a -> ShowS

show :: Merge a -> String

showList :: [Merge a] -> ShowS

Generic (Merge a)

Defined in Markov

Associated Types

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

Methods

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

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

Semigroup a => Semigroup (Merge a)

Defined in Markov

Methods

(<>) :: Merge a -> Merge a -> Merge a

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

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

Monoid a => Monoid (Merge a)

Defined in Markov

Methods

mempty :: Merge a

mappend :: Merge a -> Merge a -> Merge a

mconcat :: [Merge a] -> Merge a

Grouping a => Grouping (Merge a)

Defined in Markov

Methods

grouping :: Group (Merge a)

Combine (Merge a)

Defined in Markov

Methods

combine :: Merge a -> Merge a -> Merge a

summarize :: NonEmpty (Merge a) -> Merge a

MultiMarkov ((Product Rational :* Merge String) :* Room)

Defined in Markov.Examples

Methods

multiTransition :: ((Product Rational :* Merge String) :* Room) -> [((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]]

multiStep :: ((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]

multiChain :: [(Product Rational :* Merge String) :* Room] -> [[(Product Rational :* Merge String) :* Room]]

type Rep (Merge a)

Defined in Markov

type Rep (Merge a) = D1 (MetaData "Merge" "Markov" "markov-realization-0.1.0-6GSvYD8yAhy2vCcDg5QqBj" True) (C1 (MetaCons "Merge" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

newtype Sum a

Values which are added each step. E.g., number of times a red ball is picked from an urn.

Constructors

Sum a

Instances

Enum a => Enum (Sum a)

Defined in Markov

Methods

succ :: Sum a -> Sum a

pred :: Sum a -> Sum a

toEnum :: Int -> Sum a

fromEnum :: Sum a -> Int

enumFrom :: Sum a -> [Sum a]

enumFromThen :: Sum a -> Sum a -> [Sum a]

enumFromTo :: Sum a -> Sum a -> [Sum a]

enumFromThenTo :: Sum a -> Sum a -> Sum a -> [Sum a]

Eq a => Eq (Sum a)

Defined in Markov

Methods

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

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

Fractional a => Fractional (Sum a)

Defined in Markov

Methods

(/) :: Sum a -> Sum a -> Sum a

recip :: Sum a -> Sum a

fromRational :: Rational -> Sum a

Num a => Num (Sum a)

Defined in Markov

Methods

(+) :: Sum a -> Sum a -> Sum a

(-) :: Sum a -> Sum a -> Sum a

(*) :: Sum a -> Sum a -> Sum a

negate :: Sum a -> Sum a

abs :: Sum a -> Sum a

signum :: Sum a -> Sum a

fromInteger :: Integer -> Sum a

Show a => Show (Sum a)

Defined in Markov

Methods

showsPrec :: Int -> Sum a -> ShowS

show :: Sum a -> String

showList :: [Sum a] -> ShowS

Generic (Sum a)

Defined in Markov

Associated Types

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

Methods

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

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

Num a => Semigroup (Sum a)

Defined in Markov

Methods

(<>) :: Sum a -> Sum a -> Sum a

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

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

Num a => Monoid (Sum a)

Defined in Markov

Methods

mempty :: Sum a

mappend :: Sum a -> Sum a -> Sum a

mconcat :: [Sum a] -> Sum a

Grouping a => Grouping (Sum a)

Defined in Markov

Methods

grouping :: Group (Sum a)

Combine (Sum a)

Defined in Markov

Methods

combine :: Sum a -> Sum a -> Sum a

summarize :: NonEmpty (Sum a) -> Sum a

Markov (Sum Int) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Sum Int, Simple -> Simple)]

step :: (Sum Int, Simple) -> [(Sum Int, Simple)]

chain :: [(Sum Int, Simple)] -> [[(Sum Int, Simple)]]

MultiMarkov ((Sum Int :* Product Rational) :* Extinction)

Defined in Markov.Examples

Methods

multiTransition :: ((Sum Int :* Product Rational) :* Extinction) -> [((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]]

multiStep :: ((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]

multiChain :: [(Sum Int :* Product Rational) :* Extinction] -> [[(Sum Int :* Product Rational) :* Extinction]]

Markov (Sum Int, Product Rational) Extinction

Defined in Markov.Examples

Methods

transition :: Extinction -> [((Sum Int, Product Rational), Extinction -> Extinction)]

step :: ((Sum Int, Product Rational), Extinction) -> [((Sum Int, Product Rational), Extinction)]

chain :: [((Sum Int, Product Rational), Extinction)] -> [[((Sum Int, Product Rational), Extinction)]]

type Rep (Sum a)

Defined in Markov

type Rep (Sum a) = D1 (MetaData "Sum" "Markov" "markov-realization-0.1.0-6GSvYD8yAhy2vCcDg5QqBj" True) (C1 (MetaCons "Sum" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

newtype Product a

Values which are multiplied each step, and combined additively for equal states. E.g., probabilities.

Constructors

Product a

Instances

Enum a => Enum (Product a)

Defined in Markov

Methods

succ :: Product a -> Product a

pred :: Product a -> Product a

toEnum :: Int -> Product a

fromEnum :: Product a -> Int

enumFrom :: Product a -> [Product a]

enumFromThen :: Product a -> Product a -> [Product a]

enumFromTo :: Product a -> Product a -> [Product a]

enumFromThenTo :: Product a -> Product a -> Product a -> [Product a]

Eq (Product a)

Defined in Markov

Methods

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

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

Fractional a => Fractional (Product a)

Defined in Markov

Methods

(/) :: Product a -> Product a -> Product a

recip :: Product a -> Product a

fromRational :: Rational -> Product a

Num a => Num (Product a)

Defined in Markov

Methods

(+) :: Product a -> Product a -> Product a

(-) :: Product a -> Product a -> Product a

(*) :: Product a -> Product a -> Product a

negate :: Product a -> Product a

abs :: Product a -> Product a

signum :: Product a -> Product a

fromInteger :: Integer -> Product a

Show a => Show (Product a)

Defined in Markov

Methods

showsPrec :: Int -> Product a -> ShowS

show :: Product a -> String

showList :: [Product a] -> ShowS

Generic (Product a)

Defined in Markov

Associated Types

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

Methods

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

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

Num a => Semigroup (Product a)

Defined in Markov

Methods

(<>) :: Product a -> Product a -> Product a

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

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

Num a => Monoid (Product a)

Defined in Markov

Methods

mempty :: Product a

mappend :: Product a -> Product a -> Product a

mconcat :: [Product a] -> Product a

Grouping (Product a)

Defined in Markov

Methods

grouping :: Group (Product a)

Num a => Combine (Product a)

Defined in Markov

Methods

combine :: Product a -> Product a -> Product a

summarize :: NonEmpty (Product a) -> Product a

Markov (Product Double) FillBin

Defined in Markov.Examples

Methods

transition :: FillBin -> [(Product Double, FillBin -> FillBin)]

step :: (Product Double, FillBin) -> [(Product Double, FillBin)]

chain :: [(Product Double, FillBin)] -> [[(Product Double, FillBin)]]

Markov (Product Double) Tidal

Defined in Markov.Examples

Methods

transition :: Tidal -> [(Product Double, Tidal -> Tidal)]

step :: (Product Double, Tidal) -> [(Product Double, Tidal)]

chain :: [(Product Double, Tidal)] -> [[(Product Double, Tidal)]]

Markov (Product Double) Urn

Defined in Markov.Examples

Methods

transition :: Urn -> [(Product Double, Urn -> Urn)]

step :: (Product Double, Urn) -> [(Product Double, Urn)]

chain :: [(Product Double, Urn)] -> [[(Product Double, Urn)]]

Markov (Product Double) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Product Double, Simple -> Simple)]

step :: (Product Double, Simple) -> [(Product Double, Simple)]

chain :: [(Product Double, Simple)] -> [[(Product Double, Simple)]]

Markov (Product Double) FromMatrix

Defined in Markov.Examples

Methods

transition :: FromMatrix -> [(Product Double, FromMatrix -> FromMatrix)]

step :: (Product Double, FromMatrix) -> [(Product Double, FromMatrix)]

chain :: [(Product Double, FromMatrix)] -> [[(Product Double, FromMatrix)]]

Markov (Product Int) Simple

Defined in Markov.Examples

Methods

transition :: Simple -> [(Product Int, Simple -> Simple)]

step :: (Product Int, Simple) -> [(Product Int, Simple)]

chain :: [(Product Int, Simple)] -> [[(Product Int, Simple)]]

MultiMarkov ((Product Rational :* Merge String) :* Room)

Defined in Markov.Examples

Methods

multiTransition :: ((Product Rational :* Merge String) :* Room) -> [((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]]

multiStep :: ((Product Rational :* Merge String) :* Room) -> [(Product Rational :* Merge String) :* Room]

multiChain :: [(Product Rational :* Merge String) :* Room] -> [[(Product Rational :* Merge String) :* Room]]

MultiMarkov ((Sum Int :* Product Rational) :* Extinction)

Defined in Markov.Examples

Methods

multiTransition :: ((Sum Int :* Product Rational) :* Extinction) -> [((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]]

multiStep :: ((Sum Int :* Product Rational) :* Extinction) -> [(Sum Int :* Product Rational) :* Extinction]

multiChain :: [(Sum Int :* Product Rational) :* Extinction] -> [[(Sum Int :* Product Rational) :* Extinction]]

Markov (Sum Int, Product Rational) Extinction

Defined in Markov.Examples

Methods

transition :: Extinction -> [((Sum Int, Product Rational), Extinction -> Extinction)]

step :: ((Sum Int, Product Rational), Extinction) -> [((Sum Int, Product Rational), Extinction)]

chain :: [((Sum Int, Product Rational), Extinction)] -> [[((Sum Int, Product Rational), Extinction)]]

type Rep (Product a)

Defined in Markov

type Rep (Product a) = D1 (MetaData "Product" "Markov" "markov-realization-0.1.0-6GSvYD8yAhy2vCcDg5QqBj" True) (C1 (MetaCons "Product" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

Misc

type (:*) a b = (a, b)

Easier way to write nested 2-tuples.

(>*<) :: a -> b -> a :* b infixl 5

Easier way to write nested 2-tuples, since a >*< b >*< c >*< d is much easier to read than (((a,b),c),d). Left associative, binds weaker than + but stronger than ==.

fromLists :: Eq b => [[a]] -> [b] -> b -> [(a, b -> b)]

Create a transition function from a transition matrix. If [[a]] is an n x n matrix, length [b] should be n.

Testing