Poczytaj mi Clojure, cz. 10: Komparatory

Komparatory to funkcje, które służą do porównywania elementów kolekcji i/lub sekwencji. Są wykorzystywane 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 dwustanowe 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:

Sposób uporządkowania może być rosnący lub malejący, z kolei rodzaje porządków można ze sobą łączyć. Na przykład dla niektórych struktur danych, stosując najpierw porównywanie liczby ich elementów (porządek mnogościowy), a gdy będzie ona równa, korzystając 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 podany element powinien poprzedzać drugi;
  • 0 – jeżeli pozycja podanych elementów powinna być taka sama;
  • 1 lub większą – jeżeli pierwszy podany element powinien następować za drugim.

Pierwszy argument musi implementować interfejs Comparable.

Funkcja compare nie potrafi porównywać danych różnych typów. Próba porównania takich wartości spowoduje zgłoszenie wyjątku java.lang.ClassCastException. Wyjątkiem jest tu wartość nil, która zawsze będzie uznawana za następującą po porównywanej wartości (chyba, że też jest nią 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).
Przykłady użycia funkcji compare
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 jeśli 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. użytkowane przez nas dane pewnych odmiennych typów wymagać mogą porównywania. 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ą (typ java.lang.Integer, 32-bitowa wartość ze znakiem), 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 przed drugim;
  • 0 dla przypadku, gdy elementy są równe pod względem pozycji
  • 1 lub większą dla zakomunikowania, że element pierwszy powinien znajdować się za drugim.

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

  • true, jeżeli pierwszy podany jako argument element powinien być umieszczony przed drugim (kolejność zastana względem kolejności przekazywanych argumentów);
  • false w przeciwnym razie (dla kolejności odwróconej lub takiej samej).

Odwracalność

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

Przykład odwracalności komparatorów
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 komparatorze 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ć zaprzeczeniem założenia o unikatowości kluczy.

Porównanie zachowania komparatorów w odniesieniu do sortowanych map
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 definiowana z użyciem fn, defn czy lambda-wyrażenia funkcja wyposażona jest 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 funkcji 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).
Przykłady użycia funkcji comparator
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 mieli do czynienia z dwoma jego wywołaniami. Na przykład jeśli 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:

Przykład próby sortowania wektora złożonego z danych różnych typów
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 “dokonać niemożliwego” i pomóc funkcji sort w uszeregowaniu zaproponowanego zestawu danych.

Założenia:

  1. Jeżeli mamy do czynienia ze słowem kluczowym lub symbolem, to dokonujemy konwersji do łańcucha znakowego.
  2. Jeżeli łańcuch znakowy reprezentuje wartość numeryczną, to 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, to dokonujemy porównania leksykograficznego (słownikowego).
  4. Jeżeli porównujemy typ numeryczny z nienumerycznym, to numeryczny powinien być zawsze pierwszy.
  5. Wewnętrznie skorzystamy z compare, aby dokonywać porównań tych samych typów.
Przykład definiowania i użycia komparatora
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.

Przykład wywołania komparatora w wyrażeniu warunkowym
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.

Przykład użycia komparatora w wywołaniu funkcji sort
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):

Ten materiał jest częścią większej całości, którą można zobaczyć odwiedzając poniższy odnośnik:

Komentarze