**Wstepne notatki z MP.**
## **Podstawy**
### foldr (jest bardziej naturalny)
**foldr:**
inaczej akumulacja; procedura akumulacyjna- no widac jak to dziala

### **foldl:**
foldl na wykladzie jest ciutke inaczej zdefiniowany
w sensie w SICP mamy fold-left, ktory wyglada nastepujaco:

(define (fold-left op init set)
    (define (it res items)
        (if (null? items)
            res
            (it (op res (car items)) (cdr items)))) 
    (it init set))
    
w sensie jak wywolamy (fold-left cons null '(1 2 3))
to otrzymamy:
(cons (cons (cons '() 1) 2) 3) ->
((cons (cons '() 1) 2) . 3) ->
(((cons '() 1) . 2) . 3) ->
'(((() . 1) . 2) . 3)

aby zmienic fold-left dzialal tak jak foldl z wykladu trzeba
jedynie zmienic kolejnosc w pierwszym argumencie funkcji it-
mianowicie zamiast wywolywac w it (op res (car items)), zamieniamy res z (car items)
wtedy jak wywolamy (fold-left cons null '(1 2 3))
to otrzymamy:
(it (cons 1 '()) '(2 3)) ->
(it (cons 2 (cons 1 '())) '(3)) ->
(it (cons 3 (cons 2 (cons 1 '())))) ->
(cons 3 (cons 2 (cons 1 '()))) ->
(cons 3 (cons 2 '(1))) ->
(cons 3 '(2 1)) ->
'(3 2 1)

## **Kodowanie Huffmana**
### **Ogolny opis**
;2.3.4 Drzewa kodow Huffmana (zmeczenie, wiec trzeba troche sie pomeczyc)

Uzywajac 7 bitow, mozemy rozroznic 2^7, czyli 128 roznych znakow. Ogolnie mowiac jesli chcemy przedstawic n roznych symobli,
bedziemy potrzebowali log_{2}(n) bitow na symbol. Jesli wszystkie nasze wiadomosci skladaja sie z osmiu symobli:
A, B, C, D, E, F, G, H, to mozemy okreslic ich kodowanie przy uzyciu trzech bitow na znak; na przyklad
A 000 E 100
B 001 F 101
C 010 G 110
D 011 H 111

np wiadomosc BACA jest zakodowana jako: 001000010000
Jest to przyklad kodu o stalej dlugosci, poniewaz kazdy symbol jest w nich reprezentowany za pomoca takiej samej liczby bitow.
Czasami bardziej korzystne jest zastosowanie kodow o zmiennej dlugosci, w ktorych symbole moga byc reprezentowane za pomoca
roznej liczby bitow. Rozwazmy nastepujacy, alternatywny kod dla liter od A do H:
A 0 E 1100
B 100 F 1101
C 1010 G 1110
D 1011 H 1111

Przy takim kodowaniu wiadomosc BACA jest zakodowana jako: 100010100.
Duzo zaoszczedizlismy.
Kod prefiksowy- pelny kod zadnego symbolu nie jest poczatkiem innego symbolu.
W powyzszym przykladzie A jest kodowane jako 0 a B jako 100, wobec tego, zaden inny symbol nie moze sie zaczynac ani o 0 ani od 100.
Kod Huffmana- kod prefiksowy o zmiennej dlugosci symboli.
Kod Huffmuna moze byc przedstawiony jako drzewo binarne, ktorego liscie sa kodowanymi symbolami.
W kazdym nie bedacym lisciem wezle drzewa znajduje sie zbior wszystkich symboli przechowywanych w lisciach lezacych ponizej danego wezla.
Dodatkowo kazdy symbol znajdujacy sie w lisciu ma przypisana wage(ktora jest jego wzgledna czestoscia wystepowania), a kazdy wezel nie bedacy
lisciem ma przypisana wage bedaca suma wag wszystkich lisci lezacych ponizej niego. Wagi te nie sa uzywane ani w procesie kodowania ani dekodowania.

{A B C D E F G H} 18
/ \
A 9 {B C D E F G H} 9
/ \
{B C D} 5 {E F G H} 4
/ \ / \
B 3 {C D} 2 {E F} 2 {G H} 2
/ \ / \ / \
C 1 D 1 E 1 F 1 G 1 H 1

Na rysunku powyzej jest przedstawione drzewo Huffmana dla omowionego wczesniej kodu "od A do H". Wagi lisci wskazuja na to, ze drzewo
zostalo zaprojektowane dla wiadomosci, w ktorych A pojawia sie ze wzgledna czestotliwoscia 9, B ze wzgledna czestotliwoscia 3, a pozostale
litery z wzgledna czestotliwoscia 1.
Majac drzewo Huffmana mozemy wyznaczyc kod dowolnego symbolu, poruszajac sie w dol od korzenia do liscia zawierajacego dany symbol.
Za kazdym razem gdy przechodzimy w dol wzdluz lewej galezi, dodajemy do kodu 0, a gdy przechodzimy w dol wzdluz prawej galezi to dodajemy 1.
Wybieramy zawsze taka galaz, ktora prowadzi do liscia zawierajacego dany symbol lub do wezla zawierajacego zbior, do ktorego nalezy dany symbol.
Na przyklad, zaczynajac od korzenia drzewa narysowanego powyzej, dochodzimy do liscia oznaczajacego litere D, wybierajac najpierw prawa galaz, potem lewa,
a nastepnie dwukrotnie prawa; stad kodem D jest 1011.

Chcac zdekodowac ciag bitow za pomoca drzewa Hufmanna, zaczynamy przemieszczac sie od korzenia drzewa, wybierajac lewe badz prawe galezie
zgodnie z kolejnymi zerami i jedynkami w ciagu bitow. Za kazdym razem, gdy dochodzimy do liscia, otrzymujemy kolejny symbol wiadomosci;
po czym zaczynamy znowu od korzenia drzewa, dekodujac nastepny symbol.
Przyklad: zalozmy ze mamy dane powyzsze drzewo i ciag 100010100.
Zaczynajac od korzenia przechodzimy w dol wzdluz prawej galezi (pierwszy bit rowny 1), nastepnie lecimy w dol w lewo (drugi bit rowny 0),
nastepnie znowu w dol w lewo (trzeci bit rowny 0). Otrzymalismy symbol B. Zostal nam ciag: 010100 Zaczynamy ponownie od korzenia, idziemy
w dol w lewo bo pierwszy bit to 0. Otrzymalismy symbol A. Zostal nam ciago 10100. Idac kolejno w dol w prawo (bit 1), w dol w lewo (bit 0),
w dol w prawo (bit 1), w dol w lewo (bit 0) otrzymalismy symbol C. Zostal ciag: 0, idziemy w dol w lewo otrzymujac symbol A.
Zatem kod 100010100 odpowiada nam wiadomosci BACA.

Tworzenie drzew Huffmana
Jak zbudowac "najlepszy" kod, majac dany "alfabet" i wzgledne czestosci wystepowania symboli? Inaczej mowiac, jakie drzewo koduje wiadomosci
w najmniejszej liczbie bitow?
Algorytm jest w miare przejrzysty. Pomysl polega na takim ulozeniu wezlow, aby symbole o najmniejszych czestosciach znajdowaly sie najdalej
od korzenia. Najpierw tworzymy zbior lisci zawierajacych symbole i ich czestosci, zgodnie z danymi zrodlowymi, na podstawie ktorych budujemy kod.
Nastepnie znajdujemy dwa liscie o najmniejszych wagach i laczymy je, tworzac wezel, ktorego lewa i prawa galaz prowadza do tych lisci. Waga tego
nowego wezla jest suma wag zlaczonych lisci. Nastepnie usuwamy te dwa liscie ze zbioru poczatkowego i zastepujemy je nowym wezlem. Kontynuujemy ten proces.
W kazdym kroku laczymy dwa wezly o najmniejszych wagach, usuwamy je ze zbioru i zastepujemy wezlem, do ktorego sa one dowiazane poprzez lewa i prawa galaz.
Przerywamy proces gdy mamy tylko jeden wezek, ktory jest korzeniem calego drzewa.
Oto jak powstalo drzewo z naszego przykladu:

Poczatkowe liscie: {(A 9) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
Zlaczenie: {(A 9) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
Zlaczenie: {(A 9) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
Zlaczenie: {(A 9) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
Zlaczenie: {(A 9) (B 3) ({C D} 2) ({E F G H} 4)}
Zlaczenie: {(A 9) ({B C D} 5) ({E F G H} 4)}
Zlaczenie: {(A 9) ({B C D E F G H} 9)}
Ostatnie zlaczenie: {(A B C D E F G H} 18)}

Jak widac, algorytm ten nie zawsze jednoznacznie wyznacza drzewo, poniewaz w kazdym kroku moze byc wiele wezlow o najmniejszych wagach.
Rowniez porzadek, w jakim laczymy wezle jest dowolny.

Reprezentowanie drzew Huffmana.
Tutaj opracujemy system uzywajacy drzew Huffmana do kodowania i dekodowania wiadomosci oraz tworzacy drzewa Huffmana zgodnie z naszkicowanym
powyzej algorytmem. Najpierw omowimy reprezentacje drzew.

Liscie drzewa sa reprezentowane przez listy zawierajace symbol leaf, symbol przechowywany w lisciu oraz wage:

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))

(define (leaf? object)
  (eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

Ogolnie drzewo jest lista zlozona z lewej galezi, prawej galezi, zbioru symboli i wagi. Zbior symboli jest po prostu lista symboli,
a nie jakas bardziej wyrafinowana reprezentacja. Gdy tworzymy drzewo, laczac dwa wezly, wage tego drzewa otrzymujemy jako sume
wag wezlow, a zbior symboli jako sume zbiorow symboli wezlow. Poniewaz zbiory symboli sa reprezentowane jako listy, mozna tu uzyc
zwyklego appenda:

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))

Tworzac drzewo w opisany wyzej sposob, to mamy nastepujace selektory:

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list ( -leaf tree))
      (caddr tree)))

(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

Procedura dekodujaca

Nastepujaca procedura implementuje algorytm dekodujacy. Jej argumentami sa lista zer i jedynek oraz drzewo Huffmana.

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))


(define (choose-branch bit branch)
  (cond [(= bit 0) (left-branch branch)]
        [(= bit 1) (right-branch branch)]
        [else (error "Zla wartosc bitu -- CHOOSE-BRANCH" bit)]))

Opis:

Procedura decode-1 ma dwa argumenty: liste pozostalych bitow i biezaca pozycje biezaca w drzewie. Caly czas porusza sie "w dol" drzewa, wybierajac lewa
badz prawa galaz w zaleznosci od tego, czy kolejny bit na liscie jest rowny 0 czy 1(dzieje sie to z uzyciem procedury choose-branch). Gdy dochodzimy do liscia,
kolejnym symbolem wiadomosci jest symbol przechowywany w tym lisicu. Dolaczamy go za pomoca cons do reszty wiadomosci, ktora dekodujemy.
W ostatniej klauzuli choose-branch mamy kontrole bledow, ktora wypisje komunikat, w przypadku napotaknia danych wejsciowych innych niz zero lub jeden.

Zbiory elementow wazonych.

W naszej reprezentacji drzew kazdy wezel nie bedacy lisciem zawiera zbior symboli przedstawionych w postaci zwyklej listy. Jednakze omowiony powyzej algorytm
tworzacy drzewa wymaga rowniez operacji na zbiorach lisci i drzew, laczac kolejno dwa najmniejsze elementy. Poniewaz bedziemy musieli wielokrotnie znajdowac najmniejszy
element w zbiorze, wygodnie byloby uzyc uporzadkowanej reprezentacji tekigo rodzaju zbioru.
Zbior lisci i drzew bedziemy reprezentowac jako liste elementow, uporzadkowana zgodnie z rosnacymi wagami elementow. Ponizej konstruktor adjoin-set dodajacy
element do drzewa; porownywane sa wagi elementow, a element wstawiany do zbioru wczesniej do niego nie nalezy.

(define (adjoin-set x set)
  (cond [(null? set) (list x)]
        [(< (weight x) (weight (car set))) (cons x set)]
        [else (cons (car set)
                    (adjoin-set x (cdr set)))]))

Nastepujaca procedura na podstawie listy par symbol-czestosc, takiej jak
((A 4) (B 2) (C 1) (D 1)), tworzy poczatkowy uporzadkowany zbior lisci, gotowy do laczenia elementow zgodnie z algorytmem Huffmana:

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)     ;symbol
                               (cadr pair))   ;czestosc
                    (make-leaf-set (cdr pairs))))))

### **Kompletny program do kodowania Huffmana wg SICP**
Tutaj jeszcze opisze poszczegolne funkcjonalnosci poszczegolnych procedur.

#lang racket
;Huffman code tree

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))

(define (leaf? object)
  (eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))

(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

(define (choose-branch bit branch)
  (cond [(= bit 0) (left-branch branch)]
        [(= bit 1) (right-branch branch)]
        [else (error "Zla wartosc bitu -- CHOOSE-BRANCH" bit)]))

(define (adjoin-set x set)
  (cond [(null? set) (list x)]
        [(< (weight x) (weight (car set))) (cons x set)]
        [else (cons (car set)
                    (adjoin-set x (cdr set)))]))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)     ;symbol
                               (cadr pair))   ;czestosc
                    (make-leaf-set (cdr pairs))))))

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                    (make-leaf 'B 2)
                    (make-code-tree (make-leaf 'D 1)
                                    (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
                         
;'((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)
#|
nasze drzewo sie sklada z lewej galezi, prawej galezi listy symboli oraz wagi
lewa galaz:    (leaf A 4)
prawa galaz:   ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4)
lista symboli: (A B D C)
waga:          8

((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4)
lewa galaz:    (leaf B 2)
prawa galaz:   ((leaf D 1) (leaf C 1) (D C) 2)
lista symboli: (B D C)
waga:          4

((leaf D 1) (leaf C 1) (D C) 2)
lewa galaz:    (leaf D 1)
prawa galaz:   (leaf C 1)
lista symboli: D C
waga:          2

jak kodujemy?
sprawdzamy czy nasz symbol jest w lewej galezi czy w prawej galezi za pomoca predykatu (is-there? x tree)
w jego ciele bedzie lista symboli z tego drzewa oraz jakas procedura ktora sprawdza czy ten symbol jest na tej liscie
w zaleznosci od tego czy jest w lewej galezi czy w prawej dajemy 1 lub 0. Jesli nasze drzewo jest leaf to zwracamy ten kod

|#
(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (is-there? symbol items)
  (cond [(null? items) #f]
        [(eq? symbol (car items)) #t]
        [else (is-there? symbol (cdr items))]))

(define (foo symbol branch)
        (cond [(leaf? branch) '()]
              [(is-there? symbol (symbols (left-branch branch))) (cons 0 (foo symbol (left-branch branch)))]
              [(is-there? symbol (symbols (right-branch branch))) (cons 1 (foo symbol (right-branch branch)))]))

(define (encode-symbol symbol tree) ;to ma nam zwrocic kod danego symbolu
  (if (is-there? symbol (symbols tree))
      (foo symbol tree)
      (error "Brak symbolu w drzewku -- ENCODE_SYMBOL" symbol)))
      

(define (add-element x set)
  (cond [(null? set) (list x)]
        [(< (weight x) (weight (car set))) (cons x set)]
        [else (cons (car set) (add-element x (cdr set)))]))

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))

(define (delete a b items)
  (filter (lambda (x) (and (not (eq? a x)) (not (eq? b x)))) items))

(define (generate-huffman-tree pairs)
  (succesive-merge (make-leaf-set pairs)))

(define (succesive-merge items)
  (if (= (length items) 1)
      (car items)
      (let ((some-tree (make-code-tree (car items) (cadr items))))
        (succesive-merge (add-element some-tree
                                      (delete (car items) (cadr items) items))))))

;Probki
(define some-tree (generate-huffman-tree '((A 4) (BOOM 2) (C 1) (D 1))))

;cwiczenie 2.70
(define rock-alphabet '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1)))
(define rock-tree (generate-huffman-tree rock-alphabet))
(define rock-text '(GET A JOB SHA NA NA NA NA NA NA NA NA GET A JOB SHA NA NA NA NA NA NA NA NA WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP YIP SHA BOOM))