Programowanie funkcyjne/Procedury wyższych rzędów i listy/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 31 wersji utworzonych przez 2 użytkowników)
Linia 12: Linia 12:
 
W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.
 
W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.
  
* Przypomnij sobie zadanie o ciągu różnicowym danej listy liczb całkowitych.  Rozwiąż je za pomocą procedur wyższych rzędów.  
+
{{cwiczenie|[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.  
 +
}}
  
* Dany jest ciąg nawiasów, otwierających i zamykających.  Napisz procedurę <tt>nawiasy</tt>, 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 <tt>NieDaSie</tt>.
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Oto przykładowe rozwiązanie:
 +
  '''let''' roznicowy (h::t) =
 +
    rev
 +
      (fst
 +
        (fold_left
 +
            ('''fun''' (acc, p) x ->
 +
              ((x-p)::acc, x)
 +
            ) ([], h) t
 +
        )
 +
      );;
 +
</div></div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
A oto inne rozwiązanie:
 +
  '''let''' roznicowy l =
 +
    '''if''' l = [] '''then''' []
 +
    '''else''' map2 (-) (tl l) (rev (tl (rev l)));;
 +
</div></div>
 +
 
 +
 
 +
 
 +
{{cwiczenie|[Nawiasy]||
 +
Dany jest ciąg nawiasów, otwierających i zamykających.   
 +
Napisz procedurę <tt>nawiasy</tt>, 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 <tt>NieDaSie</tt>.
 +
}}
 
   exception NieDaSię;;
 
   exception NieDaSię;;
 
   type nawias = Otwierający | Zamykający;;
 
   type nawias = Otwierający | Zamykający;;
 
   let nawiasy  (l: nawias list) = ... ;;
 
   let nawiasy  (l: nawias list) = ... ;;
  
* Napisz procedurę, która dla danej listy funkcji, oblicza funkcję będącą sumą funkcji z danej listy.
+
{{cwiczenie|[Suma funkcji]||
 +
Napisz procedurę, która dla danej listy funkcji, oblicza funkcję będącą sumą funkcji z danej listy.
 +
}}
  
* Rozszerz rozwiązanie poprzedniego zadania tak, żeby zamiast dodawania można było zastosować dowolną dwuargumentową operację na wynikach funkcji.
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Oto przykładowe rozwiązanie:
 +
  '''let''' suma l =
 +
    fold_left
 +
      ('''fun''' a f -> '''fun''' x -> a x + f x)
 +
      ('''fun''' _ -> 0) l;;
 +
</div></div>
  
* Napisz procedurę <tt>exists</tt>, 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.  
+
{{cwiczenie|[Łączenie funkcji]||
 +
Rozszerz rozwiązanie poprzedniego zadania tak, żeby zamiast dodawania można było zastosować dowolną dwuargumentową operację na wynikach funkcji.  
 +
}}
  
* Napisz procedurę negującą predykat <tt>non: ('a -> bool) -> ('a -> bool)</tt>.  Za pomocą tej procedury oraz procedury <tt>exists</tt> zdefiniuj procedurę <tt>forall</tt>, która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.  Czy zastosowanie wyjątków w implementacji procedury <tt>exists</tt> nadal powoduje, że przeglądane są tylko niezbędne elementy listy?
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
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;;
 +
</div></div>
 +
 
 +
{{cwiczenie|[<tt>Exists</tt>]||
 +
Napisz procedurę <tt>exists</tt>, 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.
 +
}}
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
 
 +
  '''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;;
 +
</div></div>
 +
 
 +
 
 +
{{cwiczenie|[<tt>Forall</tt>]||
 +
Napisz procedurę negującą predykat <tt>non: ('a -> bool) -> ('a -> bool)</tt>.   
 +
Za pomocą tej procedury oraz procedury <tt>exists</tt> zdefiniuj procedurę <tt>forall</tt>,  
 +
która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.   
 +
Czy zastosowanie wyjątków w implementacji procedury <tt>exists</tt> nadal powoduje,  
 +
że przeglądane są tylko niezbędne elementy listy?
 +
}}
 +
 
 +
{{cwiczenie|[<tt>Sumy</tt>]||}}
 +
Napisz procedurę <tt>sumy: int list -> int list</tt>, której wynikiem dla danej listy
 +
<math>[x_1,\dots, x_n]</math> jest lista: <math>[x_1, x_1 + x_2, x_1+x_2+x_3, \dots, x_1+x_2+\cdots+x_n]</math>.
 +
 
 +
Przykład: <tt>sumy [1; 5; 2; 7; 12; 10; 5] = [1; 6; 8; 15; 27; 37; 42]</tt>.
 +
 
 +
{{cwiczenie|[<tt>Podział na listy rosnące</tt>]||}}
 +
Napisz procedurę <tt>podzial: int list -> int list list</tt>, która dla danej listy liczb całkowitych <math>l = [x_1; x_2; \dots; x_n]</math> podzieli ją na listę list <math>[l_1; \dots; l_k]</math>, przy czym:
 +
* <math>l = l_1 </math>@<math> \dots</math>@<math> l_k</math>,
 +
* każda z list <math>l_i</math> jest ściśle rosnąca,
 +
* <math>k </math> jest najmniejsze możliwe.
 +
 
 +
Przykład: <tt>podzial [1;3;0;-2;-2;4;9] = [[1; 3]; [0]; [-2]; [-2;4;9]]</tt>.
 +
 
 +
{{cwiczenie|[<tt>Podział na listy liczb tego samego znaku</tt>]||}}
 +
Napisz procedurę <tt>podzial: int list -> int list list</tt>, która dla danej listy liczb całkowitych <math>l = [x_1; x_2; \dots; x_n]</math> podzieli ją na listę list <math>[l_1; \dots; l_k]</math>, przy czym:
 +
* <math>l = l_1 </math>@<math> \dots </math>@<math> l_k</math>,
 +
* dla każdej listy <math>l_i</math> wszystkie elementy na takiej liście są tego samego znaku,
 +
* <math>k</math> jest najmniejsze możliwe.
 +
 
 +
Przykład: <tt>podzial [1;3;0;-2;-2;-4;9] = [[1; 3]; [0]; [-2;-2;-4]; [9]]</tt>.
 +
 
 +
{{cwiczenie|[Prefiksy zakończone zerami]||}}
 +
Napisz procedurę <tt>prefiksy : int list -> int list list</tt>, 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: <tt>prefiksy [0;1;2;3;0;5;6;0;1] = [[0]; [0;1;2;3;0]; [0;1;2;3;0;5;6;0]]</tt>.
 +
Zwróć uwagę na złożoność rozwiązania.
 +
 
 +
{{cwiczenie|[<tt>Zamiana iloczynu sum na sumę iloczynów</tt>]||}}
 +
Wyobraźmy sobie, że jest dana lista list elementów:
 +
 
 +
<math>
 +
[[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}]
 +
</math>
 +
 
 +
Reprezentuje ona iloczyn sum elementów postaci:
 +
 
 +
<math>
 +
  (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})
 +
</math>
 +
 
 +
Taki iloczyn sum jest równy sumie iloczynów postaci:
 +
 
 +
<math>
 +
  (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})
 +
</math>
 +
 
 +
którą z kolei można przedstawić jako listę list postaci:
 +
 
 +
<math>
 +
[[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}]]
 +
</math>
 +
 
 +
Napisz procedurę <tt>rozwin: 'a list list -> 'a list list</tt>, 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: <tt>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]]</tt>.
 +
 
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
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>''
 +
</div></div>
  
 
== Laboratorium ==
 
== Laboratorium ==
Linia 31: Linia 209:
  
 
{{cwiczenie|[Heads]||
 
{{cwiczenie|[Heads]||
Za pomocą <tt>map</tt> zapisz procedurę <tt>heads</tt>, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.  
+
Za pomocą <tt>map</tt> i <tt>flatten</tt> zapisz procedurę <tt>heads</tt>, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.  
}}
+
}}  
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
  '''let''' heads l = flatten (map ('''function''' [] -> [] | h::_ -> [h]) l) ;;
 +
</div></div>
  
 
{{cwiczenie|[Quick-sort]||
 
{{cwiczenie|[Quick-sort]||
 
Korzystając z <tt>filter</tt> zaimplementuj alorytm quick-sort.  
 
Korzystając z <tt>filter</tt> zaimplementuj alorytm quick-sort.  
 
}}
 
}}
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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>''
 +
</div></div>
 +
  
 
{{cwiczenie|[Kompresja ciągu liczb]||
 
{{cwiczenie|[Kompresja ciągu liczb]||
Linia 51: Linia 246:
 
  kompresuj [1; 2; 2; 5; 11; 11; 2];;
 
  kompresuj [1; 2; 2; 5; 11; 11; 2];;
 
  ''- : int list = [1; 6; 9; 42; 3]''
 
  ''- : int list = [1; 6; 9; 42; 3]''
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
  '''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)
 +
        )
 +
      );;
 +
