Komparatory to funkcje, które służą do porównywania wartości elementów kolekcji. Zastosowanie znajdują przede wszystkim w operacjach sortowania. W Clojure każda funkcja może być komparatorem, jeżeli tylko będziemy przestrzegali odpowiednich wytycznych.

Komparatory

Komparator (ang. comparator) to funkcja porównująca, która przyjmuje dwa argumenty i zwraca wartość określającą w jakiej relacji kolejności wartości tych argumentów powinny być uporządkowane. Używane są do m.in. do sortowania zbiorów danych (np. kolekcji czy sekwencji).

Możemy mieć do czynienia z dwoma typami komparatorów:

• komparatory trójstanowe (ang. 3-way comparators) – zwracające jedną z trzech wartości wyrażających relację kolejności między pierwszym a drugim podanym elementem: pierwszy (kolejność zastana – pierwszy element powinien być umieszczony wcześniej), równy (kolejność zastana – pierwszy element powinien być umieszczony na tej samej pozycji lub pozycja względem drugiego nie ma znaczenia), drugi (kolejność wymaga zmiany – pierwszy element powinien być umieszczony na dalszej pozycji niż drugi);

• komparatory dwustanowe (ang. 2-way comparators) – zwracające jedną z dwóch wartości wyrażających relację kolejności między pierwszym a drugim elementem: pierwszy (pierwszy element powinien być umieszczony przed drugim), drugi (pierwszy element powinien być umieszczony za drugim).

Komparatory dwustanowe bywają też nazywane komparatorami boolowskimi (ang. boolean comparators) i przez niektóre funkcje mogą być wywoływane dwukrotnie, aby dokonać sprawdzenia, czy zachodzi równość elementów.

Funkcje implementujące komparatory trójstanowe zwracają zwykle liczbę całkowitą, a komparatory dwu stanowe wartość logiczną (true lub false).

W zależności od typu danych możemy wyróżnić różne rodzaje porządków, które będą efektem pracy funkcji porównujących. Na przykład:

• porządek liczbowy (np. porządek liczb całkowitych, porządek liczb zmiennoprzecinkowych czy porządek ułamków) dla danych numerycznych lub danych asocjacyjnych identyfikowanych numerycznie;

• porządek leksykograficzny dla danych alfabetycznych (np. łańcuchów znakowych, symboli czy słów kluczowych) lub danych asocjacyjnych identyfikowanych słownikowo;

• porządek mnogościowy dla danych złożonych, które różnią się liczbą elementów.

Sposób uporządkowania może być rosnący lub malejący, a rodzaje porządków można łączyć. Na przykład dla niektórych struktur danych zastosujemy najpierw porównywanie liczby ich elementów (porządek mnogościowy), a gdy będzie ona równa, skorzystamy z algorytmu bazującego na porządku liczbowym lub leksykograficznym kolejnych elementów z obu zestawów.

Komparator domyślny, compare

Domyślnym komparatorem w języku Clojure jest funkcja compare. Przyjmuje ona dwa argumenty, którymi powinny być wartości przeznaczone do porównania, a zwraca liczbę całkowitą określającą jeden z trzech możliwych stanów wyjściowych:

• -1 lub mniejszą – jeżeli pierwszy element powinien poprzedzać drugi;
• 0 – jeżeli pozycja elementów powinna być taka sama;
• 1 lub większą – jeżeli pierwszy element powinien następować po drugim.

Pierwszy argument musi być instancją typu implementującego interfejs Comparable.

Funkcja compare nie potrafi porównywać wartości różnych typów. Próba porównania takich danych spowoduje zgłoszenie wyjątku java.lang.ClassCastException. Wyjątkiem jest tu wartość nieustalona nil, która zawsze będzie uznawana za następującą po porównywanej wartości (chyba, że tą drugą też będzie nil – wtedy będziemy mieli do czynienia z równą pozycją).

Domyślny komparator potrafi porównywać między innymi: wartości numeryczne, łańcuchy znakowe, pojedyncze znaki, słowa kluczowe, symbole, wektory, zbiory, mapy, obiekty File oraz URI i inne obiekty, które implementują Comparable.

Użycie:

• (compare x y).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

(compare 1 2)            ; => -1
(compare 1 1)            ; =>  0
(compare 2 1)            ; =>  1

(compare [1 2] [2 1])    ; => -1
(compare [1 2] [1 2])    ; =>  0
(compare [2 1] [1 2])    ; =>  1

(compare [1 2] [2 1 0])  ; => -1
(compare [1 2] [0 1 2])  ; => -1
(compare [2 1] [0 1 2])  ; => -1

(compare "abc" "cba")    ; => -2
(compare "abc" "abc")    ; =>  0
(compare "cba" "abc")    ; =>  2

(sort compare [3 2 1])   ; => (1 2 3)

Zauważmy, że w liniach 5–7 poszczególne elementy wektorów są porównywane z zastosowaniem zasad porządku liczbowego, z kolei w liniach 9–11 mamy do czynienia z porządkiem mnogościowym (porównywana jest liczba elementów), ponieważ rozmiary wektorów są różne.

