Programowanie funkcyjne/Model obliczeń/Ćwiczenia

Praca domowa

• Porównaj foldr i foldl. Która z nich jest ogonowa?
• Zaimplementuj potęgowanie liczb -- ogonowo, raz o złożoności liniowej, a raz o złożoności logarytmicznej.

Ćwiczenia

Ćwiczenie [Złożoność rekurencji ogonowej]

Rozważ standardowe procedury przetwarzania list: length, map, append,rev. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?

Ćwiczenie [Potęgowanie funkcji]

Potęgowanie funkcji -- najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową.

Rozrysuj 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

Ćwiczenie [Sześciany]

Napisz procedurę sześciany : int -> 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
• skorzystaj z tożsamości:
  • $(n+1{)}^3=n^3+3n^2+3n+1$,
  • $(n+1{)}^2=n^2+2n+1$.

Twoje rozwiązanie powinno działać w czasie $\mathrm{\Theta }(n)$.

Ćwiczenie [Podział permutacji]

Napisz procedurę podziel : int list -> int list list, która dla danej listy $[a_1;a_2;\dots ;a_n]$ zawierającej permutację zbioru $\{1,2,\dots ,n\}$ znajdzie jej 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}{cccc}\{a_1,a_2,\dots ,a_{k_1}\}& =& \{1,2,\dots ,k_1\}& \text{(równość zbiorów)},\\ \{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.