Programowanie funkcyjne/Procedury wyższych rzędów i listy/Ćwiczenia

From Studia Informatyczne

Praca domowa

W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

  • Zapisz procedurę append za pomocą fold_right lub fold_left.
  • Napisz procedurę, która dla danej listy funkcji oblicza ich złożenie.
  • Napisz procedurę obliczającą sumę elementów listy występujących po ostatniej liczbie ujemnej (lub wszystkich, jeżeli na liście nie ma liczb ujemnych).


Ćwiczenia

W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

Ćwiczenie [Ciągi różnicowe]

Przypomnij sobie zadanie o ciągu różnicowym danej listy liczb całkowitych. Rozwiąż je za pomocą procedur wyższych rzędów.

Rozwiązanie

Oto przykładowe rozwiązanie:

 let roznicowy (h::t) = 
   rev 
     (fst 
        (fold_left
           (fun (acc, p) x -> 
             ((x-p)::acc, x)
           ) ([], h) t 
        )
     );;

Rozwiązanie

A oto inne rozwiązanie:

 let roznicowy l = 
   if l = [] then []
   else map2 (-) (tl l) (rev (tl (rev l)));;


Ćwiczenie [Nawiasy]

Dany jest ciąg nawiasów, otwierających i zamykających. Napisz procedurę nawiasy, która obliczy minimalną liczbę nawiasów które należy obrócić, tak aby uzyskać poprawne wyrażenie nawiasowe. Jeżeli nie jest to możliwe, to należy podnieść wyjątek NieDaSie.

 exception NieDaSię;;
 type nawias = Otwierający | Zamykający;;
 let nawiasy  (l: nawias list) = ... ;;

Ćwiczenie [Suma funkcji]

Napisz procedurę, która dla danej listy funkcji, oblicza funkcję będącą sumą funkcji z danej listy.

Rozwiązanie

Oto przykładowe rozwiązanie:

 let suma l = 
   fold_left 
     (fun a f -> fun x -> a x + f x)
     (fun _ -> 0) l;;

Ćwiczenie [Łączenie funkcji]

Rozszerz rozwiązanie poprzedniego zadania tak, żeby zamiast dodawania można było zastosować dowolną dwuargumentową operację na wynikach funkcji.

Rozwiązanie

Oto dwa przykładowe rozwiązania:

 let zloz op (h::t) = 
   fold_left 
     (fun f g -> fun x -> op (f x) (g x)) h t;; 
 let zloz op (h::t) x = 
   fold_left 
     (fun a f -> op a (f x)) (h x) t;;

Ćwiczenie [Exists]

Napisz procedurę exists, która dla danego predykatu i listy sprawdzi, czy na liście jest element spełniający predykat. Wykorzystaj wyjątki tak, aby nie przeglądać listy, gdy to już nie jest potrzebne.

Rozwiązanie

 exception Exists; 
 let exists p l = 
   try fold_left (fun a x -> if p x then raise Exists else a) false l
   with Exists -> true;;


Ćwiczenie [Forall]

Napisz procedurę negującą predykat non: ('a -> bool) -> ('a -> bool). Za pomocą tej procedury oraz procedury exists zdefiniuj procedurę forall, która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy. Czy zastosowanie wyjątków w implementacji procedury exists nadal powoduje, że przeglądane są tylko niezbędne elementy listy?

Ćwiczenie [Sumy]

Napisz procedurę sumy: int list -> int list, której wynikiem dla danej listy [x_1,\dots, x_n] jest lista: [x_1, x_1 + x_2, x_1+x_2+x_3, \dots, x_1+x_2+\cdots+x_n].

Przykład: sumy [1; 5; 2; 7; 12; 10; 5] = [1; 6; 8; 15; 27; 37; 42].

Ćwiczenie [Podział na listy rosnące]

Napisz procedurę podzial: int list -> int list list, która dla danej listy liczb całkowitych l = [x_1; x_2; \dots; x_n] podzieli ją na listę list [l_1; \dots; l_k], przy czym:

  • l = l_1 @ \dots @ l_k,
  • każda z list l_i jest ściśle rosnąca,
  • k jest najmniejsze możliwe.

Przykład: podzial [1;3;0;-2;-2;4;9] = [[1; 3]; [0]; [-2]; [-2;4;9]].

Ćwiczenie [Podział na listy liczb tego samego znaku]

Napisz procedurę podzial: int list -> int list list, która dla danej listy liczb całkowitych l = [x_1; x_2; \dots; x_n] podzieli ją na listę list [l_1; \dots; l_k], przy czym:

  • l = l_1 @ \dots @ l_k,
  • dla każdej listy l_i wszystkie elementy na takiej liście są tego samego znaku,
  • k jest najmniejsze możliwe.

