https://en.wikipedia.org/wiki/Matrix_exponential

mapping operation for closures. Note we cannot make this a Functor instance due to constraint in the type.

operation for producing a closure out of single element.

Monadic bind operation for closures, again cannot be made instance of Monad.

https://en.wikipedia.org/wiki/Power_iteration

https://en.wikipedia.org/wiki/Taylor_series

This implementation of infinite identity matrix requires Integral constraint. it is not as efficient as identity, but is implemented using generating functions.

stream_diagonal is the "depth-first" traversal over two-dimensional streams, where the choice always goes to diagonal elements.

stream_diagonal (matrix f x y) == liftA2 f x y

sum of a stream elements.

bind diagonal element and horizontal and vertical strip

stream matrix with a specified diagonal, other elements are zero.

adding a row to a matrix.

adding a column to a matrix.

For streams \(b = (b_i)_{i\in{\mathbf{N}}}\) and \(a = (a_i)_{i\in{\mathbf{N}}}\) representing generating functions \(g(z) = \sum_{i=0}^{\infty}{b_iz^i}\) and \(f(z) = \sum_{i=1}^{\infty}{a_iz^i}\) where \(a_0 = 0\), this computes: \[(g \circ f)(z) = g(f(z)) = \sum_{i=0}^{\infty}{b_i(f(z))^i} = \sum_{i=0}^{\infty}(b_i(\sum_{j=1}^{\infty}{a_jz^j})^i)\]

Note that identity of composition on the right is s_z. That is, \(s \circ s_z = s\). https://en.wikipedia.org/wiki/Formal_power_series

computes average to normalize the matrix

distance_product a b computes \[l_k = \sqrt{\sum_{i+j=k}a_ib_j^{*}}\].

https://en.wikipedia.org/wiki/LU_decomposition This has some bug still, l_matrix computation gets stuck.

fold over streams

the function studied in the Collatz conjecture.

\[[sumSeq(f)(n)]_j = \sum_{i=n}^{n+j+1}f(i)\]

product_stream produce from a stream \([a_0,a_1,a_2,...]\) a stream \([a_0,a_0a_1,a_0a_1a_2,a_0a_1a_2a_3,...]\)

sum_stream will produce from a stream \([a_0,a_1,a_2,...]\) a stream \([a_0,a_0+a_1,a_0+a_1+a_2,...]\).

if f in cobind is a fixed-point free function, then this will find a stream that is not an element of any of the streams.

Everything but a diagonal

stream_matrix creates matrix from a diagonal and a codiagonal

this surprising function builds a two-dimensional infinite matrix from a diagonal, an upper triangular matrix and a lower triangular matrix. Notice the input matrices have no zero entries, rather indices for the triangular matrices are bijectively mapped to indices of the result matrix. This is only possible for infinite matrices. It's even more surprising once it's realised that two-dimensional infinite matrices can be bijectively described as an infinite binary tree of one-dimensional streams.

isomorphism of infinite matrices that splits along diagonal.

this matrix contains 0 on diagonal, 1 on diagonal of upper and lower triangular matrices and so on. Every element of the two-dimensional matrix gets an index.

codiagonals operation implemented natively on lists. This is not efficient due to use of list append (++) operation, which is linear-time operation. Use codiagonals function instead.

This is faster than the version for lists, because the suffix computation on Seq is constant time rather than linear. However, strictness seems to behave differently.