Programiści innych języków programowania mogą zdziwić się takim algorytmem porównywania, ponieważ dominującą tendencją jest stosowanie porządku liczbowego lub leksykograficznego, nawet gdy porównywane struktury są różnej liczebności. Jeżeli potrzebujemy w taki właśnie sposób porównywać kolekcje, możemy uzupełnić mniejszą z nich pustymi elementami (np. wartościami nil) lub stworzyć własny komparator.

Tworzenie komparatorów

Komparator domyślny może nie spełniać naszych oczekiwań w kwestii porównywania wartości, np. porównywać zechcemy dane odmiennych typów. W takich przypadkach warto rozważyć utworzenie własnego komparatora.

Właściwości komparatorów

Zanim przystąpimy do definiowania odpowiedniej funkcji powinniśmy zadbać o to, aby nasz komparator spełniał ogólne założenia funkcji porównującej, a także zdecydować o jego charakterystycznych cechach.

Stanowość

Komparator trójstanowy powinien zwracać liczbę całkowitą (32–bitową wartość ze znakiem typu java.lang.Integer), a dwustanowy wartość logiczną true lub false.

W przypadku komparatora trójstanowego należy sprawić, aby funkcja zwracała wartość:

• -1 lub mniejszą, gdy pierwszy element powinien być umieszczony wcześniej;
• 0 dla przypadku, gdy elementy są równe pod względem pozycji;
• 1 lub większą, gdy pierwszy element powinien być umieszczony później.

W przypadku komparatora dwustanowego należy założyć, że funkcja powinna zwracać:

• true, gdy pierwszy element powinien być umieszczony wcześniej;
• false, gdy pierwszy element powinien być umieszczony później.

Wartość false w komparatorze dwustanowym może komunikować też, że pozycja porównywanych elementów powinna być zachowana.

Odwracalność

Komparator musi być odwracalny, tzn. gdy zamienimy miejscami wartości przekazywanych mu argumentów, powinniśmy uzyskać odwrotne decyzje odnośnie kolejności komunikowanej zwracaną wartością.

1
2
3
4

(compare 1 2)  ; => -1
(compare 2 1)  ; =>  1
(< 1 2)        ; =>  true
(< 2 1)        ; =>  false

Porządek liniowy

Ważne jest, aby zbiór możliwych wartości, które będą porównywane z użyciem komparatora cechował porządek liniowy, tzn. taki, gdzie każdy element może być porównany z innym z tego zbioru. Nie wyklucza to oczywiście porównywania danych różnych typów pod warunkiem, że w funkcji komparatora zastosujemy koercję w odniesieniu do przyjmowanych argumentów.

Duplikaty kluczy

Budując komparator dla sortowanych kolekcji asocjacyjnych (np. sortowanych map czy zbiorów), należy unikać stanu wyjściowego, który komunikuje, że pozycje elementów są równe, ponieważ spowoduje to, że oba porównywane elementy zostaną umieszczone w kolekcji wyjściowej, co może być wbrew warunkowi unikatowości kluczy.

1
2

(sorted-map-by <  1 "a", 2 "b", 1 "x")  ; => {1 "x" 2 "b"}
(sorted-map-by <= 1 "a", 2 "b", 1 "x")  ; => {1 "x" 1 "a" 2 "b"}

„Lub równe”

Nie powinno stosować się dwustanowych komparatorów, których decyzje bazują na operatorze relacyjnym „mniejsze lub równe” bądź „większe lub równe”, ponieważ prowadzić to może do nieprzewidzianych rezultatów podczas porównywania danych (m.in. wspomniane wcześniej duplikaty w przypadku struktur asocjacyjnych):

1
2

(sorted-set-by <  3 2 1 3)  ; => {1 2 3}
(sorted-set-by <= 3 2 1 3)  ; => {1 2 3 3}

Interfejs Comparator

Funkcja porównująca powinna implementować interfejs java.util.Comparator. W Clojure każda funkcja definiowana z użyciem fn, defn czy lambda-wyrażenia jest wyposażona w ten interfejs. Dla funkcji utworzonych w inny sposób (np. metod pochodzących z Javy) można użyć funkcjonału comparator.

Funkcja comparator

Funkcja comparator służy do generowania obiektów typu funkcyjnego wyposażonych w interfejs Comparator. Przyjmuje ona jeden argument, którym powinien być funkcyjny obiekt, a zwraca funkcję, która wywołuje podany predykat i na podstawie jego rezultatu zwraca wartość -1, 0 lub 1.

Funkcja ta przydaje się kiedy:

• chcemy jako komparatora użyć obiektu funkcyjnego, który z jakichś przyczyn nie implementuje java.util.Comparator;

• chcemy stworzyć komparator trójstanowy na bazie funkcji, która zwraca wartość logiczną.

Użycie:

• (comparator predykat).

1
2
3
4
5
6

(< 0 1)               ; =>  true
(< 1 1)               ; =>  false
(< 1 0)               ; =>  false
((comparator <) 0 1)  ; => -1
((comparator <) 1 1)  ; =>  0
((comparator <) 1 0)  ; =>  1