Przykład: podzial [1;3;0;-2;-2;-4;9] = [[1; 3]; [0]; [-2;-2;-4]; [9]].

Ćwiczenie [Prefiksy zakończone zerami]

Napisz procedurę prefiksy : int list -> int list list, która dla danej listy liczb całkowitych zwróci listę wszystkich jej prefiksów zakończonych zerem, w kolejności rosnącej ich długości. Przykład: prefiksy [0;1;2;3;0;5;6;0;1] = [[0]; [0;1;2;3;0]; [0;1;2;3;0;5;6;0]]. Zwróć uwagę na złożoność rozwiązania.

Ćwiczenie [Zamiana iloczynu sum na sumę iloczynów]

Wyobraźmy sobie, że jest dana lista list elementów:

[[x_{1,1}; x_{1,2}; \dots ; x_{1, n_1}];    [x_{2,1}; x_{2,2}; \dots ; x_{2, n_2}]; \dots ;    [x_{k,1}; x_{k,2}; \dots ; x_{k, n_k}]

Reprezentuje ona iloczyn sum elementów postaci:

(x_{1,1}+x_{1,2}+\cdots+x_{1, n_1}) \cdot    (x_{2,1}+x_{2,2}+\cdots+x_{2, n_2}) \cdots    (x_{k,1}+x_{k,2}+\cdots+x_{k, n_k})

Taki iloczyn sum jest równy sumie iloczynów postaci:

(x_{1,1} \cdot x_{2,1} \cdots x_{k,1}) +    (x_{1,1} \cdot x_{2,1} \cdots x_{k,2}) + \cdots +    (x_{1,n_1} \cdot x_{2,n_2} \cdots x_{k,n_k})

którą z kolei można przedstawić jako listę list postaci:

[[x_{1,1}; x_{2,1}; \dots; x_{k,1}];    [x_{1,1}; x_{2,1}; \dots; x_{k,2}];    [x_{1,n_1}; x_{2,n_2}; \dots; x_{k,n_k}]]

Napisz procedurę rozwin: 'a list list -> 'a list list, która przekształca listę list reprezentującą iloczyn sum w listę list reprezentującą sumę iloczynów. Kolejność składników w sumie i czynników w iloczynach może być dowolna.

Przykład: rozwin [[1;2;3]; [4]; [5;6]] = [[1; 4; 5]; [1; 4; 6]; [2; 4; 5]; [2; 4; 6]; [3; 4; 5]; [3; 4; 6]].

Rozwiązanie

Oto dwa przykładowe rozwiązania:

let rozwin l = 
  fold_right
    (fun h t -> 
      (* Przemnażamy elementy t przez kolejne elementy h, gromadząc iloczyny. *)
      fold_right 
        (fun f acc ->
          (* Mnożymy elementy t przez f i dorzucamy do acc. *)
          fold_right 
            (fun x a -> (f::x)::a) 
            t acc
        ) h [] 
    ) l [[]];;
val rozwin: 'a list list -> 'a list list = <fun>
let rozwin l = 
  fold_right
    (fun h t -> 
      (* Przemnażamy elementy t przez kolejne elementy h, gromadząc iloczyny. *)
      flatten
        (map 
           (fun f -> 
             (* Mnożymy elementy t przez f *)
             (map (fun x -> f::x) t)
           ) h
        )
    ) l [[]];;
val rozwin: 'a list list -> 'a list list = <fun> 

Laboratorium

W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

Ćwiczenie [Heads]

Za pomocą map i flatten zapisz procedurę heads, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.

Rozwiązanie

 let heads l = flatten (map (function [] -> [] | h::_ -> [h]) l) ;;

Ćwiczenie [Quick-sort]

Korzystając z filter zaimplementuj alorytm quick-sort.

Rozwiązanie

let rec qsort l = 
  match l with 
    []   -> [] |
    h::t -> qsort (filter ((>) h) t) @ h :: qsort (filter ((<=) h) t);;
val qsort : 'a list -> 'a list = <fun>


Ćwiczenie [Kompresja ciągu liczb]

Rozważmy następującą metodę kompresji ciągów liczb całkowitych: jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby. Konkretnie, i powtórzeń liczby k reprezentujemy w ciągu skompresowanym jako 2^{i-1} \cdot (2 \cdot k - 1).

Napisz procedury: kompresującą i dekompresującą zadaną listę. Lista skompresowana powinna być oczywiście jak najkrótsza. Przy dekompresji możesz założyć, że lista skompresowana nie zawiera zer.

kompresuj [1; 2; 2; 5; 11; 11; 2];;
- : int list = [1; 6; 9; 42; 3]

Rozwiązanie

 let kompresuj l = 
   if l = [] then []
   else
     rev (
       snd (
         fold_left 
           (fun (y, h::t) x -> (x, if x = y then (2*h)::t else (2*x-1)::h::t)) 
           (hd l, [2 * hd l - 1]) 
           (tl l)
       )
     );;

Ćwiczenie [Tails]

Załóżmy, że dana jest lista [x_1; x_2; \dots; x_n]. Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do n) jej początkowych elementów. Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także [x_3; x_4; \dots; x_n]. Napisz procedurę tails: 'a list -> 'a list list, która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg. malejących ich długości.