The codiagonals function will divide a two-dimensional stream of streams (where elements are \(e_{(i,j)}\) into a stream of lists

\(l_k\) where \(l_k = [e_{(i,j)} | i \leftarrow naturals, j \leftarrow naturals, i+j = k]\)

The indices in the streams are closely related to "Cantor pairing function" (which is a bijection)

f :: (N,N) -> N
f(x,y) = (x+y)(x+y+1)/2 + x

Note that the list at each element of the resulting stream is of finite (but increasing) size. The order in each list is such that the diagonal elements are at the center of (the every second) list.

It is possible to think of this as "breadth-first" traversal over two-dimensional streams.

 d   x xr0 xr1  xr2 ..
 y   d' x' xr0' xr1' ..
 yr0 y'
 yr1 yr0'
 yr2 yr1'
 ..

There is symmetry between primed and unprimed (e.g. d and d') towards the diagonal.

The resulting lists would be: [d], [x,y], [xr0,d',yr0], [xr1,x',y',yr1],...

for uncodiagonals, the i'th list element of the input stream must have length i.

uncodiagonals ([a] `Pre` [b,c] `Pre` [d,e,f] ...) == Pre (a `Pre` c `Pre` f ...) $ Pre (b `Pre` e `Pre` ...) $ Pre (d `Pre` ... ) $ ...

https://en.wikipedia.org/wiki/Formal_power_series

lower_triangle takes lower half of a two-dimensional stream split at diagonal.

upper_triangle takes upper half of a two-dimensional stream split at diagonal.

concatenate a stream of lists to a stream of elements

cojoin is "better" version of join for streams. cojoin does not satisfy monad laws (Right identity and associativity do not hold.). It eventually produces every element of the original two-dimensional stream. It first produces all elements \(e_{(i,j)}\) where \(i+j=k\) and \(k\) increasing.

naturals |*| naturals == (0,0),   [note sum=0]
                         (0,1),(1,0),  [note sum=1]
                         (0,2),(2,0),(1,1),  [note sum=2]
                         (0,3),(3,0),(1,2),(2,1),  [note sum=3]
                         (0,4),(4,0),(1,3),(3,1),(2,2),  [note sum=4]
                          ...  

For a better "bind" operation, there exists (>>!=), which produces the following result (note duplicates):

naturals >>!= \x -> naturals >>!= \y -> return (x,y)
== (0,0),
  (0,0),(1,0),
     (0,1),(1,0),(2,0),
  (0,0),(1,1),(2,0),(3,0),
    (0,1),(1,0),(2,1),(3,0),(4,0),
      (0,2),(1,1),(2,0),(3,1),(4,0),(5,0),
  (0,0),(1,2),(2,1),(3,0),(4,1),(5,0),(6,0),
    (0,1),(1,0),(2,2),(3,1),(4,0),(5,1),(6,0),(7,0),
      (0,2),(1,1),(2,0),(3,2),(4,1),(5,0),(6,1),(7,0),(8,0),
       (0,3),(1,2),(2,1),(3,0),(4,2),(5,1),(6,0),(7,1),(8,0),(9,0),
  ...

The (>!=) is like binding, but the results are packaged to a finite list. Again note duplicates.

naturals >!= \x -> naturals >!= \y -> return (x,y)
== [[(0,0)]
  ],
  [[(0,0),(0,1)],
   [(1,0)]
  ],
  [[(0,0),(0,1),(0,2)],
   [(1,0),(1,1)],
   [(2,0)],
  ],
  [[(0,0),(0,1),(0,2),(0,3)],
 [(1,0),(1,1),(1,2)],
 [(2,0),(2,1)],
 [(3,0)]
],
...

A stream of integers. This is specialized version of naturals for integers

A stream of increasing numbers starting from 0

A stream of increasing numbers starting from a given number.

A stream of increasing numbers starting from 1

This is the variable used in generating functions. Note that in multidimensional streams, this is the variable associated with the largest dimension.

The variable associated with second largest dimension:

variable associated with third largest dimension

For a stream of terms \(a=[a_0,a_1,a_2,...]\), and \(x=[x_0,x_1,x_2,...]\), 'approximate_sums a x' computes \[\sum_{i=0}^n{a_ix_i^i}\], where n is the index to the result stream.

exponential_stream computes \(s_{i} = {{1}\over{i!}}\). notice that euler's constant \(e = \sum_{i=0}^{\infty}{1\over{i!}}\). therefore "sum_stream exponential_stream" produces approximations to e.

https://en.wikipedia.org/wiki/Trigonometric_functions

https://en.wikipedia.org/wiki/Trigonometric_functions

https://en.wikipedia.org/wiki/Trigonometric_functions

https://en.wikipedia.org/wiki/Trigonometric_functions

both reciprocal and inversion are the inverse of a Cauchy product. see http://en.wikipedia.org/wiki/Formal_power_series

reciprocal s * s == unit_product

see http://en.wikipedia.org/wiki/Formal_power_series

inversion s * s == unit_product.

see http://en.wikipedia.org/wiki/Formal_power_series

unit_product is the unit element of (*) for streams.

zero is the unit element of (+) for streams

add a list as a prefix to a stream

The cycle operation is better than fromList, if the list is infinite, because it will ensure the result is infinite (and no Num constraint is needed).

filter f s for streams does not terminate, if the input stream never contains any elements e for which f e == True.

interleave_count is like interleave except that i elements of each stream are taken from each stream at each stream.

interleave two streams such that even indexed elements of result are from first input stream and odd indexed elements of result are from second stream.

version of interleave that produces either instances

split a stream, elements with even index go to first result stream, rest to second.

three stream interleave

three stream uninterleave

interleave a non-empty list of streams.

uninterleave to an indicated number of streams.

interleave a queue of streams.

uninterleave to a queue of streams

drop a specified number of elements from beginning of a stream.

take a specified number of elements from the beginning of the stream.

split a stream from index.

count how many elements from a beginning of a stream satisfy a predicate.

take elements from a stream while predicate is true.

drop elements from a stream while predicate is true.

The cycle operation is better than fromList for converting a list to stream, if the list is infinite, because it will ensure the result is infinite.

use elements of a queue to produce an infinite stream.

stirling numbers are the numbers obtained from \(z (z+1) ... (z+n)\)

stream of powers of a given integer for fractional items

stream of powers of a given integer for integral items.

https://en.wikipedia.org/wiki/Generating_function. \[EGF(z \mapsto \sum_{k=0}^{\infty}{s_kz^k}) = z \mapsto \sum_{k=0}^{\infty}{{1\over{k!}}{s_kz^k}}\].

https://en.wikipedia.org/wiki/Generating_function

input stream elements are raised to n'th power.

input element is raised to successive increasing powers (first element of the stream is \(n^1\))

The elements of pascal triangle are binomial coefficients.

http://en.wikipedia.org/wiki/Binomial_coefficient

http://en.wikipedia.org/wiki/Catalan_number

http://en.wikipedia.org/wiki/Catalan_number of floating elements.

pascal triangle, elements are binomial coefficients. https://en.wikipedia.org/wiki/Pascal%27s_triangle this expands "down" (leaving zero elements)

pascal triangle which expands towards the diagonal

computes \((a + b)^n\) for all n, using binomial coefficients. Hint: use z in one of the argument. pascal_triangle == Matrix $ polynomial_powers 1 z Note: stream_powers can sometimes be a more efficient alternative.

a stream of fibonacci numbers, each element is a sum of two previous elements. 1,1,2,3,5,8,13,21,34,55,...

Triangular numbers. https://en.wikipedia.org/wiki/Generating_function 1,3,6,10,15,21,28,36,...

1.0,-1.0,1.0,-1.0,...

1.0,0.0,1.0,0.0,1.0,0.0,...

stream of odd integers

This is an ideal of the set of positive integers, usually denoted \(nZ^+\), e.g. set of positive integers divisible by n.

This function produces the equivalence class of m mod n. The numbers produced by the stream are considered as equivalent by the equivalence class.

peirces_triangle is the number of set partitions. From Knuth: The art of Computer Programming, Volume 4 "Generating all combinations and partitions", page 64.

peirces_triangle is the number of set partitions. From Knuth: The art of Computer Programming, Volume 4 "Generating all combinations and partitions", page 64.

https://en.wikipedia.org/wiki/Injective_function?wprof=sfla1 falling factorial powers specify number of injective functions from domain with specified number of elements to codomain with specified number of elements. https://en.wikipedia.org/wiki/Falling_and_rising_factorials?wprof=sfla1

Be careful about indices here, could cause off-by-one error!

bell numbers https://en.wikipedia.org/wiki/Bell_number. also see Knuth: The Art of Computer Programming, Volume 4.

newton's method of computing square root approximations:

This is an implementation of Floyd's cycle-finding algorithm http://en.wikipedia.org/wiki/Cycle_detection.

Stream of prime numbers generated using a sieve.

https://wiki.haskell.org/Prime_numbers

derivative calculates the derivative of the generating function. https://en.wikipedia.org/wiki/Generating_function \[{\rm{derivative}}({\bf{a}})_i = {\bf{b}}_i = (i+1){\bf{a}}_{i+1}\] \[f(z) = \sum_{i=0}^{\infty}{\bf{a}}_iz^i\] \[f'(z) = \sum_{i=0}^{\infty}{\bf{b}}_iz^i = {d\over{dz}} \sum_{i=0}^{\infty}{\bf{a}}_iz^i = \sum_{i=0}^{\infty}(i+1){\bf{a}}_{i+1}z^i\]

for two monotone streams, compares whether all elements of the first stream are also in the second stream. produces True for every element of the first stream, if that element is part of the second stream. produces error if the streams are not monotone.

Square root algorithm is from Simpson: Power Series, http://caps.gsfc.nasa.gov/simpson/ref/series.pdf

derivate a stream function at a particular point.

https://en.wikipedia.org/wiki/Pi

http://en.wikipedia.org/wiki/Twin_prime

http://en.wikipedia.org/wiki/Formula_for_primes

https://en.wikipedia.org/wiki/Bernoulli_number

https://en.wikipedia.org/wiki/Bernoulli_number

https://en.wikipedia.org/wiki/Bernoulli_polynomial

https://en.wikipedia.org/wiki/Legendre_polynomials