Portability | portable |
---|---|

Stability | experimental |

Maintainer | bjin1990+haskell@gmail.com |

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

`>>>`

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

- 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)

# Vector

## vector types

class VectorLike v whereSource

represents vector type class, there are two instances:

`Vector`

- General purpose vector.
`Vector1`

- Unit vector in vector space.

VectorLike Vector1 | |

VectorLike Vector |

type LinearCombination = VectorSource

A vector represents linear combination of several variables.

## vector operators and constant

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

Vector addition, `a <+> b`

represents sum of `a`

and `b`

.

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

Vector subtraction, `a <-> b`

represents difference of `a`

and `b`

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

Left-side scalar multiplication, `s <* a`

is `a`

scaled by `s`

.
For example, `1 <* a`

equals to `a`

, `2 <* a`

equals to `a+a`

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

Right-side scalar multiplication, `a *> s`

is `a`

scaled by `s`

.

zeroVector :: Num a => Vector aSource

The zero vector.

# Polynomial

data Polynomial a Source

Num a => Eq (Polynomial a) | |

Num a => Num (Polynomial a) | |

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

x :: Num a => Polynomial aSource

# Monad

data LinearRecursive a b Source

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)

Num a => Monad (LinearRecursive a) | |

Num a => Functor (LinearRecursive a) |

newVariable :: Num a => a -> LinearRecursive a (Variable a)Source

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

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

`>>>`

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

newVariables :: Num a => [a] -> LinearRecursive a [Variable a]Source

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

`>>>`

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

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

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.

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

Variable accumulated assignment. `v <+- a`

replace variable `v`

with `v <+> a`

.

Be aware that `v`

will be zero before any assignment.

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

*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 :: (Num a, VectorLike v) => LinearRecursive a (v a) -> [a]Source

*O(v^2 * n)*. similar to `runLinearRecursive`

, but return an infinite list instead of a particular index.

# Utility

getConstant :: Num a => a -> LinearRecursive a (LinearCombination a)Source

return a constent number. Use one extra variable.

`>>>`

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

getPartialSum :: Num a => LinearCombination a -> LinearRecursive a (LinearCombination a)Source

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

`>>>`

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

getStep :: Num a => LinearRecursive a (LinearCombination a)Source

return the current step number. Use two extra variables.

`>>>`

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

getPowerOf :: Num a => a -> LinearRecursive a (LinearCombination a)Source

`getPowerOf a`

return power of `a`

with order equal to current step number.
Use one extra variable.

`>>>`

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

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

`getPolynomial poly`

evaluate polynomial `poly`

with variable `x`

replaced by current step number.
Use `n`

extra variables, where `n`

is the degree of `poly`

`>>>`

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

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