</div></div>
 +
 +
{{cwiczenie|[Tails]||
 +
Załóżmy, że dana jest lista <math>[x_1; x_2; \dots; x_n]</math>.
 +
''Sufiksem'' tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do <math>n</math>) jej początkowych elementów.
 +
Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także <math>[x_3; x_4; \dots; x_n]</math>.
 +
Napisz procedurę <tt>tails: 'a list -> 'a list list</tt>, która dla danej listy tworzy listę wszystkich jej sufiksów,
 +
uporządkowaną wg. malejących ich długości.
 +
}}
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''let''' tails l = fold_right ('''fun''' x (h::t) -> (x::h)::(h::t)) l [[]];;
 +
''val tails : 'a list -> 'a list list = <fun>''
 +
</div></div>
 +
  
 
{{cwiczenie|[Uśrednienie listy]||
 
{{cwiczenie|[Uśrednienie listy]||
Linia 58: Linia 285:
 
Napisz procedurę <tt>uśrednienie</tt>, która dla danej listy obliczy jej uśrednienie.  
 
Napisz procedurę <tt>uśrednienie</tt>, która dla danej listy obliczy jej uśrednienie.  
 
}}
 
}}
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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>''
 +
</div></div>
 +
  
 
{{cwiczenie|[Od końca do końca]||
 
{{cwiczenie|[Od końca do końca]||
Linia 63: Linia 303:
 
}}
 
}}
  
{{cwiczenie|[Tails]||
 
Załóżmy, że dana jest lista <math>[x_1; x_2; \dots; x_n]</math>.
 
''Sufiksem'' tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do <math>n</math>) jej początkowych elementów.
 
Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także <math>[x_3; x_4; \dots; x_n]</math>.
 
Napisz procedurę <tt>tails: 'a list -> 'a list list</tt>, która dla danej listy tworzy listę wszystkich jej sufiksów,
 
uporządkowaną wg. malejących ich długości.
 
}}
 
  
 
{{cwiczenie|[Fold_tree]||Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:}}
 
{{cwiczenie|[Fold_tree]||Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:}}
  
  '''type''' tree = Node '''of''' tree * int * tree | Leaf;;
+
  '''type''' 'a tree = Node '''of''' 'a * 'a tree * 'a tree | Leaf;;
  '''let''' '''rec''' fold_tree f a t =  
+
 
 +
  '''let rec''' fold_tree f a t =  
 
   '''match''' t '''with'''
 
   '''match''' t '''with'''
  Leaf -> a |
+
    Leaf -> a |
  Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
+
    Node (x, l, r) -> f x (fold_tree f a l) (fold_tree f a r);;
   
+
 
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.  
+
Użyj procedury <tt>fold_tree</tt> do:
W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne.  
+
* Policzenia liczby węzłów w drzewie.
Napisz procedurę <tt>widoczne:drzewo <math>\to</math> int</tt>, która dla zadanego drzewa  
+
* Policzenia wysokości drzewa.
(zawierającego wyłącznie liczby nieujemne) obliczy liczbę widocznych liczb.  
+
* Policzenia średnicy drzewa (tj. najdłuższej prostej ścieżki w drzewie łączącej dwa liście).
Rozwiązując to zadanie należy  skorzystać z procedury <tt>fold_tree</tt>.
+
* Sprawdzenia czy drzewo jest drzewem BST (dla drzewa liczb <tt>float</tt>).
 +
 
 +
{{cwiczenie|[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?
 +
}}
 +
 
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie [Rozwiązanie nieefektywne]</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
  '''let''' infix t =
 +
    '''let''' merge x l r = l @ (x :: r)
 +
    '''in''' fold_tree merge [] t;;
 +
  </div></div>
 +
 
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie [Rozwiązanie efektywne]</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
  '''let''' infix t =
 +
    '''let''' merge x l r = '''fun''' acc -> l (x :: (r acc))
 +
    '''and''' id x = x
 +
    '''in'''  fold_tree merge id t [];;
 +
  </div></div>
 +
 
 +
{{cwiczenie|[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ę <tt>widoczne:drzewo <math>\to</math> int</tt>, 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 <tt>fold_tree</tt>. Możesz założyć, że w drzewie nie ma liczb ujemnych.
 +
}}
 +
 
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Rozwiązanie polega na tym, że <tt>fold_tree</tt> 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>''
 +
</div></div>
 +
 
  
 
{{cwiczenie|[Procedury wyższych rzędów dla drzew]||
 
{{cwiczenie|[Procedury wyższych rzędów dla drzew]||

Aktualna wersja na dzień 12:32, 28 wrz 2020

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

Rozwiązanie


Ć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

Ć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

Ć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


Ć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 jest lista: .

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 podzieli ją na listę list , przy czym:

  • @@,
  • każda z list jest ściśle rosnąca,
  • 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 podzieli ją na listę list , przy czym:

  • @@,
  • dla każdej listy wszystkie elementy na takiej liście są tego samego znaku,
  • 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:

Reprezentuje ona iloczyn sum elementów postaci:

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

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

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

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

Ćwiczenie [Quick-sort]

Korzystając z filter zaimplementuj alorytm quick-sort.

Rozwiązanie


Ć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, powtórzeń liczby reprezentujemy w ciągu skompresowanym jako .

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

Ćwiczenie [Tails]

Załóżmy, że dana jest lista . Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do ) jej początkowych elementów. Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także . 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


Ćwiczenie [Uśrednienie listy]

Dana jest lista liczb zmiennopozycyjnych . Jej uśrednienie, to lista postaci: . Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. Napisz procedurę uśrednienie, która dla danej listy obliczy jej uśrednienie.

Rozwiązanie


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

Napisz funkcję od_końca_do_końca: int list -> int, która dla danej niepustej listy obliczy .


Ć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]


Rozwiązanie [Rozwiązanie efektywne]

Ć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 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


Ć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.