Rekurzia a Zoznamy

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ plus(m,n)= \begin{cases} m \quad \quad \quad \quad \quad \quad \quad \quad \text{ak}~n=0,\\ plus(m+1, n-1)\quad \text{inak.} \end{cases} $$ kde $m,n \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argumenty $3$ a $2$.

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ minus(m,n)= \begin{cases} m \quad \quad \quad \quad \quad \quad \quad \quad \quad \text{ak}~n=0,\\ minus(m-1,n-1) \quad \text{inak.} \end{cases} $$ kde $m,n \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argumenty $3$ a $2$.

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ times(m,n)= \begin{cases} 0 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ~~\text{ak}~n=0,\\ m+times(m,n-1) \quad \quad \text{inak.} \end{cases} $$ kde $m,n \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argumenty $3$ a $2$.

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ fib(n) = \begin{cases} 0 & \text{ak } n = 0,\\ 1 & \text{ak } n = 1,\\ fib(n-1) + fib(n-2) & \text{ak } n > 1 \end{cases} $$ kde $n \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argument $3$.

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ power(a, b) = \begin{cases} 1 & \text{ak } b = 0,\\ a \times power(a, b-1) & \text{ak } b > 0 \end{cases} $$ kde $a,b \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argumenty $2$ a $3$.

Majme rekurzívnu funkciu, ktorú opisuje nasledujúca rekurzívna definícia:

$$ sum(n) = \begin{cases} 0 & \text{ak } n = 0,\\ n + sum(n-1) & \text{ak } n > 0 \end{cases} $$ kde $n \in \mathbf{N}$.

• Definujte ju ako $\lambda$-term v typovanom $\lambda-kalkule$.
• Definujte funkciu pomocnú funkciu vyššieho rádu $g$.
• Overte čí je funkcia $g$ správne typovaná
• Aplikujte operátor $fix$ na $g$ a argument $3$.

Overte či term $t$ je správne typovaný: $$\vdash Cons\ [Nat]\ 5\ (Cons\ [Nat]\ 8\ (Cons\ [Nat]\ 11\ Nil[Nat])): List[Nat]$$

Aplikujte na term $t$ operácie $isnil,\ head,\ \text{ a } tail$ a vyhodnoťte dane termy: $$ \begin{array}{l} isnil [Nat]\ (Cons\ [Nat]\ 5\ (Cons\ [Nat]\ 8\ (Cons\ [Nat]\ 11\ Nil[Nat]))) \to \\ \\ head [Nat]\ (Cons\ [Nat]\ 5\ (Cons\ [Nat]\ 8\ (Cons\ [Nat]\ 11\ Nil[Nat]))) \to \\ \\ tail [Nat]\ (Cons\ [Nat]\ 5\ (Cons\ [Nat]\ 8\ (Cons\ [Nat]\ 11\ Nil[Nat]))) \to \end{array} $$

1. Zadefinujte funkciu dĺžka zoznamu prirodzených čísel, ktorá pre ľubovoľný zoznam vráti počet jeho prvkov: $$ length:\ List[Nat] \to Nat $$
2. Overte či je správne typovaná.
3. Aplikujte ju na term $t$.

1. Zadefinujte funkciu pre výpočet hodnoty sčítania všetkých hodnôt zoznamu prirodzených čísel: $$ sum:\ List[Nat] \to Nat $$
2. Overte či je správne typovaná.
3. Aplikujte ju na term $t$.