Rozwiązanie

let tails l = fold_right (fun x (h::t) -> (x::h)::(h::t)) l [[]];;
val tails : 'a list -> 'a list list = <fun>


Ćwiczenie [Uśrednienie listy]

Dana jest lista liczb zmiennopozycyjnych [x_1; x_2; \dots; x_n]. Jej uśrednienie, to lista postaci: [\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]. Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. Napisz procedurę uśrednienie, która dla danej listy obliczy jej uśrednienie.

Rozwiązanie

let usrednienie l = 
  match l with 
    []   -> [] |
    h::t -> 
      let (_, w) = fold_left (fun (p, v) x -> (x, (x +. p)/. 2. :: v)) (h, []) t
      in rev w;;
val usrednienie : float list -> float list = <fun>


Ćwiczenie [Od końca do końca]

Napisz funkcję od_końca_do_końca: int list -> int, która dla danej niepustej listy [a_1;...;a_n]$ obliczy \min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|.


Ćwiczenie [Fold_tree]

Dane są: definicja typu tree i procedura fold_tree:
type 'a tree = Node of 'a * 'a tree * 'a tree | Leaf;;
let rec fold_tree f a t = 
  match t with
    Leaf -> a |
    Node (x, l, r) -> f x (fold_tree f a l) (fold_tree f a r);;

Użyj procedury fold_tree do:

  • Policzenia liczby węzłów w drzewie.
  • Policzenia wysokości drzewa.
  • Policzenia średnicy drzewa (tj. najdłuższej prostej ścieżki w drzewie łączącej dwa liście).
  • Sprawdzenia czy drzewo jest drzewem BST (dla drzewa liczb float).

Ćwiczenie [Obejście infiksowe]

Wyznacz listę wartości w węzłach danego drzewa w kolejności infiksowej, używając procedury fold_tree. Czy potrafisz to zrobić efektywnie?

Rozwiązanie [Rozwiązanie nieefektywne]

 let infix t = 
   let merge x l r = l @ (x :: r)
   in  fold_tree merge [] t;;
 

Rozwiązanie [Rozwiązanie efektywne]

 let infix t = 
   let merge x l r = fun acc -> l (x :: (r acc))
   and id x = x
   in  fold_tree merge id t [];;
 

Ćwiczenie [Liczba widocznych elementów]

Powiemy, że liczba w węźle drzewa jest widoczna, jeżeli na ścieżce od tego węzła do korzenia drzewa nie ma większej liczby. W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne. Napisz procedurę widoczne:drzewo \to int, która dla zadanego drzewa (zawierającego wyłącznie liczby nieujemne) obliczy liczbę widocznych liczb. Rozwiązując to zadanie należy skorzystać z procedury fold_tree. Możesz założyć, że w drzewie nie ma liczb ujemnych.

Rozwiązanie

Rozwiązanie polega na tym, że fold_tree wyznacza procedurę, która po podaniu największej liczby na ścieżce do korzenia oblicza listę wartości widocznych w poddrzewie. Po wyznaczeniu takiej procedury dla całego drzewa wystarczy jej podać jako maksimum na ścieżce do korzenia wartość mniejszą od wszystkich wartości w drzewie, np. -1.

let widoczne t = 
  let merge x l r = 
    fun k -> if x < k then l k + r k else l x + r x + 1
  in
    fold_tree merge (fun _ -> 0) t (-1);;
val widoczne : tree -> int = <fun>


Ćwiczenie [Procedury wyższych rzędów dla drzew]

Przypomnij sobie rozwiązanie jednego z poprzednich zadań, gdzie trzeba było zdefiniować typ danych reprezentujący drzewa dowolnego (skończonego) stopnia. Zdefiniuj dla takich drzew odpowiedniki procedur map, filter i fold.

W procedurze filter, jeżeli odrzucamy jakiś wierzchołek, to odrzucamy również wszystkich jego potomków. Odpowiednik procedury fold powinien być sparametryzowany dwiema funkcjami: Jedna powinna działać "w poziomie", kumulując wyniki policzone dla poddrzew zakorzenionych w synach danego węzła. Druga powinna działać "w pionie", okreslając wynik dla poddrzewa zakorzenionego w danym węźle, na podstawie wartości przechowywanej w tym węźle oraz wyniku skumulowanego dla poddrzew zakorzenionych w jego synach.