Programowanie funkcyjne/Struktury danych/Ćwiczenia

Ćwiczenia

Ćwiczenie programistyczne na listy:

• $N$-ty element listy.
• Lista $n$ pierwszych liczb naturalnych.
• Odwrócenie listy rev. Wersje o liniowej (z ::) i kwadratowej (z @) złożoności czasowej. Porównać je.
• Sklejanie list append. Obliczenie ciągu różnicowego zadanej listy liczb całkowitych.
• Obliczenie listy kolejnych ciągów różnicowych zadanej listy liczb całkowitych.
• Napisz procedurę, której wynikiem jest para: minimum i maksimum elementów z listy. Procedura ta powinna wykonywać jak najmniej porównań (ale bez przeginania).

Ćwiczenia na inne struktury danych:

• Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego stopnia).
• Zdefiniuj trochę procedur operujących na takich drzewach.
• Zdefiniuj typ reprezentujący dni tygodnia, miesiące i datę.
• Zdefiniuj procedurę obliczającą na podstawie daty dzień tygodnia. Możesz założyć, że dana jest procedura sylwester, która na podstawie roku określa jakiego dnia tygodnia był Sylwester.

Laboratorium

Proste ćwiczenia na listy. Można je wykonywać w dwóch wariantach: korzystając ze wzorców, lub z procedur hd, tl i (zdefiniowanej samemu) null.

• Rozwinięcie listy list do listy (flatten).
• Zdublować elementy listy.
• Napisz procedurę last, której wynikiem jest ostatni element listy.
• Napisz procedury head i tail, które dla zadanej listy $l$ i liczby całkowitej $n$ zwracają pierwsze/ostatnie $n$ elementów listy $l$. Jeśli lista $l$ ma mniej elementów niż $n$, to wynikiem powinna być cała lista $l$. (Nazwy pochodzą od programów head i tail w Uniksie.) Co jest wynikiem tail (head l n) 1?
• Napisz procedurę posumuj, która dla danej niemalejącej listy dodatnich liczb całkowitych $(a_1\dots a_n)$ oblicza listę $(b_1\dots b_n)$, gdzie $b_i=\sum _{k=a_i}^n{a}_k$. (Pamiętaj o tym, że jeśli $m>n$, $\sum _{k=m}^n{a}_k=0$.)
• Zaimplementuj sortowanie: przez scalanie lub quick-sort.
• Zaimplementuj pakiet arytmetyczny nieograniczonych liczb całkowitych.
• Napisz program wybierający większość z listy większościowej; uzasadnij jego poprawność. Uwaga: to zadanie można rozwiązać probabilistycznie: metodą Las Vegas: wylosuj element i sprawdź czy to większość; policz oczekiwaną złożoność,
• Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości. Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1. Napisz procedurę słupki, która dla danej listy początkowych wysokości słupków obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków. Napisz funkcję max_diff : int list $\to$ int, która dla niepustej listy $[x_1;\dots ;x_n]$ znajdzie maksymalną różnicę $x_j-x_i$ dla $1\le i<j\le n$. Jaką złożoność ma Twój program.
• Napisz funkcję trójki:int list $\to$ (int * int * int) list, która dla zadanej listy dodatnich liczb całkowitych, uporządkowanej rosnąco, stworzy listę takich trójek $(a,b,c)$ liczb z danej listy, że:
  • $a<b<c$,
  • liczby $a$, $b$ i $c$ spełniają nierówność trójkąta, czyli $c<a+b$.
• Zdefiniuj taką funkcję przedziały:int list $\to$ int*int, że , gdzie jest to taka para liczb $1\le k\le l\le n$, dla której suma $a_k+\cdots +a_l$ jest największa. Oblicz i podaj złożoność Twojego rozwiązania (jako funkcję $n$).

Ćwiczenia na inne struktury danych:

• Napisz całe mnóstwo procedur operujących na drzewach. Mogą to być znane Ci operacje dotyczące drzew, lub odpowiedniki operacji na listach.
• Napisz procedurę, która dla dowolnego drzewa binarnego poprawia je tak, że spełnia ono słabszą wersję warunku BST: dla dowolnego węzła, lewy syn nie jest większy, a prawy nie jest mniejszy, niż węzeł.
• Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.
• Zaimplementować arytmetykę liczb wymiernych, reprezentując liczby wymierne jako rekordy złożone z licznika i mianownika. Implementacja może być uproszczona, np.\ bez skracania ułamków i bez normalizacji znaków (jeśli czasu mało).
• Rozszerzyć implementację kolejek o wkładanie i wyjmowanie elementów z obydwu stron.
• Dany jest typ danych reprezentujący (mało efektywnie) liczby naturalne: type nat = ZERO | SUCC of nat;;. Zaimplementuj operacje arytmetyczne na takich liczbach.
• Zaimplementuj takie operacje na zbiorach, jak suma, przecięcie, różnica.
• Zadeklaruj typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych. Napisz procedurę obliczającą wartość wyrażenia.