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]
- class VectorLike v where
- type LinearCombination = Vector
- type Variable = Vector1
- (<+>) :: (Num a, VectorLike v1, VectorLike v2) => v1 a -> v2 a -> Vector a
- (<->) :: (Num a, VectorLike v1, VectorLike v2) => v1 a -> v2 a -> Vector a
- (<*) :: (Num a, VectorLike v) => a -> v a -> Vector a
- (*>) :: (Num a, VectorLike v) => v a -> a -> Vector a
- zeroVector :: Num a => Vector a
- data Polynomial a
- x :: Num a => Polynomial a
- data LinearRecursive a b
- newVariable :: Num a => a -> LinearRecursive a (Variable a)
- newVariables :: Num a => [a] -> LinearRecursive a [Variable a]
- (<:-) :: (Num a, VectorLike v) => Variable a -> v a -> LinearRecursive a ()
- (<+-) :: (Num a, VectorLike v) => Variable a -> v a -> LinearRecursive a ()
- runLinearRecursive :: (Num a, Integral b, VectorLike v) => LinearRecursive a (v a) -> b -> a
- simulateLinearRecursive :: (Num a, VectorLike v) => LinearRecursive a (v a) -> [a]
- getConstant :: Num a => a -> LinearRecursive a (LinearCombination a)
- getPartialSum :: Num a => LinearCombination a -> LinearRecursive a (LinearCombination a)
- getStep :: Num a => LinearRecursive a (LinearCombination a)
- getPowerOf :: Num a => a -> LinearRecursive a (LinearCombination a)
- getPolynomial :: Num a => Polynomial a -> LinearRecursive a (LinearCombination a)
- getPartialSumWith :: (Num a, VectorLike v) => Polynomial a -> v a -> LinearRecursive a (LinearCombination a)
represents vector type class, there are two instances:
- General purpose vector.
- Unit vector in vector space.
vector operators and constant
a <+> b represents sum of
a <-> b represents difference of
Left-side scalar multiplication,
s <* a is
a scaled by
1 <* a equals to
2 <* a equals to
Right-side scalar multiplication,
a *> s is
a scaled by
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)
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]
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]
v <:- a replace variable
a after this step.
If there are multiple assignments to one variable, only the last one counts.
Variable accumulated assignment.
v <+- a replace variable
v <+> a.
Be aware that
v will be zero before any assignment.
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
n must be non-negative.
O(v^2 * n). similar to
runLinearRecursive, but return an infinite list instead of a particular index.
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]
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]
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 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 poly evaluate polynomial
poly with variable
x replaced by current step number.
n extra variables, where
n is the degree of
map (runLinearRecursive (getPolynomial ((x+1)^2))) [0..10][1,4,9,16,25,36,49,64,81,100,121]