Math.LinearRecursive.Monad

A monad to calculate linear recursive sequence efficiently. Matrix multiplication and fast exponentiation algorithm are used to speed up calculating the number with particular index in the sequence. This library also provides a monadic DSL to describe the sequence.

As an example, here is the fibonacci sequence

fib = do
    [f0, f1] <- newVariables [1, 1]
    f0 <:- f0 <+> f1
    return f1

>>> map (runLinearRecursive fib) [0..10]
[1,1,2,3,5,8,13,21,34,55,89]

Vector

vector types

class VectorLike v where

represents vector type class, there are two instances:

Vector

General purpose vector.

Vector1

Unit vector in vector space.

Methods

toVector :: (Eq a, Num a) => v a -> Vector a

Instances

VectorLike Vector1

VectorLike Vector

type LinearCombination = Vector

A vector represents linear combination of several variables.

type Variable = Vector1

An unit vector represents dependence on a particular variable.

vector operators and constant

(<+>) :: (Eq a, Num a, VectorLike v1, VectorLike v2) => v1 a -> v2 a -> Vector a

Vector addition, a <+> b represents sum of a and b.

(<->) :: (Eq a, Num a, VectorLike v1, VectorLike v2) => v1 a -> v2 a -> Vector a

Vector subtraction, a <-> b represents difference of a and b

(<*) :: (Eq a, Num a, VectorLike v) => a -> v a -> Vector a

Left-side scalar multiplication, s <* a is a scaled by s. For example, 1 <* a equals to a, 2 <* a equals to a+a

(*>) :: (Eq a, Num a, VectorLike v) => v a -> a -> Vector a

Right-side scalar multiplication, a *> s is a scaled by s.

zeroVector :: (Eq a, Num a) => Vector a

The zero vector.

Polynomial

data Polynomial a

Instances

Eq a => Eq (Polynomial a)

(Eq a, Num a) => Num (Polynomial a)

(Show a, Eq a, Num a) => Show (Polynomial a)

x :: (Eq a, Num a) => Polynomial a

Monad

data LinearRecursive a b

The monad to specify the calculation of next number of a linear recursive sequence.

All linear recursive sequences can be generated by iteration, the next number can be represented by linear combination of some previous numbers. This can be regarded as linear transformation between states, and it's actually multiply a transform matrix.

In order to formalize and simply this procedure, this monad use mutable-like variables to denote the states, and mutable-like assignment to denote the transform matrix.

To evaluate this sequence, the monad will be simulated step by step, after each step, all variable will be updated. Besides, if the monad returns a LinearCombination, a number will be generated each step. (well, actual calculation uses fast exponentiation algorithm to speed up this calculation)

Instances

Num a => Monad (LinearRecursive a)

Num a => Functor (LinearRecursive a)

newVariable :: (Eq a, Num a) => a -> LinearRecursive a (Variable a)

Declare a new variable, with its initial value (the value before step 0).

test = do
    v <- newVariable 1
    v <:- v <+> v
    return v

>>> map (runLinearRecursive test) [0..10]
[1,2,4,8,16,32,64,128,256,512,1024]

newVariables :: (Eq a, Num a) => [a] -> LinearRecursive a [Variable a]

Declare a new sequence, with their initial value.

After each step, each variable except the first one will be assigned with the value of its predecessor variable before this turn.

It's not encouraged to assign any value to the variables other than the first one.

test = do
     [v1, v2, v3] <- newVariables [1,2,3]
     v1 <:- v3
     return v3

>>> map (runLinearRecursive test) [0..10]
[3,2,1,3,2,1,3,2,1,3,2]

(<:-) :: (Eq a, Num a, VectorLike v) => Variable a -> v a -> LinearRecursive a ()

Variable assignment. v <:- a replace variable v with a after this step. If there are multiple assignments to one variable, only the last one counts.

(<+-) :: (Eq a, Num a, VectorLike v) => Variable a -> v a -> LinearRecursive a ()

Variable accumulated assignment. v <+- a replace variable v with v <+> a.

Be aware that v will be zero before any assignment.

runLinearRecursive :: (Eq a, Num a, Integral b, VectorLike v) => LinearRecursive a (v a) -> b -> a

O(v^3 * log n), where v is the number of variables, and n is steps to simulate.

runLinearRecursive m n simulate the monad by n steps, and return the actual value denoted by returned LinearCombination.

n must be non-negative.

simulateLinearRecursive :: (Eq a, Num a, VectorLike v) => LinearRecursive a (v a) -> [a]

O(v^2 * n). similar to runLinearRecursive, but return an infinite list instead of a particular index.

Utility

getConstant :: (Eq a, Num a) => a -> LinearRecursive a (LinearCombination a)

return a constent number. Use one extra variable.

>>> map (runLinearRecursive (getConstant 3)) [0..10]
[3,3,3,3,3,3,3,3,3,3,3]

getPartialSum :: (Eq a, Num a) => LinearCombination a -> LinearRecursive a (LinearCombination a)

return sum of a linear combination in steps before current one. Use one extra variable.

>>> map (runLinearRecursive (getConstant 3 >>= getPartialSum)) [0..10]
[0,3,6,9,12,15,18,21,24,27,30]

getStep :: (Eq a, Num a) => LinearRecursive a (LinearCombination a)

return the current step number. Use two extra variables.

>>> map (runLinearRecursive getStep) [0..10]
[0,1,2,3,4,5,6,7,8,9,10]

getPowerOf :: (Eq a, Num a) => a -> LinearRecursive a (LinearCombination a)

getPowerOf a return power of a with order equal to current step number. Use one extra variable.

>>> map (runLinearRecursive (getPowerOf 3)) [0..10]
[1,3,9,27,81,243,729,2187,6561,19683,59049]

getPolynomial :: (Eq a, Num a) => Polynomial a -> LinearRecursive a (LinearCombination a)

getPolynomial poly evaluate polynomial poly with variable x replaced by current step number. Use n extra variables, where n is the degree of poly

>>> map (runLinearRecursive (getPolynomial ((x+1)^2))) [0..10]
[1,4,9,16,25,36,49,64,81,100,121]

getPartialSumWith :: (Eq a, Num a, VectorLike v) => Polynomial a -> v a -> LinearRecursive a (LinearCombination a)