Sequences · Integrity

This page documents library functions related to sequences.

Fibonacci

g_ ext{fib} left(, n , ight)

Generate the Fibonacci sequence up to its $n$ -th term.

Arguments

Argument	Description	Domain	Constraints	Notes
$n$	terms count	$\mathbb{Z}$	$0 < n$

Return

Value	Description	Codomain	Constraints	Notes
$\omega$	terms	$[\mathbb{N}, ...]$		Produces an empty list for invalid $n$ .

Instances

g_\text{fib}\left(0\right)-\left[\right]
g_\text{fib}\left(1\right)-\left[0\right]
g_\text{fib}\left(2\right)-\left[0,\ 1\right]
g_\text{fib}\left(3\right)-\left[0,\ 1,\ 1\right]
g_\text{fib}\left(7\right)-\left[0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8\right]
g_\text{fib}\left(13\right)-\left[0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144\right]

Implementation

egin{align*} g_ ext{fib}left(n ight) &= { nle0: left[ ight], \ &quadquad n=1: left[0 ight], \ &quadquad n=2: left[0, 1 ight], \ &quadquad operatorname{join}left(left[0, 1 ight], g_ ext{fibo}left(1, n-2 ight) ight) \ &quad } \[1em] g_ ext{fibs}left(n, n_ ext{max} ight) &= operatorname{join}left(left[0, 1 ight], g_ ext{fibo}left(n+1, n_ ext{max} ight) ight) \ g_ ext{fibo}left(n, n_ ext{max} ight) &= left{n>n_ ext{max}: left[ ight], g_ ext{fibs}left(n, n_ ext{max} ight)+f_ ext{tail}left(g_ ext{fibs}left(n, n_ ext{max} ight) ight) ight} end{align*}

This uses a mutually recursive implementation with 2 helper functions. It could probably be optimised?

Dependencies

$f_\text{tail}$ (from Lists)