Math.TriangularNumbers

Triangular numbers and various helper functions.

Main use is for linearization of triangular array indexing.

Triangular numbers: @ T_n = Σ_{k=1)^n k = 1 + 2 + 3 + ... + n =

n * (n+1) / 2 = (n+1) choose 2 @

Documentation

triangularNumber :: Int -> Int

Triangular numbers.

https://oeis.org/A000217

linearizeUppertri :: (Int, Int) -> Int

Size of an upper triangle starting at i and ending at j. "(0,N)" what be the normal thing to use.

toLinear :: Int -> (Int, Int) -> Int

Subword indexing. Given the longest subword and the current subword, calculate a linear index "[0,..]". "(l,n)" in this case means "l"ower bound, length "n". And "(i,j)" is the normal index.

0 1 2 3    <- j = ...

0 1 2 3    i=0
_ 4 5 6    i=1
_ _ 7 8    i=2
      9    i=3

i=2, j=3  -> (4+1) * i - tri i + j

_
_ _  the triangular number to subtract.

fromLinear :: Int -> Int -> (Int, Int)

Linear index to paired.

We have indices in [0,N], and linear index k.

(N+1)*i - (i*(i+1)/2) + j == K