Haskell posiada wiele rozszerzeń zaimplementowanych w GHC. Jednym z najbardziej znaczących okazało się Functional Dependecies[1], które odmieniło życie wielu programistom Haskella. Niektórzy jednak narzekali, że nie jest to zbyt funkcyjne podejście i w końcu powstało inne bardziej funkcyjne. Mianowicie TypeFamilies[2]. Nie chcę tu opisywać na czym polegają funkcyjne zależności i tym bardziej jak to samo wyrazić za pomocą "rodzin typów". To o czym chcę dzisiaj napisać to to co dodatkowo umożliwiają rodziny typów czyli funkcje na poziomie typów (Type Level Functions).
O co chodzi
Funkcje na poziomie typów to takie funkcje, które wykonuje kompilator, a ich treść zapisana jest w typie. Brzmi to trochę zawile więc najlepiej będzie pokazać to na przykładzie. Zaczniemy od końca. Powiedzmy, że chciałbym aby moja funkcja mogła zostać wywołana tylko na argumencie, którego największy wspólny dzielnik (NWD czy też GCD) z liczbą 4 to 4. Próba wywołania jej na innym argumencie powinna skończyć się paniką kompilatora :)
fun :: (Nat a, GCD Zero a Four ~ Four) => a -> Int
Właśnie tak będzie wyglądać typ naszej funkcji. Wyjaśnienie:
- Nat a - a jest liczbą naturalną, treść klasy Nat pokażę niżej,
- GCD Zero a Four - typ GCD składa się z 3 parametrów: GCD r a b oznacza: reszta z dzielenia(r), pierwszej liczby(a) z drugą(b),
- i wreszcie ~ Four - odpowiednik = w typach, innymi słowy GCD 0 a 4 = 4 czyli największy wspólny dzielnik liczby a i 4 to 4.
Liczby naturalne
Zaczniemy od zdefiniowania liczb naturalnych:
Zero zaskakująco oznacza 0. Natomiast Succ n oznacza kolejną liczbę po n czyli Succ Zero oznacza 1. Ciężko byłoby nam definiować większe liczby więc dla wygody zdefiniowane są dodatkowe typy jak One, Two, Four itd.
Klasa Nat reprezentuje liczby naturalne i zawiera funkcję toInt konwertującą liczbę naturalną do Inta. Godna uwagi jest implementacja toInt dla Succ n. Otóż wynika ona z tego, że nie posiadamy konstruktorów ani typu Zero ani też Succ n. Wykorzystujemy więc specjalną zmienną undefined, która może udawać dowolny typ i rzutujemy ją na typ n wewnątrz Succ, który musi być klasy Nat. Aby w ogóle móc w ten sposób zaimplementować tę funkcję potrzebne jest rozszerzenie ScopedTypeVariables[3], czyli najlepiej dodać sobie w pliku taką linijkę:
{-# LANGUAGE ScopedTypeVariables #-}
Możemy przetestować sobie w ghci to co do tej pory napisaliśmy:
> toInt (undefined::Four)
4
Type Families
Przyszła pora na zdefiniowanie naszej funkcji liczącej GCD. Funkcja będzie oczywiście realizowana na poziomie typów danych i do tego celu użyjemy rozszerzenia TypeFamilies więc od razu dodajmy sobie na początek pliku:{-# LANGUAGE TypeFamilies #-}
Przejdźmy zatem do kodu:
Jeżeli ktoś nie widział nigdy wcześniej tego rozszerzenia to może go zaskoczyć słowo instance. To słowo kluczowe przede wszystkim sugeruje, że rodziny typów są otwarte tak samo jak klasy. Oznacza to, że ich "instancje" mogą być rozrzucone po plikach i zawsze można dołożyć kolejne. W przeciwieństwie chociażby do funkcji, która w całości musi być zdefiniowana w jednym pliku.
I co my tu mamy? Rekursywnie zaimplementowany algorytm liczenia największego wspólnego dzielnika. Mamy 3 warunki brzegowe:
- gdy reszta z dzielenia to 0 i pierwszy argument to 0 to GCD Zero Zero a = a,
- gdy reszta z dzielenia to 0 i drugi argument to 0 to GCD Zero a Zero = a
- gdy dwie liczby zeszły do zera to GCD r Zero Zero = r,
No to sprawdźmy to od razu w GHCi:
> toInt (undefined::(GCD Zero Eight Four))
4
> toInt (undefined::(GCD Zero Eight Two))
2
Treść funkcji
Pozostało nam napisać testową funkcję, która przyjmuje tylko liczby podzielne przez 4 po czym je wypisuje. Wykorzystując typ funkcji z początku postu możemy napisać na przykład coś takiego:
fun :: (Nat a, GCD Zero a Four ~ Four) => a -> Int
fun a = toInt a
Spróbujmy zatem wywołać ja w GHCi:
> fun (undefined::Eight)
8
> fun (undefined::Six)
<interactive>:2:1:
Couldn't match type `Zero' with `Two'
Expected type: Four
Actual type: GCD Zero Six Four
In the expression: fun (undefined :: Six)
In an equation for `it': it = fun (undefined :: Six)
Jak widać funkcja nie może zostać wywołana dla szóstki, gdyż nie jest podzielna przez 4 ale dla ósemki działa wyśmienicie.
Kiedy można to wykorzystać
Nie wykorzystamy tego na pewno dla argumentów podawanych dynamicznie, tj. z zewnętrznych źródeł jak baza danych, plik, klawiatura itd. Kompilator w żaden sposób nie sprawdzi czy liczba, którą wpiszemy podczas uruchamiania programu jest podzielna przez 4. No bo niby skąd on ma wiedzieć co wpiszemy?
Ale możemy to wykorzystać przy argumentach podawanych na sztywno w kodzie źródłowym. Przypuśćmy, że mamy dwie funkcje. Jedna która działa na wszystkich liczbach i druga, która działa na podzielnych przez 4. Oczywiście argumenty przekazujemy na sztywno. Mamy dwa wyjścia, albo napisać dwa różne typy danych, tzn. liczby podzielne przez 4 i dowolne liczby, albo utworzyć tylko jeden typ danych tak jak w naszym przykładzie i użyć rodzin typów by móc wymusić na nich własności, których oczekujemy.
Podsumowanie
Haskell po raz kolejny wprowadza programowanie na wyższy poziom. Być może rodziny typów to nie jest rzecz, którą da się często wykorzystać (przynajmniej jeśli chodzi o funkcje na typach danych) ale można w ten sposób poradzić sobie z kilkoma problemami. Więcej o rodzinach typów można znaleźć tutaj. Pełen kod użyty w tym poście do podglądu tutaj.
Brak komentarzy:
Prześlij komentarz