Programowanie funkcyjne/Wyliczanie procesów/Ćwiczenia

Ćwiczenia

• Porównaj foldr i foldl. Która z nich jest ogonowa?
• Potęgowanie liczb - liniowe i logarytmiczne, ogonowe.
• Rozważ standardowe procedury przetwarzania list: length, map, append,rev. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?
• Potęgowanie funkcji - najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową. Rozrysować w jaki sposób oblicza się:

iterate 2 (function x -> x * (x+1)) 2
iterate 3 (function x -> x * (x+1)) 1
         

(w zależności od wersji, cierpliwości i powierzchni tablic :-). W przypadku wersji logarytmicznej, procedura wynikowa jest obliczana w czasie logarytmicznym, ale ona sama działa w czasie liniowym.

Laboratorium

• Napisz procedurę sześciany: int $\to$ int list taką, że wynikiem sześciany $n$ jest lista postaci$[1^3;2^3;\dots ;n^3]$. Rozwiązując to zadanie:
  • możesz korzystać wyłącznie z rekurencji ogonowej,
  • jedyne operacje na liczbach, z jakich możesz korzystać to: \texttt{+}, - oraz porównywanie.
• Napisz procedurę podziel: int list $\to$ int list list,która dla danej listy $[a_1;a_2;\dots ;a_n]$ zawierającej permutację zbioru $1,2,\dots ,n$ znajdziejej podział na jak najliczniejszą listę list postaci:

$[[a_1;a_2;\dots ;a_{k_1}];[a_{k_1+1};a_{k_1+2};\dots ;a_{k_2}];\dots ;[a_{k_{m-1}+1};a_{k_{m-1}+2};\dots ;a_{k_m}]]$, taką że:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{matrix}”): {\displaystyle \begin{matrix} {a_1, a_2, \dots, a_{k_1}} & = &{1, 2, \dots, k_1} \quad\mbox{(ro\'wnos\'c\' zbioro\'w)}, \\{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}} & = &{k_1+1, k_1+2, \dots, k_2},\\ & \vdots & \\ {a_{{k_{m-1}}+1}, a_{{k_{m-1}}+2}, \dots, a_{k_m}} & = &{k_{m-1}+1, k_{m-1}+2, \dots, k_m}.\end{matrix}}

Przyjmujemy, że wynikiem dla listy pustej jest lista pusta. Przykład:

Parser nie mógł rozpoznać (nieznana funkcja „\mabox”): {\displaystyle \texttt{\mabox{podziel}} [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]}

.

Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.