monad-lrs-0.0.1: a monad to calculate linear recursive sequence

Portabilityportable
Stabilityexperimental
Maintainerbjin1990+haskell@gmail.com

Math.LinearRecursive.Monad

Contents

Description

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]

Synopsis

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.

Methods

toVector :: Num a => v a -> Vector aSource

Instances

VectorLike Vector1 
VectorLike Vector 

type LinearCombination = VectorSource

A vector represents linear combination of several variables.

type Variable = Vector1Source

An unit vector represents dependence on a particular variable.

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.

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)

Instances

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
>>> map (runLinearRecursive test) [0..10]
[1,2,4,8,16,32,64,128,256,512,1024]

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
>>> map (runLinearRecursive test) [0..10]
[3,2,1,3,2,1,3,2,1,3,2]

(<:-) :: (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.

Utility

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

return a constent number.

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

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

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

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

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

return the current step number.

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

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

getPowerOf a return power of a with order equal to current step number.

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