Programowanie funkcyjne/Model obliczeń/Ćwiczenia

From Studia Informatyczne

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 \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{matrix} \{a_1, a_2, \dots, a_{k_1}\} & = &\{1, 2, \dots, k_1\}  & \mbox{(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\},\\  & \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: \texttt{\mbox{podziel}} [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]], \texttt{\mbox{podziel}} [3;4;1;2] = [[3;4;1;2]].

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