W istocie funkcja comparator jest bardzo prosta. Jej ciałem jest następujące wyrażenie (pred to przekazany jako argument predykat):

1
2
3
4

(cond
  (pred x y) -1
  (pred y x)  1
  :else       0)

Widzimy więc, że dla predykatu dwuwartościowego (zwracającego np. true lub false) będziemy w przypadku równej kolejności wartości mieli do czynienia z jego dwoma wywołaniami. Gdy predykatem jest funkcja wyrażająca relację „mniejsze niż”, to pierwszy warunek nie zostanie spełniony, drugi również, a zwrócona będzie wartość domyślna 0.

Własna funkcja porównująca

Spójrzmy co się stanie, gdy spróbujemy posortować wektor zawierający klucze, symbole i liczby:

1
2
3

(sort [:b 1 :a 'd 2 'c])
; >> java.lang.ClassCastException:
; >>   java.lang.Long cannot be cast to clojure.lang.Keyword

Otrzymaliśmy komunikat o wystąpieniu wyjątku ClassCastException, który informuje nas, że nie można było rzutować liczby wyrażonej obiektem klasy Long do słowa kluczowego (obiektu klasy Keyword). Gdy wywołamy funkcję pst, przekonamy się, że miejscem, w którym doszło do usterki, był kod funkcji compare, czyli wbudowanego komparatora. Przyczyną problemu był fakt, że funkcja ta nie potrafi porównywać danych różnych typów.

Funkcja compare-on-steroids

Spróbujmy stworzyć taki komparator, który byłby w stanie pomóc funkcji sort w uszeregowaniu zaproponowanego zestawu danych.

Założenia:

1. Jeżeli mamy do czynienia ze słowem kluczowym lub symbolem, dokonujemy konwersji do łańcucha znakowego.

2. Jeżeli łańcuch znakowy reprezentuje wartość numeryczną, dokonujemy konwersji do typu, który tę wartość wyraża.

3. Jeżeli łańcuch znakowy nie reprezentuje wartości numerycznej, a jest porównywany z innym łańcuchem, dokonujemy porównania leksykograficznego (słownikowego).

4. Jeżeli porównujemy typ numeryczny z nienumerycznym, numeryczny powinien być zawsze pierwszy.

5. Wewnętrznie skorzystamy z compare, aby dokonywać porównań tych samych typów.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(defn cos-adjust-type [x]
  (let [new-x (cond
                (keyword? x) (str x)
                (symbol?  x) (str x)
                :else x)
        str-x (when (string? new-x) (read-string new-x))]
    (if (number? str-x) str-x new-x)))

(defn compare-on-steroids [x y]
  (let [new-x (cos-adjust-type x)
        new-y (cos-adjust-type y)
        typ-x (type new-x)
        typ-y (type new-y)
        c-fn  #(compare new-x new-y)]
    (cond
      (= typ-x typ-y)  (c-fn)
      (nil?    typ-x)  (c-fn)
      (nil?    typ-y)  (c-fn)
      (number? new-x) -1
      (number? new-y)  1
      :else (c-fn))))

(sort compare-on-steroids [:b 1 :a 'd 2 'c])
; => (1 2 :a :b c d)

Użytkowanie komparatorów

Wywoływanie bezpośrednie

Funkcję porównującą możemy wywoływać bezpośrednio, np. w celu uwarunkowania wykonywania się programu. Zaletą użycia komparatora może być w tym przypadku możliwość pracy z danymi różnych typów.

1
2
3
4
5
6
7

(let [x 10 y 20]
  (case (compare x y)
    (-1 0) "mniejsze lub równe"
    1      "większe"
    "bardzo różne"))

; => "mniejsze lub równe"

Przekazywanie do funkcji

Najczęstszym sposobem korzystania z komparatorów jest ich przekazywanie do funkcji wyższego rzędu, gdzie będą wywoływane w celu porównania kolejnych elementów kolekcji lub sekwencji.

Funkcja sortująca

Weźmy za przykład wbudowaną funkcję sortującą sort, której przekazać możemy komparator. Będzie on wywoływany podczas szeregowania elementów w wynikowej sekwencji.

1
2

(sort compare [:z :c :b :a])
; => (:a :b :c :z)

Funkcjonały korzystające z komparatorów

W Clojure pewna liczba funkcji wyższego rzędu jako jeden z argumentów przyjmuje komparator. Są to głównie funkcje związane z sortowaniem elementów kolekcji i/lub sekwencji na żądanie lub z tworzeniem tzw. sortowanych kolekcji (zachowujących określony porządek podczas następczego dostępu):

•          sort – sortuje elementy,
•       sort-by – sortuje elementy wg. wartości zwróconej przez funkcję,
• sorted-set-by – tworzy zbiór sortowany,
• sorted-map-by – tworzy mapę sortowaną,
•        subseq – tworzy sekwencję z zakresu elementów,
•       rsubseq – tworzy odwróconą sekwencję z zakresu elementów.