Programowanie funkcyjne/Struktury danych/Ćwiczenia

Praca domowa

• Napisz procedurę dubluj, która dubluje elementy listy, na przykład dubluj [1;2;3] = [1;1;2;2;3;3].

• Punkty (kratowe) na płaszczyźnie reprezentujemy jako pary liczb całkowitych. Prostokąty o bokach równoległych do osi układu współrzędnych reprezentujemy jako pary punktów: dolny lewy i górny prawy róg. Napisz procedurę, która dla dwóch danych prostokątów wyznacza ich przecięcie. Podaj w jaki sposób reprezentowany jest zbiór pusty.

• Zadeklaruj wariantowy typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych. Napisz procedurę obliczającą wartość wyrażenia.

Ćwiczenia

Ćwiczenie [rev]

Zaimplementuj procedurę rev odwracającą listę. (Zwróć uwagę, że rozwiązując to zadanie można korzystać z :: lub @, co daje liniową lub kwadratową złożoność czasową.)

Rozwiązanie nieefektywne, ale proste

    h::t -> (rev t) @ [h];;

Ze względu na koszt operacji @ to rozwiązanie ma złożoność czasową kwadratową.

Rozwiązanie efektywne

      h::t -> pom t (h::w)
  in
    pom l [];;

Ćwiczenie [flatten]

Napisz procedurę flatten rozwijającą listę list do listy elementów. Na przykład, flatten [[1; 2]; []; [3; 4; 5]] = [1; 2; 3; 4; 5].

Rozwiązanie

    h::t -> h @ flatten t;;

Ćwiczenie [Średnica drzew]

Dana jest definicja typu: type tree = Node of tree * tree | Leaf. Odległością między dwoma wierzchołkami (Node) w drzewie nazywamy minimalną liczbę krawędzi jakie trzeba przejść z jednego wierzchołka do drugiego. Średnicą drzewa nazwiemy maksymalną odległość między dwoma węzłami (Node) w drzewie. Przyjmujemy, że średnica pustego drzewa (Leaf) jest równa 0. Napisz procedurę srednica: tree -> int, która oblicza średnicę danego drzewa.

Rozwiązanie

{{{3}}}

Ćwiczenie [Drzewa dowolnego stopnia]

Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego) stopnia. Zdefiniuj trochę procedur operujących na takich drzewach, np. procedury wyznaczające listy elementów w porządku prefiksowym i postfiksowym.

Laboratorium

Ćwiczenia programistyczne na listy:

Ćwiczenie [$n$-ty element listy]

Zaimplementuj procedurę zwracającą $n$-ty element listy.

Rozwiązanie

{{{3}}}

Ćwiczenie [Lista $[0;1;\dots ;n]$]

Napisz procedurę tworzącą listę $n$ pierwszych liczb naturalnych.

Rozwiązanie

{{{3}}}

Ćwiczenie [append]

Zaimplementuj procedurę append sklejającą listy.

Rozwiązanie

     h::t -> h :: append t l2;;

Ćwiczenie [ciąg różnicowy]

Ciąg różnicowy ciągu $(x_1,\dots ,x_n)$ to ciąg postaci $(x_2-x_1,\dots ,x_n-x_{n-1})$. Napisz procedurę obliczającą ciąg różnicowy żądanej listy liczb całkowitych.

Rozwiązanie

       _                  -> rev a
   in pom [] l;;

Ćwiczenie [ciąg ciągów różnicowych]

Napisz procedurę obliczającą listę kolejnych ciągów różnicowych zadanej listy liczb całkowitych.

Rozwiązanie

{{{3}}}

• Napisz procedurę, której wynikiem jest para: minimum i maksimum elementów z listy. Procedura ta powinna wykonywać co najwyżej $\frac{3}{2}n$ porównań.
• 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?
• Zaimplementuj sortowanie: przez scalanie lub quick-sort.
• Zaimplementuj pakiet arytmetyczny nieograniczonych liczb całkowitych.
• Lista większościowa to taka lista, na której ponad połowa elementów jest sobie równa, a ich wartość nazywa się właśnie większością. Napisz procedurę wybierającą większość z listy większościowej; uzasadnij jej poprawność.
• Napisz procedurę trójki:int list -> (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$.

Ćwiczenia na inne struktury danych:

• Zaimplementuj 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.
• 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.
• 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.
• Zaimplementuj takie operacje na zbiorach (reprezentowanych jako drzewa BST) jak suma, przecięcie i różnica.
• Rozszerz implementację kolejek o wkładanie i wyjmowanie elementów z obydwu stron. Jaką własność powinna zachowywać procedura balance, aby koszt zamortyzowany operacji był stały?
• Dany jest typ danych reprezentujący (mało efektywnie) liczby naturalne: type nat = ZERO | SUCC of nat;;. Zaimplementuj operacje arytmetyczne na takich liczbach.