Programowanie funkcyjne/Podstawy/Ćwiczenia

Ćwiczenia

• Forma specjalna let-in jest tylko lukrem syntaktycznym i może być rozwinięta do $\lambda$-abstrakcji. W jaki sposób?
• Udowodnij, że dla każdego naturalnego $n$ zachodzi $\text{<mrow data-mjx-texclass="ORD">fib</mrow>}n={\text{Fib}}_n$. Podaj specyfikację dla fibpom i udowodnij ją przez indukcję.

let fib n =
  let rec fibpom a b n = 
    if n = 0 then a else fibpom b (a + b) (n - 1)
  in 
    fibpom 0 1 n;;

Laboratorium

Uruchamianie Ocamla. Proste programiki operujące liczbami całkowitymi (bez rekurencji ogonowej i list):

• Stopień parzystości liczby całkowitej $x$, to największa taka liczba naturalna $i$, że $x$ dzieli się przez 2ⁱ. Liczby nieparzyste mają stopień parzystości 0, liczby 2 i -6 mają stopień parzystości 1, a liczby 4 i 12 mają stopień parzystości 2. Przyjmujemy, że 0 ma stopień parzystości -1.

Napisz procedurę parzystość wyznaczającą stopień parzystości danej liczby całkowitej.

• sprawdź, czy liczba jest pierwsza,
• sprawdzenie podzielności przez 9 metodą sumowania cyfr: liczba -> suma cyfr, powtarzać aż do uzyskania liczby jednocyfrowej,
• odwrócić liczbę ($1234\to 4321$),
• sprawdzenie, czy liczba dzieli się przez 11: sumujemy cyfry liczby znajdujące się na parzystych pozycjach, oraz te na nieparzystych pozycjach, różnica tych dwóch reszt przystaje modulo 11 do wyjściowej liczby; powtarzać aż do uzyskania liczby jednocyfrowej,
• kodowanie par liczb całkowitych jako liczby całkowite.