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: +, - 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:

$\begin{array}{ccc}{a}_1,a_2,\dots ,a_{k_1}& =& 1,2,\dots ,k_1\text{(rownosc zbiorow)},\\ a_{k_1+1},a_{k_1+2},\dots ,a_{k_2}& =& k_1+1,k_1+2,\dots ,k_2,\\ & ⋮& \\ 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{array}$

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

.

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