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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
== Praca domowa ==
 
== Praca domowa ==
 
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.
 +
 
* Zapisz procedurę <tt>append</tt> za pomocą <tt>fold_right</tt> lub <tt>fold_left</tt>.
 
* Zapisz procedurę <tt>append</tt> za pomocą <tt>fold_right</tt> lub <tt>fold_left</tt>.
 +
 
* Napisz procedurę, która dla danej listy funkcji oblicza ich złożenie.  
 
* 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).
 
* 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 ==
 
== Ćwiczenia ==
 
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.
* Napisz procedurę, która dla danej listy funkcji oblicza funkcję będącą sumą funkcji z danej listy.
+
 
 +
* 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ę \texttt{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 <tt>NieDaSie</tt>.
 +
  exception NieDaSię;;
 +
  type nawias = Otwierający | Zamykający;;
 +
  let nawiasy  (l: nawias list) = ... ;;
 +
 
 +
* 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.
 +
 
 
* 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.  
 
* 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.  
 +
 
* 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?
 
* 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?
 +
 +
 +
 +
== Laboratorium ==
 +
W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.
  
 
* 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> zapisz procedurę <tt>heads</tt>, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.  
 +
 
* Korzystając z <tt>filter</tt> zaimplementuj alorytm quick-sort.  
 
* Korzystając z <tt>filter</tt> zaimplementuj alorytm quick-sort.  
 +
 
* 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, <math>i</math> powtórzeń liczby <math>k</math> reprezentujemy w ciągu skompresowanym jako <math>2^{i-1} \cdot (2 \cdot k - 1)</math>.  
 
* 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, <math>i</math> powtórzeń liczby <math>k</math> reprezentujemy w ciągu skompresowanym jako <math>2^{i-1} \cdot (2 \cdot k - 1)</math>.  
 
: 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.  
 
: 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.  
Linia 20: Linia 43:
  
 
* Dana jest lista liczb zmiennopozycyjnych <math>[x_1; x_2; \dots; x_n]</math>. Jej uśrednienie, to lista postaci: <math>[\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]</math>. Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. Napisz procedurę <tt>uśrednienie</tt>, która dla danej listy obliczy jej uśrednienie.  
 
* Dana jest lista liczb zmiennopozycyjnych <math>[x_1; x_2; \dots; x_n]</math>. Jej uśrednienie, to lista postaci: <math>[\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]</math>. Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. Napisz procedurę <tt>uśrednienie</tt>, która dla danej listy obliczy jej uśrednienie.  
 +
 
* Napisz funkcję <tt>od_końca_do_końca: int list -> int</tt>, która dla danej niepustej listy <math>[a_1;...;a_n]$</math> obliczy <math>\min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|</math>.
 
* Napisz funkcję <tt>od_końca_do_końca: int list -> int</tt>, która dla danej niepustej listy <math>[a_1;...;a_n]$</math> obliczy <math>\min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|</math>.
 +
 
* 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.  
 
* 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.  
 +
 
* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:
 
* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:
  

Wersja z 11:29, 5 paź 2006

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.

  • 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ę \texttt{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) = ... ;;
  • 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.
  • 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.
  • 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?


Laboratorium

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

  • Za pomocą map zapisz procedurę heads, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.
  • Korzystając z filter zaimplementuj alorytm quick-sort.
  • 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]
  • 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.
  • Napisz funkcję od_końca_do_końca: int list -> int, która dla danej niepustej listy obliczy .
  • 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.
  • Dane są: definicja typu tree i procedura fold_tree:
type tree = Node of tree * int * tree | Leaf;;
let rec fold_tree f a t = 
  match t with
  Leaf -> a |
  Node (l, x, 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. 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.