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:
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))
|
