Clojure Elementary 3

“Don't worry about what anybody else is going to do. The best way to predict the future is to invent it.”

— Alan Kay 

Kolejna część zmagań z zadaniami ze strony 4Clojure.

Do dzieła!: ;)

Problem 17: Sequences : filter.

Zadanie polega na zgadnięciu rezultatu filtrowania listy za pomocą funkcji testującej. Funkcja filter bierze za pierwszy argument funkcję testującą a drugi sekwencję. Zwraca elementy sekwencji, które przejdą test pozytywnie. Tutaj funkcja anonimowa zwraca logiczną prawdę jeżeli przekazany do niej parametr jest większy od 5, a więc filter powinien zwrócić wszystkie elementy sekwencji większe od 5.

T1: (= __ (filter #(> % 5) '(3 4 5 6 7))) E1: '(6 7) E2: [6 7]

Problem 18: Local bindings.

Funkcja let pozwala na lokalne przypisanie nazw funkcjom bądź danym. Bardzo ułatwia czytanie kodu. Budowa jest postaci:
(let [zmienna1 funkcja1 zmienna2 funkcja2 .... zmiennaN funkcjaN] (obliczena z wykorzystaniem zmienna1..N))
Zadanie polega na odgadnięciu rezultatu działania funkcji.

T1: (= __ (let [x 5] (+ 2 x))) T2: (= __ (let [x 3, y 10] (- y x))) T3: (= __ (let [x 21] (let [y 3] (/ x y)))) E1: 7

Problem 19: Let it Be

Zadanie odwrotne do zadania 18. Zamiast zgadywać wynik, trzeba zgadnąć postać przypisania. Zadanie jest trudne bo trzeba zgadnąć wartości przypisań. Najlepiej zacząć od dołu (T3).

T1: (= 10 (let __ (+ x y))) T2: (= 4 (let __ (+ y z))) T3: (= 1 (let __ z)) E1: [z 1 y 3 x 7]

Problem 20: Regular Expressions

Wyrażenia regularne. Tym razem trzeba zgadnąć rezultat działania funkcji re-seq, która za pierwszy parametr bierze postać wyrażenia regularnego, a jako drugi ciąg znaków do przeszukania. Wyrażenie regularne w Clojure ma postać: #" ". re-seq zwraca każde poprawne wystąpienie tekstu spełniającego wyrażenie w postaci sekwencji. Funkcję str już znamy. Funkcja apply natomiast powoduje użycie listy jako argumentów do funkcji str.
Zamiast:

(str "a" "b" "c")

jest:

(apply str '("a" "b" "c"))

I zadanie:

T1: (= __ (apply str (re-seq #"[A-Z]+" "bA1B3Ce "))) E1: "ABC"

Problem 21: Intro to Reduce

Funkcja reduce bierze dwa lub trzy argumenty. Pierwszym jest funkcja, która może przyjąć dwa argumenty. Jeżeli drugim argumentem jest kolekcja, reduce bierze pierwsze dwa elementy z kolekcji i przekazuje je do funkcji. Jeżeli są jeszcze elementy w kolekcji, to brany jest wynik poprzedniej operacji na elementach, kolejny element z listy i przekazywane do podanej funkcji aż do wyczerpania elementów. Jeżeli zamiast kolekcji podamy jakąś wartość i kolekcję, to pierwszym elementem przekazanym do funkcji będzie ta wartość, a drugim pierwszy element z kolekcji.
Zadnie polega na zgadnięciu postaci funkcji jaka zastosowana według powyższych reguł da podany wynik.

T1: (= 15 (reduce __ [1 2 3 4 5])) T2: (=  0 (reduce __ [])) T3: (=  6 (reduce __ 1 [2 3])) E1: + E2: (fn add       ([] 0)       ([a b] (+ a b)))

Uwaga. W odpowiedzi użyłem dziwnie wyglądającej funkcji anonimowej. Wcześniej napisałem, że funkcja reduce potrzebuje za pierwszy argument funkcji, która potrafi przyjąć dwa argumenty. Niestety, test T2 wymaga, by funkcja radziła sobie z brakiem argumentów. Clojure pozwala skonstruować funkcje tak, by w jednej definicji przewidywały odpowiedź na różną ilość argumentów. Te definicje oddziela się nawiasami okrągłymi i mogą być w dowolnej kolejności.

Problem 22: Simple Recursion

Rekurencja. Występuje wtedy, gdy funkcja wywołuje samą siebie. W tym zadaniu funkcja foo bierze liczbę za argument x. Jeżeli x jest większe od 0 (when) wykonuje funkcję conj, która tworzy sekwencję z funkcji foo pomniejszonej o 1 i aktualnego x. Funkcja conj łączy do początku listy, ale wykona się rekurencyjnie dopiero po napotkaniu warunku brzegowego (x > 0 ). Jeżeli x będzie 0 funkcja when zwróci nil. conj z nil i x daje (x). Ostatnim x przed warunkiem jest 1, pierwszym jest 5. Czyli łącząc do początku listy od 1 do 5 mamy listę w kolejności odwrotnej.

T1: (= __ (   (fn foo [x]                       (when (> x 0)                             (conj (foo (dec x))                                   x)))                5 )) E1:  '(5 4 3 2 1) E2: [5 4 3 2 1]

Problem 23: Rearranging Code: ->

Makro -> pozwala wykonywać na danych operacje sekwencyjnie zamiast zagnieżdżać w nawiasy. Co my tutaj mamy?

Funkcja reverse odwraca kolejność elementów w kolekcji, czyli będzie: [6 3 1 4 5 2]. rest zwraca wszystkie elementy oprócz pierwszego, więc: [3 1 4 5 2]. sort porządkuje elementy w kolejności rosnącej: [1 2 3 4 5]. Zadanie polega na zgadnięciu ostatniej funkcji, która po zastosowaniu na ostatnim wyniku zwróci 5.

T1: (= (__ (sort (rest (reverse [2 5 4 1 3 6]))))        (-> [2 5 4 1 3 6] reverse rest sort __)        5) E1: last E2: #(first (reverse %))

Uwaga, może nie zadziałać na 4Clojure mimo, że odpowiedzi są poprawne.

Problem 24: Recurring Theme

Clojure posiada konstrukcję, która pozwala na zapętlanie bez zapychania stosu - taki odpowiednik for. W językach takich jak C, Java kolejne wywołania funkcji powodują, że na stosie odkładane są kolejne ich parametry. Dodatkowo na stosie odkładane są zmienne lokalne funkcji. Jako, że stos nie jest nieskończony może się dość szybko zapchać, szczególnie, gdy stosujemy pętle rekurencyjne, które polegają na wywołaniach funkcji przez samą siebie.
Jako anegdotę dodam, że twórcom gry MMO : Eve Online udało się osiągnąć limit jaki stawia stos C. Wtedy w obroty wzięli odnogę Pyhona: Stackless, który nie zużywa stosu. Jako, że Python ma problemy ze skalowalnością horyzontalną (winowajca: GIL) ciekawi mnie jak rozwiązali sprawę komunikacji pomiędzy procesami działającymi na wielu rdzeniach.
Wracając do tematu. Konstrukcją Clojure, która nie powoduje przepełnień stosu jest loop - recur .
loop bierze wektor zmiennych tymczasowych podobnie do let, które są aktualizowane przez funkcję recur.
Rozkładając na czynniki pierwsze T1 mamy zainicjalizowaną zmienną x wartością 5 i sekwencję result jako pusty wektor: []. Idąc dalej mamy test x > 0. Jeżeli x będzie większe od 0 zostanie wywołana funkcja recur z nowym x pomniejszonym o jeden, a do pustego result zostanie dodany wynik powiększenia x o 2. Jeżeli warunek x > 0 nie będzie spełniony zostanie zwrócona aktualna wartość result. Czyli zaczynając od 5 do 1 włącznie zostanie zbudowany wektor [7 6 5 4 3].

T1: (= __       (loop [x 5              result []]         (if (> x 0)           (recur (dec x) (conj result (+ 2 x)))           result))) E1: [7 6 5 4 3]

Problem 25: Rearranging Code: ->>

Makro ->>. Służy do poprawy czytelności kodu. Jest to rozwinięta wersja ->, gdzie funkcje były jedno-parametrowe. Makro bierze dane z pierwszego argumentu i wstawia je na koniec listy podanej w kolejnym argumencie. Jeżeli są dodatkowe listy, to wynik poprzedniego działania jest wstawiany na koniec kolejnej. Na końcu tak zbudowana lista jest ewaluowana (wykonywana).
W zadaniu mamy wektor [2 5 4 1 3 6], który jest skracany o dwa elementy z przodu funkcją drop. Wynik to : [4 1 3 6] Następnie z wyniku brane są trzy pierwsze elementy : [4 1 3]. Kolejna rzecz, to za pomocą map zwiększenie elementów o 1, dając: [5 2 4].
Teraz trzeba znaleźć taką funkcję, która zrobi jakoś z tych danych 11. Okazuje się, że suma elementów to 11, więc użyję + wraz z funkcją operująca na listach.

T1: (= (__ (map inc (take 3 (drop 2 [2 5 4 1 3 6]))))        (->> [2 5 4 1 3 6] (drop 2) (take 3) (map inc) (__))        11) E1: reduce + E2: apply +

Problem 26: A nil key

Zadanie polega na znalezieniu funkcji, która pobierze dwa argumenty: klucz i mapę, oraz zwróci prawdę jeżeli klucz istnieje w tej mapie i ma wartość nil. Jest to dość ciekawe zadanie, bo mapa zwraca nil jeżeli klucz nie istnieje. Jak więc dowiedzieć się, że klucz istnieje i ma wartość nil?

Potrzebne będą dwa porównania. Jedno sprawdza, czy klucz istnieje za pomocą funkcji contains?, a drugie, czy wartość przypisana do klucza jest nil. Stąd rozwiązanie E1. Drugie rozwiązanie E2 jest lepsze, bo nie iteruje dwukrotnie po mapie tylko raz. W pętli loop biorę pierwszą parę klucz-dane z mapy i sprawdzam, czy nie dostaję nil. Dostanę nil jeżeli mapa będzie pusta. Jeżeli jest pusta zwracam falsz. Jeżeli nie sprawdzam, czy pierwszy element pary to mój klucz i przy okazji sprawdzam czy drugi to nil. Jeżeli to nasz klucz i ma wartość nil zwracam true. W przeciwnym wypadku biorę kolejny element z mapy oraz jej resztę i przekazuję jako nowe wartości do loop za pomocą recur.
Update:

Przykład E3 wykorzystuje możliwość przypisania do zmiennej lokalnej wartości domyślnej jeżeli klucz w mapie nie istnieje. Trzeba jednak uważać, by wartość domyślna nie mogła wystąpić w danych, bo dostaniemy niepoprawny wynik.

T1: (true?  (__ :a {:a nil :b 2})) T2: (false? (__ :b {:a nil :b 2})) T3: (false? (__ :c {:a nil :b 2})) E1: #(and (contains? %2 %1) (nil? (%2 %1))) E2: #(let [klucz %1 mapa %2]         (loop [p (first mapa) r (rest mapa)]                  (if (nil? p)                      false                      (if (and (= (first p) klucz) (nil? (second p)))                              true                              (recur (first r) (rest r)))))) E3: #(let [dane (%1 %2 :not_exist)]         (if (nil? dane)         true         false))