Programowanie funkcyjne/Model obliczeń/Ćwiczenia

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 . 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:
    • ,
    • .

Twoje rozwiązanie powinno działać w czasie .

Ćwiczenie [Podział permutacji]

Napisz procedurę podziel : int list -> int list list, która dla danej listy zawierającej permutację zbioru znajdzie jej podział na jak najliczniejszą listę list postaci:

,

taką, że:


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.