# Przygotowanie do egzaminu
## Wstępne informacje
Notatki zostały przygotowane przeze mnie @matgar14 oraz @wooc4sh, ale podczas ich tworzenia mocno insiprowałem się notatkami innych osób takich jak:
- Victoriia Kashpruk:
- [Zadania dodatkowe z indukcji](https://hackmd.io/@Vikos/SyJe8LRQ2),
- [Rose-Tree](https://hackmd.io/@Vikos/HyoHXWHm3),
- [Wykład 9](https://hackmd.io/@Vikos/Sy35_tGN3),
- [Wykład 10](https://hackmd.io/@Vikos/S1WlDKoN3),
- [Wykład 11](https://hackmd.io/@Vikos/SkBvH7MBn).
- grupa z roku 2022 (link do ich notatek: [link](https://hackmd.io/@orkur/mp_fajrantpack)) (*jeśli lubisz luźne tłumaczenie, to szczerze polecam*).
**Zastrzeżenie: Kolejność informacji w notatkach może nie pokrywać się w kolejnością z wykładu.**
**Uwaga: Omówiłem tylko I tercję, pomijając wytłumaczenie jednego z algorytmów (Kodowanie Huffmana)**
---
## Tercja I
---
### Wykład I
#### **PODSTAWOWE INFORMACJE**
Racket to funkcyjny język programowania, który w większości wypadków jest gorliwy, ale zdarzają się wypadki, gdzie jest leniwy. O tym, powiem bardziej szczegółowo później.
Racket używa notacji prefiksowej np. $(f\ x\ y)$, gdzie $f$ to procedura (o tym później), a $x$ i $y$ to argumenty. Nawiasy (wyrażenie) mówią, że całe wyrażenie $(f\ x\ y)$ ma być obliczone.
Nie ma siły wiązania operatorów, musimy zająć się tym sami, wymusząc piorytet nawiasami.
Racket nie przejmuje się różnymi rodzajami nawiasów np. \[], {} i (). Należy pamiętać, że jeśli otworzyło się nawias jednym rodzajem nawiasów, to tym samym należy go zamknąć.
W Racket'cie mamy różne "typy" (typy dopiero w Plait'cie):
- $Boolean$: #t, #f
- $Number$: 1, 2.0
- $String$: "a"
- $Symbol$: 'a
Mamy też takie rzeczy jak:
- procedury: $+$, $-$, $/$, $*$, $<$, $>$, $=$, $string \rightarrow number$ itd.
- predykaty (funkcja zwracająca #t lub #f): $symbol?$, $string?$, $number?$, $pair?$ (o tym na następnym wykładzie) itd.
- formy specjalne:
- ($and$ boolean1 boolean2) - Forma $and$ oblicza podwyrażenia od lewej do prawej tak długo, aż natrafi na wartość #f, którą wtedy zwraca. Jeśli żadne podwyrażenie nie oblicza się do #f, zwracana jest wartość ostatniego podwyrażenia,
- ($or$ boolean1 boolean2) - Forma $or$ oblicza podwyrażenia od lewej do prawej tak długo, aż natrafi na wartość inna niż #f, którą wtedy zwraca. Jeśli wszystkie podwyrażenia obliczają sie do #f, zwracana jest wartość ostatniego podwyrażenia,
- ($if$ cond ifTrue ifFalse), gdzie cond to $Boolean$
- ($let$ (\[*$to$, co chcesz, żeby zostało podstawione*
*coś, za co podstawiasz $to$*]) wyrażenie) - do tego wrócę później,
- ($lambda$ (arg1 arg2 ...) (wyrażenie z arg1, arg2, ...)) (o tym będzie na jednym z następnych wykładów) itd.
Trzeba zaznaczyć, że $and$, $or$ i $if$ są leniwymi formami specjalnymi.
W Racket'cie można deklarować zmienne i funkcje za pomocą define np.
```=racket
(define x 42)
; lub
(define (f x y) (+ x y))
```
Można również nadpisywać wbudowane definicje za pomocą użycia define, tzw. leksykalne wiązanie np.
```racket=
(define + *)
; lub
(define + 2)
```
Na wykładzie było też wspomiane o modelu podstawieniowym obliczeń. Poniżej skopiowany wywód z poprzedniego roku:
#### **PODSTAWIENIOWY MODEL OBLICZEŃ**
```racket=
; Leniwa kolejność
; (addition 2 (* 2 2))
; -> (+ 2 (* 2 2))
; -> (+ 2 4)
; -> 6
; (return-first (+ 1 0) (/ 1 0))
; -> (+ 1 0)
; -> 1
; Gorliwa kolejność
; (addition 2 (* 2 2))
; -> (addition 2 4)
; -> (+ 2 4)
; -> 6
; (return-first (+ 1 0) (/ 1 0))
; -> (return-first 1 **wyjątek**)
; -> **wyjątek**
```
Istnieją 2 rodzaje ewaulacji (modelu obliczeniowego):
- leniwa, czyli taka, że funkcja nie oblicza każdego argumentu odrazu, tylko wtedy kiedy jest potrzebna,
- gorliwa, która oblicza wartość argumentów funkcji jeszcze przed jej wywołaniem.
Tutaj jest dokładnie objaśnione jak przebiega leniwa ewaluacja.
Jeśli obliczane wyrażenie to:
- zmienna $\rightarrow$ pobierz wartość zmiennej ze środowiska
- wyrażenie pierwotne (np. stała liczbowa, boolowska, ciąg znaków, obrazek) $\rightarrow$ zwróć jego wartość
- kombinacja (ciąg wyrażeń w nawiasie) $\rightarrow$
- obliczyć wartość wszystkich składowych kombinacji
- patrzymy na wartość pierwszego wyrażenia kombinacji (operatora):
* jeśli jest to procedura wbudowana (np. $+$, $*$) $\rightarrow$ oblicz wartość
* jeśli to procedura zdefiniowana przez programistę $\rightarrow$
* podstaw wartości argumentów w ciele procedury
* oblicz ciało procedury
- forma specjalna $\rightarrow$ stosujemy reguły obliczeń tej formy specjalnej np.
```racket=
; (if (= 1 2) (+ 2 3) (* 2 3))
; -> (if #f
; (+ 2 3)
; (* 2 3))
; -> (* 2 3) -> 6
; (let ([x (+ 2 2)]) (* x x))
; -> (let ([x 4]) (* x x))
; -> (* 4 4) -> 16
```
#### **LOGIKA I RZĘDU**
W Racket'cie tak samo jak w logice I rzędu, występuje wiązanie zmiennych, czyli zmienne mogą być wolne lub wiązane np. w $let$'cie można to dobrze wytłumaczyć:
```racket=
(let ([x 5])
(+ (let ([x 3]) x)
x y))
```
W tym wyrażeniu $x$ jest wiązany, a $y$ jest zmienną wolną. Zmienna $x$ wewnątrz $let$'a ma wartość 5, ale mamy tutaj również kolejnego $let$'a, który ma wiąże mocniej zmienną $x$, dlatego tutaj zmienna $x$ ma wartość $3$. Dlatego wyrażenie oblicza nam się do ($+$ $3$ $5$ $y$).
Inne przykłady zadań ze zmiennymi wolnymi i związanymi:
- Lista 2 Zadanie 1:
- :::spoiler Treść
:::
- :::spoiler Rozwiązanie
:::
- Egzamin 2022 Zadanie 1:
- :::spoiler Treść
:::
- :::spoiler Rozwiązanie
:::
- [Egzamin 2023 Zadanie 1](#Egzamin-zasadniczy-Zadanie-1)
Jest też takie coś jak $let*$, który działa tak samo jak sam $let$, ale nie musimy robić zagnieżdżeń $let$'a w $let$'cie np.
```racket=
(define x 5)
(let* ([y x] [x 4]) x)
; Oczwyiste jest to, że zmienna x jest równa 4, bo zostaje nadpisana.
(let* ([y x] [x 4]) y)
; Wyrażenia w let'cie ewaulują się od lewej do prawej, czyli zmienna y nie będzie równa 4, tylko 5.
(let* ([y x] [x 4]) (+ x y))
; Wyrażenie obliczy się do (+ 4 5) -> 9
```
#### **ZASADY PISANIA PROGRAMÓW**
W wykładzie I też jest powiedziane o dobrym nazywaniu zmiennych, czyli tak, żeby zmienna znaczyła dokładnie to, jaką wartość przechowuje. Wspomniane jest o testowaniu, czyli o module rackunit, który można importować za pomocą ($require$ rackunit), a jest w nich kilka fajny narzędzi:
---
### Wykład II
#### **DWA PODEJŚCIA DO ROZWIĄZYWANIA PROBLEMÓW**
Na początku mamy podany przykład nieskończonej rekursji:
```racket=
(define (loop n)
(loop (+ n 1)))
```
Potem mamy podaną niezbyt dobrą implementację silni, która zużywa dużo pamięci, bo kolejne rekurencyjne wywołania są kładzone na stosie, a mnożenia są odraczane, aż do czasu, kiedy napotkamy 0.
```racket=
(define (silnia-rek n)
(if (= n 0)
1
(* n (silnia-rek (- n 1)))))
```
```racket=
; (silnia-rek 5) -> ... ->
; (* 5 (silnia-rek)) -> ... ->
; (* 5 (* 4 (slinia-rek 3))) -> ... ->
; ... ->
; (* 5 (* 4 (* 3 (* 2 (* 1 (slinia-rek 0)))))) -> ... ->
; (* 5 (* 4 (* 3 (* 2 (* 1 1))))) -> (* 5 (* 4 (* 3 (* 2 1)))) -> ...
; (* 5 24) -> 120
```
Następnie pokazywana jest iteracyjna implementacja silni, która jest dużo lepsza od poprzedniej, bo mnoży na bieżąco następne liczby, przez co nie tworzymy rekurencyjnych wywołań.
```racket=
(define (silnia-iter n)
(define (it n acc)
(if (= n 0)
acc
(it (- n 1) (* n acc))))
(it n 1))
```
```racket=
; (silnia-iter 5)
; -> (it 5 1)
; -> (if (= 5 0) 1 (it (- 5 1) (* 1 5)))
; -> (it 4 5)
; -> (it 3 20)
; -> (it 2 60)
; -> (it 1 120)
; -> (it 0 120)
; -> 120
```
#### **PARY**
W Racket'cie mamy taką strukturę jak $cons$, która jest parą, czyli ($cons$ $a$ $b$), gdzie $a$ i $b$ może być dowolną wartością. Możemy sprawdzić czy dana zmienna jest parą za pomocą predykatu $pair?$ np.
($pair?$ ($cons$ $1$ $2$)) $\rightarrow$ #t
Możemy dostać się do lewgo elementu pary za pomocą procedury car (**C**ontents of **A**ddress part of **R**egister), a do prawego za pomocą cdr (**C**ontents of **D**ecrement part of **R**egister) np.
($car$ ($cons$ $1$ $2$)) $\rightarrow$ $1$
($cdr$ ($cons$ $1$ $2$)) $\rightarrow$ $2$
Istnieją podobne funkcje, które pozwalają na dostanie się do zagnieżdżonych par np. $caar$, $cddr$, $cadr$, $cdar$ itd. Czytamy to od prawej do lewej, czyli dla $cdar$ będzie $a$ czyli lewa część pary, potem $d$, czyli prawy część pary np.
($cdar$ ($cons$ ($cons$ $1$ $2$) $3$)) $\rightarrow$ $2$
W Racket'cie możemy definiować swoje struktury za pomocą $define-struct$, ale można też to zrobić za pomocą $struct$. Wyżej wymienione funkcje wprowadzają nowe procedury np.
```racket=
(define-struct pos (x y))
; pos - konstruktor
; pos-x, pos-y - selektory
; pos? - predykat
```
Dzięki temu, wprowadzamy też nowy typ danych $pos$, odróżnialny od pozostałych typów.
#### **LISTY**
Najważniejszym typem danych, który spotkamy na Metodach Programowania są listy. Są to pary zagnieżdzone w sobie, ale w zagnieżdzonej najgłębiej parze prawym elementem jest $null$ np.
($cons$ $a$ ($cons$ $b$ ($cons$ $c$ $null$))),
gdzie $a$, $b$ i $c$ mogą być dowolnymi wartościami.
W skrócie budowa list można zdefiniować w sposób rekurencyjny (przyda się to w wielu przypadkach):
- zero elementów: $null$,
- więcej niz zero elementów:
- ($cons$ pierwszy_element lista_pozostałych_elementów).
Listę można też tworzyć za pomocą $list$ np.
```racket=
(list 1 2 3)
'(1 2 3)
```
Podobniej jak $cons$ lista ma procedury, za pomocą których można dostać się do jej elementów np. tak samo jak w $cons$ $car$, $cdr$ itd., ale i też $first$, $second$, ..., $tenth$, $last$. Jeżeli mamy chcemy dostać się do n'tej pozycji listy, to możemy użyć ($list-ref$ $n$ $xs$), gdzie $xs$ to lista (od teraz tak będziemy pisać listy). Jak sprawdzić czy zmienna jest $list$'ą? Proste, za pomocą predykatu $list$? np.
```racket=
(list? (cons 1 2)) -> #f
(list? (list 1 2)) -> #t
```
#### **REKURSJA DLA LIST + PRZYKŁADY**
Później na wykładzie za pomocą rekrusji struktualnej (dla list) piszemy własne przydatne funkcje dla list:
- dwa przypadki: dla listy pustej ($null?$ $xs$) oraz niepustej
- wywołanie rekurencyjne w przypadku dla listy niepustej to wywołanie rekurencyjne jest na ogonie listy ($cdr$ $xs$)
Poniżej kod z wykładu, gdzie mamy:
- my-list-ref,
```racket=
(define (my-list-ref xs n)
(if (= n 0)
(car xs)
(my-list-ref (cdr xs) (- n 1))))
```
```racket=
; (my-list-ref (cons 1 (cons 2 null)) 1) ->
; (my-list-ref (cdr (cons 1 (cons 2 null))) (- 1 1)) ->
; (my-list-ref (cons 2 null) 0) ->
; (car (cons 2 null)) ->
; 2
```
- my-append,
```racket=
(define (my-append xs ys)
(if (null? xs)
ys
(cons (car xs) (my-append (cdr xs) ys))))
```
```racket=
; (my-append (cons 1 (cons 2 null)) (cons 3 null)) ->
; (cons (car (cons 1 (cons 2 null)))
; (my-append (cdr (cons 1 (cons 2 null))) (cons 3 null))) ->
; (cons 1 (my-append (cons 2 null) (cons 3 null))) ->
; (cons 1 (cons 2 (my-append null (cons 3 null)))) ->
; (cons 1 (cons 2 (cons 3 null)))
```
- my-rev.
```racket=
(define (my-reverse xs)
(define (it xs ys)
(if (null? xs)
ys
(it (cdr xs) (cons (car xs) ys))))
(it xs null))
```
```racket=
; (my-reverse (cons 1 (cons 2 null))) ->
; (it (cons 1 (cons 2 null)) null) ->
; (it (cons 2 null) (cons 1 null)) ->
; (it null (cons 2 (cons 1 null))) ->
; (cons 2 (cons 1 null))
```
Ostatni raz kiedy skorzystamy z rekursji struktualnej na tym wykładzie II będzie sortowanie przez wstawianie:
```racket=
(define (insert n xs)
(if (null? xs)
(list n)
(if (< n (car xs))
(cons n xs)
(cons (car xs) (insert n (cdr xs))))))
(check-equal? (insert 2 (list 1 3))
(list 1 2 3))
(define (insertion-sort xs)
(define (it xs ys)
(if (null? xs)
ys
(it (cdr xs) (insert (car xs) ys))))
(it xs null))
(check-equal? (insertion-sort (list 3 1 2 4))
(list 1 2 3 4))
```
---
### Wykład III
#### **MODEL PUDEŁKOWY**
Na początku wykładu jest o modelu pudełkowym, który łatwo wyjaśnia, jak zbudowane są listy oraz jak działają funkcje na listach, a szczególnie $append$, o którym zaraz.
Widzimy powyżej pudełka, które łączą się w łańcuchy. Dla $null$'a mamy przekreślone pudełko, a dla list mamy pudełko, które w prawej części wskazuje na kolejne pudełko (działa to tak samo jak wskaźniki, o czym za chwilę).
Poniżej przykłady jak wygląda lista i jak **nie** wygląda lista.
W przykładzie **"A TO NIE JEST LISTA"** widzimy, że w liście pojawia się ```.``` (kropka), o czym później.
Zobaczmy jak w modelu pudełkowym wygląda łączenie list:
Z definicji $append$a iterujemy przez $xs$, aż do momentu, kiedy napotkamy na $null$, wtedy wskaźnik na $null$'a przepinamy na początek $ys$ (w czasie iteracji robimy nowe pudełka, które wskazują na te same elementy). Koszt pamięciowy i czasowy $append$a jest liniowy względem ilości elementów w $xs$.
Można wspomnieć szybko jak **nie** może wyglądać łączenie list:
Efekt takiego łączenia jest zły. Dostajemy parę list, a nie listę, która na początku ma $xs$, a na końcu $ys$ (dzieje się tak, bo nie zmieniamy wskaźnika nulla w $xs$).
Mamy też pokazany ciekawy przypadek łączenia list za pomocą $append$'a. Czy kolejność łączenia list powinno mieć taki sam efekt?
```racket=
; res1
(append (list 1) (append (list 2) (list 3)))
```
```racket=
; res2
(append (append (list 1) (list 2)) (list 3))
```
Okazuje się, że tak.
$res1$ to wynik działania linijki nr 1. Tutaj nie tworzymy nieużytków, czyli $cons$'ów, które zajmują pamięć i nie mają żadnego wpływu na wynik programu. Proces łączenia $3$ list w $res1$, przebiega najpierw na połączeniu ($list$ $2$) i ($list$ $3$), tutaj tworzymy nowy $cons$, którego lewy element wskazuje na $2$, a prawy na początek ($list$ $3$).
W $res2$ wygląda to inaczej. Najpierw liczymy wynik działania (append ($list$ $1$) ($list$ $2$)). Ciekawie robi się, gdy łączymy ($list$ $3$) z (list $1$ $2$). Tworzymy tutaj tak samo nowe pudełka i przepinamy wskaźniki, ale tworzymy przez to śmieć, którym jest pudełko w pomarańczowym kole, którym zajmie się *garbage collector*.
#### **RÓWNOŚCI**
W Racket'cie mamy różne równości:
- $=$ (równość dla liczb),
- $equal?$ (równość strukturalna),
- $eq?$ (równość tożsamościowa).
Równości dla liczb nie będę omawiał (jest ona oczywista). Ciekawsze są 2 następne. Można je łatwo omówić za pomocą wcześniejszego przykładu z $append$.
```racket=
(define xs1 (list 1))
(define xs2 (list 2))
(define xs3 (list 3))
(define res1 (append xs1 (append xs2 xs3)))
(define res2 (append (append xs1 xs2) xs3))
(check-equal? res1 res2)
(check-eq? (cddr res1) (cddr res2))
(check-not-eq? (cdr res1) (cdr res2))
```
Równość $equal?$ jest w sumie też łatwa do zrozumienia. Wygląda to tak, że patrzymy czy struktury są zbudowane tak samo, jeśli tak, to dostajemy #t.
Równość $eq?$ działa tak, że jeśli porównywane wartości zajmują ten sam obszar pamięci, to dostajemy #t.
```(check-not-eq? (cdr res1) (cdr res2))```
W tym przypadku powyżej, nie dostajemy błędu, ponieważ $eq?$ sprawdza każde pudełko ($cons$) i umie wykryć nieużytki.
#### **SYMBOLE**
Ciekawą strukturą danych w Rackecie są symbole. Są one podobne do ciągu znaków ($string$), ale nie do końca, o czym za chwilę.
```
> 'symbol
'symbol
> "string"
"string"
> (symbol? 'symbol)
#t
> (symbol? "string")
#f
> (string? 'symbol)
#f
> (string? "string")
#t
```
Symbol zapisujemy "prawie" jak $string$, z taką różnicą, że ciąg znaków nie jest w cudzysłowach ```"``` oraz na początku dajemy apostrof ```'```.
Symbole można zamienić w stringi i na odwrót za pomocą funkcji $symbol$->$string$ oraz $string$->$symbol$.
```racket=
(check-not-eq? (make-string 3 #\a) "aaa")
(check-eq? (string->symbol "aaa") 'aaa)
```
Powyżej w 1 linijce mamy pokazaną nierówność tożsamościową $eq?$, ponieważ $make-string$ tworzy ciąg "aaa" w innym miejscu w pamięci. Interesująco robi się w 2 linijce. Mamy tutaj równość tożsamościową, bo $symbol$'e mają taką własność, że jeśli pisze się je tak samo, to są równe pod każdym względem!
#### **CYTOWANIA**
Znak ```'``` jest odgrywa tutaj znaczącą rolę, ponieważ wszystko co po nim występuje jest cytowane. Typy takie jak $number$, $string$, $boolean$ są samocytujące, czyli są równe swoim wersją niezacytowanym. Procedura + i '+ nie oznaczają tego samego, bo + to procedura, a '+ to zacytowany znak +.
```racket=
(check-true (number? '1))
(check-eq? 1 '1)
(check-true (boolean? '#t))
(check-eq? #t '#t)
(check-equal? "foo" '"foo")
(check-not-equal? + '+)
```
Zacytowana "kombinacja" ```'(+ 1 2)``` oznacza opis listy, której elementami są '+, 1 i 2. Bez ```'``` (+ 1 2) oznacza, że mamy obliczyć podwyrażenia 1, 2 i wywołać procedurę +.
```racket=
(check-equal? (list '+ '1 '2) '(+ 1 2))
(check-equal? (list '+ '1 '2) (list '+ 1 2))
(check-not-equal? (list '+ '1 '2) (list + 1 2))
```
Notacja $cons$a oznacza, że jeśli ogonem jest zmienna różna od $null$'a, to przed nią stawiamy ```.``` (kropkę). Zobrazowaliśmy to wcześniej za pomocą [pudełek](#MODEL-PUDEŁKOWY). $null$ inaczej to $'()$.
```racket=
(check-equal? (cons 1 2) '(1 . 2))
(check-equal? (cons 1 null) '(1))
(check-equal? '(1 . ()) '(1))
(check-equal? (cdddr '(1 2 3 . 4)) 4)
```
#### **KWAZICYTOWANIE**
Kwazicytowanie polega na poprzedzeniu wyrażenia w tym przypadku ``` ` ``` (eng. backtick). Jest ono taki sam efekt jak cytowanie za pomocą ```'```, ale kiedy pojawia się ```,``` to zachodzi odcytowanie (czyli obliczenie wyrażenia) wyrażenia po nim.
```racket=
(check-equal? `(1 2 ,(+ 1 2)) '(1 2 3))
```
#### KOLEJNA ZASADA TWORZENIA PROGRAMÓW
Aby programy były czytelne, łatwe w zrozumieniu, łatwe w rozwijaniu oraz modyfikacji, nie można powtarzać się, czyli nie pisać tego samego kodu wiele razy. Czemu? Są 2 powody, dlaczego powinno się tak robić:
1. W razie potrzeby modyfikacji kodu będziemy robić to w 1 miejscu, dzięki czemu unikniemy błędów.
2. Rozdzielamy niezależne od siebie części kodu, dzięki czemu łatwiej testować oraz zrozumieć istotę rozwiązywanego problemu.
Później na wykładzie piszemy kilka typów sortowań przez wstawianie, dzięki którym zauważymy schemat pisania takiego typu funkcji:
```racket=
; sortowanie nierosnące
(define (insert-desc n xs)
(if (null? xs)
(list n)
(if (> n (car xs))
(cons n xs)
(cons (car xs) (insert-desc n (cdr xs))))))
(define (insertion-sort-desc xs)
(define (it xs ys)
(if (null? xs)
ys
(it (cdr xs) (insert-desc (car xs) ys))))
(it xs null))
; sortowanie ciągów znaków
(define (insert-string n xs)
(if (null? xs)
(list n)
(if (string<? n (car xs))
(cons n xs)
(cons (car xs) (insert-string n (cdr xs))))))
(define (insertion-sort-string xs)
(define (it xs ys)
(if (null? xs)
ys
(it (cdr xs) (insert-string (car xs) ys))))
(it xs null))
; sortowanie dla dowolnego operatora
(define (insert-generic lt n xs)
(if (null? xs)
(list n)
(if (lt n (car xs))
(cons n xs)
(cons (car xs) (insert-generic lt n (cdr xs))))))
(define (insertion-sort-generic lt xs)
(define (it xs ys)
(if (null? xs)
ys
(it (cdr xs) (insert-generic lt (car xs) ys))))
(it xs null))
(define (insertion-sort-new xs)
(insertion-sort-generic < xs))
(define (insertion-sort-desc-new xs)
(insertion-sort-generic > xs))
(define (insertion-sort-string-new xs)
(insertion-sort-generic string<? xs))
```
Wspólną częścią tych sortowań jest porównywanie elementów listy za pomocą jakiejś funkcji porównującej, czyli można ten kod zgeneralizować do $insert-generic$ oraz $inserion-sort-generic$, gdzie podajemy instrukcje jak nasze sortowanie ma działać.
#### **MAP**
Ponownie jak poprzednio zauważyliśmy wspólną część funkcji $add1-to-all$ i $number-list->string-list$, które robią coś dla każdego z elementów i zapisaliśmy ją jako funkcję $map$, która zamienia każdy element listy na wynik działania funkcji mapującej na tym elemencie.
```racket=
(define (add1-to-all xs)
(if (null? xs)
null
(cons (add1 (car xs))
(add1-to-all (cdr xs)))))
(check-equal? (add1-to-all '(1 2 3)) '(2 3 4))
(define (number-list->string-list xs)
(if (null? xs)
null
(cons (number->string (car xs))
(number-list->string-list (cdr xs)))))
(check-equal? (number-list->string-list '(1 2 3)) '("1" "2" "3"))
(define (my-map f xs)
(if (null? xs)
null
(cons (f (car xs))
(my-map f (cdr xs)))))
```
Takie samo rozumowanie można pokazać dla funkcji $my-filter$, która jest generalizacją funkcji filtrujących $only-postive$ i $only-numbers$, które mają predykat pozwalający na wzięcie tych elementów, które chcemy.
```racket=
(define (only-positive xs)
(if (null? xs)
null
(if (positive? (car xs))
(cons (car xs) (only-positive (cdr xs)))
(only-positive (cdr xs)))))
(define (only-numbers xs)
(if (null? xs)
null
(if (number? (car xs))
(cons (car xs) (only-numbers (cdr xs)))
(only-numbers (cdr xs)))))
(define (my-filter p? xs)
(if (null? xs)
null
(if (p? (car xs))
(cons (car xs) (my-filter p? (cdr xs)))
(my-filter p? (cdr xs)))))
```
#### **FOLDR**
W czym podobne są teraz funkcje $my-append$, $my-map$ i $my-filter$? Na pierwszy rzut oka widać, że każda z nich ma rekursję struktualną dla list, czyli mamy warunek ($null?$ $xs$) i jeśli jest prawdziwy to zwracamy coś, czyli można takie coś nazwać końcowym elementem (poniżej $x$). W przeciwnym wypadku wywołujemy funkcję na bieżącym elementcie ($car$ $xs$) oraz na wartości po rekurencyjnym wywołaniu głównej funkcji na ($cdr$ $xs$). Tak zgeneralizowaną funkcję nazywamy $foldr$'em.
```racket=
(define (my-append xs ys)
(if (null? xs)
ys
(cons (car xs) (my-append (cdr xs) ys))))
(define (my-map f xs)
(if (null? xs)
null
(cons (f (car xs))
(my-map f (cdr xs)))))
(define (my-filter p? xs)
(if (null? xs)
null
(if (p? (car xs))
(cons (car xs) (my-filter p? (cdr xs)))
(my-filter p? (cdr xs)))))
(define (my-foldr f x xs)
(if (null? xs)
x
(f (car xs) (my-foldr f x (cdr xs)))))
(define (new-append xs ys)
(my-foldr cons ys xs))
(define (new-map f xs)
(define (g y ys)
(cons (f y) ys))
(my-foldr g null xs))
(define (new-filter p? xs)
(define (g y ys)
(if (p? y)
(cons y ys)
ys))
(my-foldr g null xs))
```
#### **LAMBDY**
$lambda$ to funkcja bez nazwy. Jej zapis pozwala na szybkie przepisanie funkcji zdefiniowanej za pomocą $define$, dzięki czemu kod jest czytelniejszy tak jak np. w $new-map2$ i $new-filter2$.
```racket=
(define (new-map2 f xs)
(my-foldr (lambda (y ys) (cons (f y) ys))
null xs))
(define (new-filter2 p? xs)
(my-foldr (lambda (y ys)
(if (p? y) (cons y ys) ys))
null xs))
```
#### **FOLDL**
Teraz na warsztat bierzemy 3 inne funkcje: $my-reverse$, $my-length$, $mys-sum$. Od razu może zobaczyć, że każda z nich używa dodatkowej funkcji wewnątrz. Funkcja $it$ podobnie jak w $foldr$'u ma warunek ($null?$ $xs$). Jeśli ten warunek będzie spełniony to zwracamy $acc$, czyli akumulator. Skąd taka nazwa? Popatrzmy na 2 przypadek: wywoływana jest funkcja $it$ z listą $xs$ bez głowy oraz uaktualniony akumulator za pomocą funkcji podanej w głównej funkcji. Wiedząc to wszystko można napisać zgeneralizowaną wersję, która nazywa się $foldl$.
```racket=
(define (my-reverse xs)
(define (it xs acc)
(if (null? xs)
acc
(it (cdr xs) (cons (car xs) acc))))
(it xs null))
(define (my-length xs)
(define (it xs acc)
(if (null? xs)
acc
(it (cdr xs) (+ acc 1))))
(it xs 0))
(define (my-sum xs)
(define (it xs acc)
(if (null? xs)
acc
(it (cdr xs) (+ acc (car xs)))))
(it xs 0))
(define (my-foldl f x xs)
(define (it xs acc)
(if (null? xs)
acc
(it (cdr xs) (f (car xs) acc))))
(it xs x))
(define (new-reverse xs)
(my-foldl cons null xs))
(define (new-length xs)
(my-foldl (lambda (y acc) (+ acc 1)) 0 xs))
(define (new-sum xs)
(my-foldl + 0 xs))
```
#### **CO ROBIĄ FOLDR I FOLDL?**
Odpowiedź na pytanie nie jest taka trudna, wystarczy spojrzeć na nazwy tych specjalnych procedur. $foldr$ i $foldl$ mają w sobie angielskie słowo fold, która oznacza po polsku zawijanie. Co oznacza to tajemnicze zawijanie? Zaraz do tego dojdziemy, bo zostały nam ostatnie prawe litery nazw tych funkcji: odpowiednio mamy dla $foldr$'a - r, czyli right (pl. prawo) oraz dla $foldl$'a - l, czyli left (pl. lewo). Zatem zawijanie oznacza powiązywanie elementów za pomocą funkcji i ostatniego elementu zaczynając od lewej lub prawej strony. Ta definicja zdaje się być skomplikowana, ale na przykładzie będzie widać to znacznie lepiej.
```racket=
(foldr f x (cons A (cons B (cons C (cons D null)))))
(f A (f B (f C (f D x))))
(foldl f x (cons A (cons B (cons C (cons D null)))))
(f D (f C (f B (f A x))))
```
Patrząc na rozwinięcie naszych specjalnych procedur, widzimy, że patrząc od końca (tam gdzie jest najwięcej nawiasów zamykających): dla $foldr$'a elementy wstawiamy od końca, a dla $foldl$'a od początku.
Podsumowując, $fold$'y są bardzo przydatne i intuicyjne w użyciu, jeśli dobrze je się zrozumie, używając ich pomocnego nazewnictwa.
### Wykład IV
#### **DRZEWA**
Zacznijmy od tego czym jest drzewo binarnych przeszukiwań (BST - eng. Binary Search Tree). Jest to struktura danych, która zawiera węzły ($node$) i liście ($leaf$). Każdy z węzłów ma 3 zmienne:
* $l$ - lewe poddrzewo,
* $elem$ - element węzła o znamym typie,
* $r$ - prawe poddrzewo.
W lewym poddrzewie mamy elementy mniejsze od węzła, a w prawym mamy większe (lub równe - stosujemy kiedy chcemy wielokrotne wystąpienia w drzewie) od węzła np.
Jeśli nie mamy większego lub mniejszego elementu od węzła, to w te miejsca dajemy liście ($leaf$). Warto zaznaczyć, że w drzewie BST elementy raczej nie powtarzają się (wszystko zależy od potrzeby). Dzięki ```#:transparent``` wyświetlanie tych struktury działa prawidłowo i pozwala na porównywanie ich za pomocą $equal?$.
```racket=
(define-struct leaf () #:transparent)
(define-struct node (l elem r) #:transparent)
```
Już wiemy, co to drzewo binarne, ale co jeśli ktoś da nam ogromne drzewo (nie koniecznie binarne) i będziemy musieli zdecydować czy zostało dobrze zbudowane? Do tego przyda nam się predykat $tree?$.
```racket=
(define (tree? x)
(cond [(leaf? x) #t]
[(node? x) (and (tree? (node-l x))
(tree? (node-r x)))]
[else #f]))
(define (tree-alt? x)
(or (leaf? x)
(and (node? x)
(tree-alt? (node-l x))
(tree-alt? (node-r x)))))
```
Tak jak w listach mieliśmy rekursje struktualną dla list, teraz mamy rekursję struktualną dla drzew. Naturalnym pierwszą rzeczą, którą chcielibyśmy sprawdzić, czy drzewo nie jest liściem. Jeśli jest, to sprawa załatwiona, wiemy że jest drzewem. W przeciwnym wypadku dla węzła sprawdzamy czy lewe i prawe poddrzewo są prawidłowymi drzewami. Na koniec jeśli żadne z tych przypadków nie jest spełnione, to z pewnością nie jest to drzewo, dlatego zwracamy #f. Ciekawą wersją tego problemu jest funkcja $tree-alt?$, która działa tak samo, ale jest napisana troszkę innym sposobem.
Kolejną przydatną funkcją będzie szukanie wartości w BST. Aby znaleźć element $x$, to używamy zasad tworzenia takiego typu drzew. Zacznijmy po raz kolejny od liścia. Wtedy wiemy, że nie znaleźliśmy tego elementu. I tutaj dochodzimy do 2 implementacji. $find-bst$ to funkcja z wykładu, $my-find-bst$ to napisana przeze mnie (@m14). W mojej funkcji nie sprawdzamy czy drzewo $t$ jest węzłem, bo po sprawdzeniu czy jest liściem wykluczamy ten przypadek, chyba że nie jest to prawidłowe drzewo, ale ja założyłem, że nim jest. Tak czy siak, lepiej zostańmy przy wersji z wykładu. W przypadku kiedy $t$ nie jest liściem sprawdzamy, czy jest węzłem ($node?$ $t$). Później sprawdzamy, czy element korzenia (korzeń - to najwyższy węzeł w drzewie) jest równy szukanej wartości. Jeśli nie, to mamy 2 przypadki:
- $x$ jest mniejszy od elementu korzenia, dlatego sprawdzamy lewe poddrzewo (na lewo są mniejsze wartości - według zasad BST),
- $x$ jest większy od elementu korzenia, dlatego sprawdzamy prawe poddrzewo (na prawo są większe wartości - według zasad BST).
```racket=
(define (find-bst x t)
(cond [(leaf? t) #f]
[(node? t)
(cond [(= x (node-elem t)) #t]
[(< x (node-elem t))
(find-bst x (node-l t))]
[else
(find-bst x (node-r t))])]))
(define (my-find-bst x t)
(cond [(leaf? t) #f]
[(= x (node-elem t)) #t]
[(> x (node-elem t)) (my-find-bst x (node-r t))]
[(< x (node-elem t)) (my-find-bst x (node-l t))]))
```
Następną funkcją jest $insert-bst$. Jest to jedna z procedur, bez której wstawianie do elementów byłoby trudne albo niemożliwe. Działa ona tak:
1. Kiedy drzewo jest liściem, nie mamy co robić i wstawiamy element do korzenia,
2. Kiedy drzewo jest węzłem, mamy 3 przypadki:
- wstawiany element jest równy elementowi w korzeniu (wtedy zwracamy samo drzewo $t$, bo z definicji BST elementy nie powtarzają się),
- wstawiany element jest mniejszy od elementu w korzeniu (wtedy odbudowujemy drzewo tak, że element korzenia i prawe poddrzewo zostawiamy bez zmian w tym samym miejscu, bo wiemy, że tam nie wstawimy $x$, a w lewym poddrzewie nadal szukamy miejsca),
- wstawiany element jest większy od elementu w korzeniu (wtedy odbudowujemy drzewo tak, że element korzenia i lewe poddrzewo zostawiamy bez zmian w tym samym miejscu, bo wiemy, że tam nie wstawimy $x$, a w prawym poddrzewie nadal szukamy miejsca).
```racket=
(define (insert-bst x t)
(cond [(leaf? t) (node (leaf) x (leaf))]
[(node? t)
(cond [(= x (node-elem t)) t]
[(< x (node-elem t))
(node (insert-bst x (node-l t))
(node-elem t)
(node-r t))]
[else
(node (node-l t)
(node-elem t)
(insert-bst x (node-r t)))])]))
```
Teraz przed nami ciekawe pytanie. Jak działa ta funkcja z punktu pamięci? $insert-bst$ podpina wskaźniki do starego drzewa z węzłów, które utworzyliśmy bez ich kopiowania. Poniżej obrazek pokazujący wstawianie $2$$\frac{1}{2}$ do drzewa oraz obrazek pokazujący wstawianie 7 do drzewa.
#### **KODOWANIE HUFFMANA**
[Świetne wytłumaczenie - link do flimiku YT](https://youtu.be/L5MloiCxHPk?si=rWySspy66RbsTTgu)
### Wykład V
#### **Typy**
Typy pomagają programiście pisać funkcje, które zawsze zwracają ten sam typ danych. W Racket'cie nie ma ściśle określonych typów, dlatego przesiadamy się na tym wykładzie na Plait'a, w którym pisze się podobnie z małymi zmianami:
- po wypisaniu jakiejś zmiennej, Plait wypisze jej typ, a potem wartość, tak samo postępuje z fukcjami, podając typ danych, które przyjmuje i zwraca,
- predykaty $number?$, $string?$ itd. nie istnieją w Plait'cie, ponieważ kompilator sam je sprawdza.
Można powiedzieć, że Racket też robi coś podobnego, bo nie pozwala na operację pomiędzy liczbą ($number$) a ciągiem znaków ($string$), ale jest sytuacja, w której tak jakny na to pozwala. Spójrzy na taką sytuację ```(if #t 1 (+ 1 "1"))```. Wiemy, że Racket zwróci wartość $1$, bo $if$ jest formą specjalną leniwą, czyli oblicza tylko, co jest potrzebne, dlatego nie spojrzy nawet na wartość, która byłaby zwracana w przeciwym przypadku.
W Plait'cie jest inaczej. Wszystkie funkcje są gorliwe, dlatego Plait profesjonalnie wyrzuci błąd typów. Tak samo będzie się dziać, dla ```(if #t "1" 1)```, bo $if$ nie zwraca wartości tego samego typu.
Zobaczmy teraz przykłady typów procedur w Plait'cie. $+$ przyjmuje tylko 2 argumenty, a nie jak w Racket'cie $n$ argumentów, dlatego typ wygląda tak ```(Number Number -> Number)```.
Weźmy sobie teraz na warsztat procedurę obliczającą silnie.
```racket=
(define (fact x)
(if (= x 0)
1
(* x (fact (- x 1)))))
```
Bierze ona zmienną $x$ typu ```Number```, coś z nią robi i zwraca typ ```Number```, czyli jest to funkcja typu ```(Number -> Number)```.
Kolejnym intrygującym przykładem będzie taka procedura:
```racket=
(define (foo x))
(if x x x))
```
Pomyślmy teraz logicznie jakiego typu musi być ta funkcja. $if$ przyjmuje warunek, który musi być ```Boolean```, czyli $x$ jest tego typu. Dochodzimy do wniosku, że $if$ zwróci nam ```Boolean```, bo w każdym warunku mamy $x$.
Doszliśmy teraz do fundamentalnego przykładu, dzięki którym poznamy parametryczne typy. Rozpatrzmy tą procedurę:
```racket=
(define (id x) x)
```
Bierze ona $x$, który może być dowolnym ustalonym typem i potem go zwraca. Zatem typem tej funkcji będzie ```('a -> 'a)```, gdzie ```'a``` jest naszym typem. Podobnie działa $equal?$, który ma typ ```('a 'a -> Boolean)```, dlatego dla ```(equal? "1" 1)``` wypisze błąd.
#### **Pary i listy w Plait'cie**
Parę w Plait'cie zapisujemy za pomocą struktury ```pair```, która jest typu ```('a 'b -> ('a * 'b))```. Tak samo jak w Racket'cie możemy dostać się do pierwszego i drugiego elementu, dzięki analogicznie ```fst``` (jej typ to: ```(('a * 'b) -> 'a)```) oraz ```snd``` (jej typ to: ```(('a * 'b) -> 'b)```). Jak można zauważyć elementy pary mogą być różnego typu, dzięki czemu możemy napisać ```(pair 1 "1")```. Plait wypisze nam w terminalu ```(Number * String)``` oraz ```(values "1" 1)```.
```values``` jest to struktura podobna do tuple, ponieważ może przyjmować $n$ argumentów dowolnego typu, ale nie będziemy się na wykładzie nimi zajmować, pomijając to, że są bez użyteczne (nie można w żaden sposób dostać do jej elementów, nie mówiąc o 2 argumentowej wersji, czyli o $pair$).
Innym przykładem pary może być ```(pair 1 +)```, która jest typu ```(Number * (Number Number -> Number))```. Plait wypisze również w terminalu ```(values 1 #<procedure:+>)```. Spójrzmy na inne przykłady procedur z parami.
```racket=
; ( -> (Number * String))
(define (pair-ns)
(pair (id 1) (id "x")))
; Błąd - nie typuje się
(define (pair-ns-2 f)
(pair (f 1) (f "x")))
; ((Number -> 'a) (String -> 'b) -> ('a * 'b))
(define (pair-ns-3 f g)
(pair (f 1) (g "x")))
```
Pierwszy przykład jest oczywisty, ale w drugim przykładzie jest ciekawiej.
Funkcja $pair-ns-2$ wyrzuca błąd. Czemu? Przejdźmy przez tą funkcję powoli. Mamy parę ($f$ 1), czyli funkcja $f$ przyjmuje typ ```Number```. Idziemy teraz dalej do 2 elementu pary, czyli ($f$ "1"). Argumentem tej funkcji jest "1" typu ```String```! Przecież funkcja $f$ przyjmuje jako argument liczbę, dlatego dostajemy błąd.
W 3 przykładzie procedura $pair-ns-3$ ma typ wypisany pod nią. Jest ona podobna do poprzedniej, ale tutaj mamy 2 funkcje. Intrygujące staje się, to dlaczego ($pair-ns-3$ $id$ $id$) nie wyrzuca błędu, przecież przekazujemy tą samą funkcję. Kluczowe jest to, że przekazujemy procedurę $id$ do 2 innych zmiennych. Okazuje się, że te $id$ są osobnymi bytami, które od siebie nie zależą, dlatego pierwszy $id$ przyjmuje i zwraca typ ```Number```, a drugi $id$ przyjmuje i zwraca typ ```String```. Sytuacją, kiedy ta funkcja nie zadziała jest przekazanie funkcji przez lambdę:
```racket=
; Nie zadziała: taka sama sytuacja, co w pair-ns-2
((lambda (f) (pair-ns-3 f f)) id)
; Tutaj zadziała, bo deklarujemy funkcję w let'cie lub define
(let ([f id]) (pair-ns-3 f f))
(define f id)
(pair-ns-3 f f)
```
Wytłumaczenie powyższej sytuacji za pomocą argumentu z wykładu: "[...] schematy typów właśnie takie jak dla identyczności, one się pojawiają i mogą być używane pod warunkiem, że ta procedrura, która ten schemat typów otrzymuje [...] jest zdefiniowana przez $define$ albo $let$'a".
Można pomyśleć, że $pair$ to taki $cons$, ale nie nadaje się on do tworzenia list. Zobaczmy to na przykładzie:
```racket=
(define (bar-bledny x)
(pair x (bar (+ x 1))))
(define (bar x)
(cons x (bar (+ x 1))))
```
Po wypisaniu $bar-bledny$ dostaniemy błąd typowania, a dla $bar$ ```(Number -> (Listof Number))```, co oznacza, że po dostaniu liczby, zwróci listę liczb.
Jeśli $pair$ nie pomoże nam w tworzeniu list, to co? Okazuje się, że tak samo jak w Racket'cie możemy użyć $cons$'a do tworzenia list. Ma on typ ```('a (Listof 'a) -> (Listof 'a))```, dlatego listy w Plait'cie są wyłącznie jednego typu. Czy aby zrobić listę jednoelementową napiszemy $(cons\ 1\ null)$? Po wpisaniu tego w konsoli dostaniemy błąd. $null$ w Plait'cie nie istnieje, ale mamy zamiast niego $empty$, który jest typu ```(Listof 'a)``` i reprezentowany jest przez ```'()```.
Twórcom Plaita nie wiadomo czemu, ale nie spodobało się nazewnictwo $car$ i $cdr$, dlatego mamy $first$ i $rest$, co w sumie jest bardziej intuicyjne :stuck_out_tongue:
Zatem listy zapisujemy tak: ```(cons 1 (cons 2 empty)```, co po wpisaniu w terminal daje ```(Listof Number)``` oraz ```'(1 2)```, co ciekawe jest to równie prawidłowy sposób na definiowanie list. Mamy oczywiście nie procedurę, tylko formę specjalną, którę jest $list$. Działa on tak samo jak $list$ w Racket'cie, tylko że nie można do niej wpisać zmiennych różnych typów (co wydaje się oczywiste).
#### **Letrec i local**
$letrec$ i $local$ przydają się do pisania funkcji wewnątrz funkcji, ponieważ bez nich nie byłoby to możliwe. Oto przykłady ich użycia:
```racket=
(define (sum xs)
(local [(define (it xs acc)
(if (empty? xs)
acc
(it (rest xs) (+ acc (first xs)))))]
(it xs 0)))
(define (sum2 xs)
(letrec [(it (lambda (xs acc)
(if (empty? xs)
acc
(it (rest xs) (+ acc (first xs))))))]
(it xs 0)))
```
#### **Foldl i foldr w Plait**
```racket=
(define (my-foldr f x xs)
(if (empty? xs)
x
(f (first xs) (my-foldr f x (rest xs)))))
(define (my-foldl f x xs)
(if (empty? xs)
x
(my-foldl f (f (first xs) x) (rest xs))))
```
Każda z tych funkcji ma typ ```(('a 'b -> 'b) 'b (Listof 'a) -> 'b)```, gdzie:
- f ma typ ```('a 'b -> 'b)```,
- x ma typ ```'b```,
- xs ma typ ```(Listof 'a)```.
Funkcje te zwracają ten sam typ ```'b```.
Pomyślmy czy to ma sens. Tak samo jak w $foldr$ i $foldl$ funkcja $f$ przyjmuje pierwszy element listy, który jest typu ```'a```. Na razie wszystko gra. $f$ dostaje jako 2 argument $x$, tylko w trochę innych momentach. W $foldr$, gdy $xs$ jest już listą pustą, zwraca go rekurencyjnie, czyli $f$ dostaje go i zwraca typ ```'b```, czyli to co chcemy. W $foldl$ nasz typ dostajemy od razu w 1 wywołaniu, w tym momencie ```(f (first xs) x)```. Omówiliśmy procedurę $f$, a reszta typów argumentów jest oczywista. Zwracany typ dla obu jest ```'b```, bo $f$ miesza elementy typu ```'a``` z elementami ```'b``` końca do początku (dzięki rekurencji) w $foldr$, a w $foldl$ od początku do końca.
#### **WŁASNE TYPY**
Aliasowanie działa tak, że możemy nadać swoją nazwę typom już istniejącym dla własnych potrzeb, jest to kosmetyczna zmiana, która ułatwia pisanie kodu.
```racket=
(define-type-alias NumberList (Listof Number))
(define x : NumberList empty)
```
Po wypisaniu $x$ dostajemy ```(Listof Number)```, a przecież użyliśmy $empty$, który ma typ ```(Listof 'a)```, dzięki czemu udało się nam ograniczyć jego typ do liczb.
```racket=
(define-type MyNumberList
(my-empty)
(my-cons [first : Number] [rest : MyNumberList]))
```
$define-type$ jest lepszy od $define-struct$, bo pozwala na tworzenie wielu struktur za pomocą 1 wypisania. Po wypisaniu $my-empty$ dowiemy się, że jest typu ```MyNumberList```, a dla $my-cons$ ```(Number MyNumberList -> MyNumberList)```.
W prezencie od $define-type$ dostajemy takie zabawki:
```racket=
; define-type powyżej definiuje:
; typ MyNumberList
; konstruktory:
; my-empty : (-> MyNumberList)
; my-cons : (Number MyNumberList -> NumberList)
; predykaty:
; my-empty? : (MyNumberList -> Boolean)
; my-cons? : (MyNumberList -> Boolean)
; selektory:
; my-cons-first : (MyNumberList -> Number)
; my-cons-rest : (MyNumberList -> MyNumberList)
```
Zbudujmy sobie teraz drzewo za pomocą $define-struct$. Będzie ono przyjmować tylko liczby.
```racket=
(define-type NumberTree
(nleaf)
(nnode [l : NumberTree] [elem : Number] [r : NumberTree]))
```
Dobrze, ale co jeśli ktoś chciałby drzewo z dowolnym ustalonym typem? Napiszemy wtedy tak:
```racket=
(define-type (Tree 'a)
(leaf)
(node [l : (Tree 'a)] [elem : 'a] [r : (Tree 'a)]))
```
Popatrzmy na drzewo, którego elementami będą pary liczby i stringa.
```racket=
(define example-tree
(node (node (leaf) (pair 1 "foo") (leaf))
(pair 2 "bar")
(node (leaf) (pair 3 "baz") (leaf))))
```
Napiszmy teraz funkcje, która po podaniu liczby zwróci nam przypisanego do niej stringa w parze. Będzie to działało trochę jak słowniki.
```racket=
; (bst-lookup : (Number (Tree (Number * 'a)) -> 'a)
(define (bst-lookup x t)
(cond [(leaf? t) (error 'bst-lookup "Not found")]
[(= x (fst (node-elem t))) (snd (node-elem t))]
[(< x (fst (node-elem t)))
(bst-lookup x (node-l t))]
[else
(bst-lookup x (node-r t))]))
```
Funkcja działa, ale gdy nie znajdziemy naszej liczby, to zwróci błąd. Nie chcemy, żeby tak to działało, dlatego zrobimy coś takiego.
```racket=
; (bst-lookup : (Number (Tree (Number * 'a)) -> (Optionof 'a))
(define (bst-lookup-opt x t)
(cond [(leaf? t) (none)]
[(= x (fst (node-elem t))) (some (snd (node-elem t)))]
[(< x (fst (node-elem t)))
(bst-lookup-opt x (node-l t))]
[else
(bst-lookup-opt x (node-r t))]))
```
Funkcja działa "tak samo" w małymi różnicami. Zamiast ```'a``` mamy ```(Optionof 'a)```. Jest to typ, który ma 2 konstruktory:
- $some$ ```('a -> (Optionof 'a))```,
- $none$ ```( -> Optionof 'a)```.
Kiedy będziemy mieli, co zwrócić to bierzemy $some$ wkładamy tam nasz wynik, w przeciwnym przypadku zwrócimy "nic", czyli ($none$). Dzięki takiemu typowi unikneliśmy wypisania błędu.
---
## Rozwiązania list
Rozwiązania są dostępne tylko dla mnie, żeby nie było, że daje rozwiązania do wszystkiego. Po prostu w razie problemu napisz na discordzie, do **logic_matthew**.
### [Rozwy z ćwiczeń](https://hackmd.io/lhJaGpdVTZK8h0W_B9cNYg)
---
## Egzamin zasadniczy 2023
---
### Zadanie 1
:::spoiler Treść
:::
:::spoiler Rozwiązanie
:::
---
### Zadanie 2
:::spoiler Treść
:::
:::spoiler Rozwiązanie + kod
```racket=
(define (inserts x xs)
(cons (cons x xs)
(if (null? xs)
null
(map (lambda (ys) (cons (car xs) ys))
(inserts x (cdr xs))))))
(define (concat xs)
(if (null? xs)
null
(append (car xs) (concat (cdr xs)))))
(define (map-dict f xs)
(if (null? xs)
null
(cons (cons (car xs) (f (car xs))) (map-dict f (cdr xs)))))
```
:::
---
### Zadanie 3
:::spoiler Treść
:::
:::spoiler Rozwiązanie + bonus oraz protip na zapamiętywanie sposobów na przechodzenie drzewa
```racket=
(require rackunit)
(define-struct leaf () #:transparent)
(define-struct node (l elem r) #:transparent)
(define (insert-bst x t)
(cond [(leaf? t) (node (leaf) x (leaf))]
[(node? t)
(cond [(= x (node-elem t)) t]
[(< x (node-elem t))
(node (insert-bst x (node-l t))
(node-elem t)
(node-r t))]
[else
(node (node-l t)
(node-elem t)
(insert-bst x (node-r t)))])]))
(define (list->bst xs)
(foldl insert-bst (leaf) xs))
; Inorder
(define (bst->inordist t)
(cond [(leaf? t) null]
[else (append (bst->inordist (node-l t))
(list (node-elem t))
(bst->inordist (node-r t)))]))
; Preorder
(define (bst->preordist t)
(cond [(leaf? t) null]
[else (append (list (node-elem t))
(bst->preordist (node-l t))
(bst->preordist (node-r t)))]))
; Postorder
(define (bst->postordist t)
(cond [(leaf? t) null]
[else (append (bst->postordist (node-l t))
(bst->postordist (node-r t))
(list (node-elem t)))]))
; Przykłady
(define t (list->bst '((4 2 6 3 1 5 7))
(check-equal? (bst->inordist t) '(1 2 3 4 5 6 7))
(check-equal? (bst->preordist t) '(4 2 1 3 6 5 7))
(check-equal? (bst->postordist t) '(1 3 2 5 7 6 4))
```
Ciekawy wniosek: dla inorder ($list$ ($node-elem$ $t$)) dajemy do środka $appenda$, dla preorder na początku, a postorder na końcu :smile:
:::
---
### Zadanie 4
:::spoiler Treść
:::
---
### Zadanie 5
:::spoiler Treść
:::
---
### Zadanie 6
:::spoiler Treść
:::
---
### Zadanie 7
:::spoiler Treść
:::
Sign in with Wallet
Connect another wallet