Z pogranicza

Haskell 1) Wartości i typy

  • 2007-01-06 12:21
  • 4 komentarze
  • 2526 odsłon
  • Oceń ten tekst jako pierwszy
Tłumaczenie: Maciej Kasprzyk "Kapustka", [email protected]</email> Warszawa 2002.

Spis treści

          1 Wprowadzenie
          2 Wartości, Typy i Inne
          3 Typy wielopostaciowe
          4 Definiowanie typów
               4.1 Typy rekurencyjne
          5 Synonimy typów
          6 Wbudowane typy nie są wyjątkowe
               6.1 Fabrykatory i ciągi arytmetyczne
               6.2 Napisy


Wprowadzenie


Gdy pisaliśmy ten przewodnik nauczanie programowania, jak i nauczanie programowania funkcyjnego nie były naszym celem. Tekst ten ma służyć jako uzupełnienie Haskell Report [4], który jest skądinąd zwartym, formalnym opisem języka. Naszym zadaniem jest dostarczenie łagodnego wprowadzenia do Haskell'a dla kogoś, kto ma doświadczenie z co najmniej jednym innym językiem, najlepiej funkcyjnym (albo prawie funkcyjnym jak np. ML albo Scheme). Jeśli czytelnik pragnie dowiedzieć się więcej o paradygmacie programowania funkcyjnego, to polecamy tekst Bird'a Introduction to Functional Programming [1] lub Davie'go An Introduction to Functional Programming Systems Using Haskell [2]. Pożyteczny przegląd języków programowania funkcyjnego i technik, w tym obejmujących część z konstrukcyjnych założeń Haskell'a, znajduje się w [3].

Język programowania Haskell znacząco się rozwinął od chwili swoich narodzin w 1987 roku. Ten przewodnik opisuje Haskell 98. Starsze wersje języka są w tej chwili zdezaktualizowane a użytkownikom silnie zaleca się korzystanie z Haskell 98. Ponadto istnieje wiele powszechnie wprowadzanych rozszerzeń Haskell 98. Nie są one jeszcze formalną częścią języka i jako takie nie są opisane w tym przewodniku.

Naszą generalną strategią przy przedstawianiu elementów języka jest: zarysowanie idei, zdefiniowanie kilku terminów, pokazanie przykładów i odesłanie do Haskell Report po szczegóły. Przy czym silnie zalecamy, aby czytelnik przy pierwszym czytaniu pominął szczegóły. Z drugiej strony, Haskell Standard Prelude (znajdujące się w dodatku "A" Haskell Report jak i standardowych bibliotekach znalezionych w Library Report [5]) zawiera wiele użytecznych przykładów kodu Haskell'a i materiał ten polecamy po ukończeniu niniejszego wprowadzenia. Dostarczy to czytelnikowi nie tylko poglądu na to, jak rzeczywisty kod Haskell'a wygląda, ale też przyzwyczai do zbioru przedefiniowanych funkcji i typów Haskell'a.

Ostatecznie  - bogatym źródłem informacji o języku i jego implementacjach jest strona http://haskell.org.

( Postanowiliśmy nie przedstawiać na wstępie nadmiaru zasad składni leksykalnej, raczej wyprowadzamy je w miarę potrzeb, stopniowo i zamykamy w nawiasach tak jak ten paragraf. Jest to rażący kontrast do układu Haskell Report, niemniej to Report pozostaje autorytatywnym źródłem dotyczącym szczegółów (odwołania takie jak §2.1 dotyczą rozdziałów w Report). )

Haskell jest językiem mocno typowanym [w oryginale "typeful" to więcej niż polski odpowiednik "mocne typowanie", które oznacza, że typ każdego wyrażenia musi być określony już na etapie kompilacji - przyp. tłum.]: nowi użytkownicy powinni od samego początku uświadomić sobie siłę i złożoność systemu typowania w Haskell'u. Dla osób, których jedyne doświadczenia to relatywnie "słabo" typowane języki takie jak Perl, Tcl, lub Scheme, przestawienie się może być trudne, natomiast dla użytkowników języków Java, C, Modula, lub nawet ML, zmiana powinna być łatwiejsza, lecz nadal nie znikoma, gdyż system typowania Haskell'a jest odmienny i bardziej urozmaicony od większości języków programowania.

Wartości, Typy i Inne


Ponieważ Haskell jest językiem czysto funkcyjnym, wszelkie obliczenia są dokonywane poprzez ewaluowanie wyrażeń (członów syntaktycznych), w celu dostarczenia wartości (abstrakcyjne byty, które odczytujemy jako odpowiedzi). Każda wartość ma przypisany typ. (Intuicyjnie możemy postrzegać typ jako zbiór wszystkich możliwych do obrania wartości). Przykładami wyrażeń są atomowe wartości - liczba całkowita 5, znak 'a', funkcja x -> x+1 jak i wartości strukturalne takie jak ciąg [1, 2, 3] lub para ('b', 4).

Tak jak wyrażenia wskazują na wartości, wyrażenia typujące (ang. type expressions) są syntaktycznymi członami, które wskazują na typy. Przykładami są typy atomowe Integer (liczby całkowite nieskończonej precyzji), Char (typ znakowy), Integer -> Integer (funkcja odwzorowująca Integer w Integer), jak i typy złożone [Integer] (ciąg liczb całkowitych) i (Char, Integer) (pary, w których poprzednik jest znakiem a następnik jest liczbą całkowitą).
W Haskell'u wszystkie wartości są "pierwszorzędne" (ang. "first-class") - mogą być przekazane do funkcji jako jej argumenty, zwrócone jako wynik, umieszczone w strukturach danych, itd. Z drugiej strony typy nie są w Haskell'u pierwszorzędne. W pewnym sensie typy opisują wartości, a połączenie wartości z jej typem jest nazywane typowaniem (ang. typing). Używając wymienionych wcześniej typów i wartości, możemy rozpisać następujące typowania:

5 ::        Integer
'a' ::        Char
inc ::        Integer -> Integer
[1, 2, 3] ::        [Integer]
('b', 4) ::        (Char, Integer)


Symbol "::" należy odczytywać jako "ma typ".

Funkcje w Haskell'u są definiowane za pomocą sekwencji równań. Np. funkcja inc może być zdefiniowana pojedynczym równaniem:
inc n = n+1


Równanie jest przykładem deklaracji. Innym rodzajem deklaracji jest deklaracja wzorca (ang. type signature declaration) (§4.4.1), za pomocą której możemy jawnie deklarować typowanie funkcji inc:

inc :: Integer -> Integer


Do tematu deklaracji funkcji powrócimy w Rozdziale 3.
Jeśli chcemy, z edukacyjnych powodów, pokazać że wyrażenie e1 przechodzi w inne wyrażenie, lub wartość e2, to będziemy pisać:

e1 => e2

Przykładowo:
inc (inc 3) => 5


Statyczny  system typowania Haskell'a definiuje formalne zależności pomiędzy typami a wartościami (§4.1.3) i sprawdza, czy programista nie próbował błędnie dopasować typów. Np. Zazwyczaj nie możemy dodać do siebie dwóch znaków, więc wyrażenie 'a'+'b' jest błędne. Główna zaleta języków statycznie typowanych jest powszechnie znana: Wszystkie błędy wynikające z niewłaściwego dopasowywania typu są wykrywane w czasie kompilacji (ang. compile-time error). Nie oznacza to, że wszystkie błędy wyłapywane są przez system typowania; wyrażenie takie jak
1/0
z punktu widzenia typowania jest poprawne i dopiero próba jego ewaluacji prowadzi do błędu w czasie wykonania (ang. run-time error). Wciąż jednak, system typowania odnajduje wiele błędów w czasie kompilacji, pomaga użytkownikowi zrozumieć program i umożliwia kompilatorowi wygenerowanie wydajniejszego kodu (znika potrzeba etykietowania i testowania typów w czasie wykonania).

Dodatkowo, system typowania upewnia się, czy dostarczone przez użytkownika wzorce są poprawne. W rzeczywistości jest on na tyle sprawny, że poza nielicznymi przypadkami opisanymi dalej, możemy pomijać pisanie wzorców; mówimy że system typowania wnioskuje poprawny typ za nas. Niemniej rozsądne umieszczanie wzorców, jak ten który podaliśmy dla inc, jest dobrym pomysłem, gdyż wzorce są bardzo wydajną formą dokumentacji i pomagają w lokalizacji błędów.


[Czytelnik prawdopodobnie zauważył, że identyfikatory wskazujące na typy, takie jak Integer lub Char piszemy z wielkiej litery, natomiast identyfikatory wskazujące na wartości takie jak inc, piszemy z małej. Nie jest to tylko konwencja gdyż Haskell wymusza taką pisownię. Ponadto, wielkość pozostałych liter również odgrywa znaczenie i tak foo, fOo i fOO są trzema odmiennymi identyfikatorami.]

Typy wielopostaciowe


Haskell udostępnia typy wielopostaciowe (ang. polymorphic types) - typy, których liczność jest określana względem innych typów (typ jest zbiorem wszystkich możliwych do obrania wartości - przyp. tłum.). Zasadniczo opisują one rodziny typów, np. (∀a)[a] jest, dla każdego typu a, rodziną typów składającą się z ciągów a. Do zbioru tego należą przykładowo ciągi liczb całkowitych (np. [1, 2, 3]), ciągi liter (['a', 'b', 'c']), a nawet ciągi, których elementami są ciągi liczb całkowitych itd. (Warto zaznaczyć, że [2, 'b'] nie należy do tej rodziny, gdyż nie istnieje pojedynczy typ, który zawiera jednocześnie elementy 2 i 'b').

[identyfikatory takie jak użyty powyżej a są nazywane wskaźnikami typu (ang. type variables) (są to zmienne, które wskazują na typ - przyp. tłum.) i są pisane z małej litery, aby je odróżnić od określonych typów takich jak Int. Ponadto, ponieważ Haskell posiada wyłącznie typy zliczane ogólnie, nie istnieje potrzeba jawnego pisania symbolu kwantyfikatora ogólnego, dlatego w powyższym przykładzie po prostu piszemy [a]. Innymi słowy, wszystkie wskaźniki typu domyślnie są kwantyfikowane ogólnie.]

(użyty powyżej znak jest kwantyfikatorem ogólnym (odwrócona litera a, od słowa "all"), którego tradycyjny polski odpowiednik to znak Ʌ, analogicznie znak jest kwantyfikatorem szczegółowym (odwrócona litera e, od słowa "exists") i jego tradycyjnym polskim odpowiednikiem jest znak V - przyp.tłum.).

Ciągi są powszechnie używaną strukturą danych w programowaniu funkcyjnym i są dobrym odniesieniem dla ukazania istoty polimorfizmu. Ciąg [1, 2, 3] jest w istocie skrótowym zapisem ciągu 1 : ( 2 : ( 3 : [ ] ) ), gdzie [ ] jest ciągiem pustym, natomiast ':' jest infiksowym operatorem dopisującym pierwszy argument na początek drugiego. Ponieważ ':' jest prawo skojarzeniowy (inna nazwa "prawo wiązany", czyli jeśli w wyrażeniu jest kilka operatorów o równym priorytecie, wykonywany jest w pierwszej kolejności ten, który stoi najbardziej po prawej stronie - przyp. tłum.), możemy ten ciąg zapisać w postaci 1 : 2 : 3 : [ ].

Jako przykład funkcji zdefiniowanej przez użytkownika i operującej na ciągach, rozważmy problem zliczania elementów w ciągu:

length :: [a] -> Integer
length [ ] = 0
length (x : xs) = 1 + length xs


Ta definicja niemalże mówi sama za siebie. Możemy odczytać równania jako "Długość pustego ciągu wynosi 0, a długość ciągu, którego pierwszym elementem jest x, a resztą jest xs wynosi 1 plus długość ciągu xs." (Warto zwrócić uwagę na konwencję nazywania; 'xs' jest liczbą mnogą 'x' i tak właśnie należy to odczytywać). (w języku angielskim liczbę mnogą tworzymy dopisując końcówkę -s - przyp. tłum.).

Powyższy, wręcz intuicyjny przykład, naświetla jedno zagadnienie, które wymaga omówienia: dopasowywanie szablonu (ang. pattern matching). Po lewych stronach podanych równań znajdują się takie szablony jak [ ] i x : xs. W działającej aplikacji szablony te są przyrównywane do rzeczywistych parametrów ([ ] odpowiada wyłącznie pustemu ciągowi, natomiast x : xs z powodzeniem dopasuje się do każdego co najmniej jednoelementowego ciągu). Jeśli próba dopasowania zakończy się powodzeniem, prawa strona jest obliczana i zwracana jako wynik. Jeśli natomiast porównywany parametr nie pasuje do szablonu, próbowane jest następne równanie a jeśli wszystkie równania zawiodą, wyświetlany jest błąd.

Definiowanie funkcji za pomocą dopasowywania szablonu jest w Haskell'u całkiem powszechne i użytkownik powinien zapoznać się z różnymi dozwolonymi szablonami. Do tematu powrócimy w rozdziale 4.

Funkcja length jest jednocześnie przykładem funkcji polimorficznej. Może być zastosowana dla różnych typów ciągów, w tym np. [Integer], [Char], lub [[Integer]].

length [1, 2, 3] => 3
length ['a', 'b', 'c'] => 3
length [ [1], [2], [3] ] => 3


Poniżej podajemy dwie inne polimorficzne funkcje, z których będziemy korzystać w przyszłości. Funkcja head zwraca pierwszy element ciągu, natomiast funkcja tail zwraca wszystko, poza pierwszym elementem ciągu.

head :: [a] -> a
head (x : xs) = x
tail :: [a] -> [a]
tail (x : xs) = xs


Funkcje te, w przeciwieństwie do length, nie są zdefiniowane dla wszystkich możliwych argumentów. Gdy spróbujemy zastosować je dla pustego ciągu, pojawi się błąd czasu wykonania.

Gdy mamy do czynienia z typami wielokrotnymi, okazuje się że niektóre z nich są bardziej ogólne od innych w tym sensie, że definiowany przez nie zbiór możliwych do obrania wartości jest większy. Np. typ [a] jest bardziej ogólny od [Char]. Gdyż ten drugi może być wyprowadzony z pierwszego poprzez odpowiednie podstawienie typu wielokrotnego a. Odnośnie tego, system typowania Haskell'a posiada dwie ważne właściwości: Po pierwsze gwarancja, że każde poprawne wyrażenie posiada swój typ (wzorzec) nominalny (ang. principial type) (opisany poniżej), zaś po drugie, typ nominalny może być wywnioskowany automatycznie (§4.1.3). W porównaniu do języków typowanych jednoznacznie (ang. monomorphically typed) takich jak C, czytelnik przekona się, że wielopostaciowość zwiększa czytelność, natomiast automatyczne wnioskowanie typu zdejmuje z programisty ciężar typowania.

Nominalny typ (wzorzec) wyrażenia, lub funkcji, jest najmniejszym typem, który zawiera wszystkie możliwe przypadki wyrażenia. Np. nominalnym wzorcem funkcji head jest [a] -> a . Przeciwnie, [b] -> a, a -> a, czy nawet a, są poprawne, lecz zbyt szerokie, natomiast określenie w stylu [Integer] -> [Integer] jest zbyt wąskie. Pojęcie nominalnego typu jest istotą systemu typowania Hindley-Milner'a (ang. Hindley-Milner type system), który leży u podstaw systemu typowania Haskell'a, ML, Miranda i kilku innych (w większości funkcyjnych) języków.


Definiowanie typów


W Haskell'u możemy definiować własne typy używając słowa kluczowego data (§4.2.1), użycie którego prześledzimy w następujących przykładach.

Niezwykle ważnym, przedefiniowanym typem Haskell'a jest ten, który dotyczy wartości logicznych:
data Bool = False | True


(wyrażenie "a | b" oznacza wybór pomiędzy a lub b, sam znak '|' należy czytać jako "albo"  - przyp. tłum.). Typ Bool, zdefiniowany powyżej, może przyjmować dokładnie dwie wartości: True albo False. Jest on przykładem sygnalnego (ang. nullary) konstruktora typu (ang. type constructor), natomiast True i False są przykładami (również sygnalnych) konstruktorów danych (ang. data constructor) (skrótowo zwanych konstruktorami).

Podobnie możemy zdefiniować typ opisujący barwę:
data Color = Red | Green | Blue | Indigo | Voilet


Obydwa typy Bool i Color są przykładami typów wyliczeniowych (ang. enumerated types), gdyż składają one się, ze skończonej liczby wyliczonych sygnalnych konstruktorów danych.

W następnym przykładzie definicji, użyjemy tylko jednego konstruktora danych:
data Point a = Pt a a


Z powodu pojedynczego konstruktora, typ taki jak Point jest często nazywany typem pokrywającym (ang. tuple type), gdyż jest on w istocie produktem kartezjańskim (w tym przypadku binarnym) innych typów. Natomiast typy takie jak Bool lub Color są nazywane typami sumarycznymi (ang. sum types).

Typ Point, co ważniejsze, jest przykładem typu wielopostaciowego: dla każdego typu t, definiuje on zbiór punktów których współrzędne są typu t. W związku z tym, że na bazie jednego typu t konstruuje on nowy typ Point t, nazywamy go jednostkowym konstruktorem typu (ang. unary type constructor). (w przypadku ciągów, analogicznie, [ ] jest również konstruktorem typu - wychodząc z dowolnego typu t, możemy posłużyć się [ ] aby stworzyć nowy typ [ t ]. Składnia Haskell'a umożliwia stosowanie uproszczonego zapisu [ t ] zamiast [ ] t. Podobnie -> jest konstruktorem typu: na bazie dwóch typów t i u możemy stworzyć t -> u będący wzorcem funkcji odwzorowującej zmienne typu t w wartości typu u.)

Warto odnotować, że binarny konstruktor danych Pt ma typ a -> a -> Point a więc poniższe typowania są poprawne:

Pt   2.0    3.0 :: Point Float
Pt    'a'    'b' :: Point Char
Pt True False :: Point Bool


Natomiast nie jest poprawne wyrażenie takie jak Pt 'a' 1, ponieważ 'a' i 1 należą do dwóch różnych typów.

Absolutnie kluczowe znaczenie ma, aby odróżniać stosowanie konstruktora danych w celu uzyskania wartości, od stosowania konstruktora typu którego wynikiem jest nowy typ. Pierwsza z tych czynności, ma miejsce w czasie wykonania i jest sposobem w jaki prowadzimy w Haskell'u obliczenia, natomiast druga z wymienionych czynności ma miejsce w czasie kompilacji i jest częścią przeprowadzanego przez system typowania procesu sprawdzania poprawności typów.

[Nazwy konstruktorów typu takie jak Point, a nazwy konstruktorów danych takie jak Pt istnieją w oddzielnych przestrzeniach nazw. Dzięki temu możliwe jest posługiwanie się jedną nazwą na oznaczenie konstruktora typu jak i konstruktora danych, np.
data Point a = Point a a


Mimo iż w pierwszej chwili wygląda to dość dziwnie (sugeruje bledną rekurencję - przyp. tłum.), konstrukcje takie służą podkreśleniu związku pomiędzy konstruktorem typu i odpowiadającym mu konstruktorem danych.]

Typy rekurencyjne


Deklaracje typów mogą być rekurencyjne, jak w poniższym przykładzie drzewa binarnego: (drzewo binarne to takie, które na każdym węźle może mieć co najwyżej dwie gałęzie - przyp. tłum.)

data Tree a = Leaf a | Branch (Tree a) (Tree a) 


(ang.leaf liść; branch gałąź). Jest to wielopostaciowa definicja drzewa binarnego, którego elementy są albo liśćmi przechowującymi wartość typu a, albo gałęziami składającymi się z dwóch (rekurencja) pod-drzew.

Kiedy czytamy deklaracje takie, jak powyższa, musimy pamiętać o tym że Tree jest konstruktorem typu, natomiast Leaf i Branch są konstruktorami danych. Poza określeniem zależności pomiędzy tymi konstruktorami, powyższa deklaracja nade wszystko automatycznie definiuje przynależność Leaf i Branch do następujących typów:

Leaf :: a -> Tree a
Branch :: Tree a -> Tree a -> Tree a


Zdefiniowany przez nas typ jest na tyle bogaty, że bazując na nim możemy utworzyć kilka interesujących (rekurencyjnych) funkcji. Np. powiedzmy, że chcemy zdefiniować funkcję fringe, zwracającą listę wszystkich elementów zawartych w kolejnych liściach, poczynając od lewej strony. Częstokroć pożyteczne jest wpierw określenie wzorca nowej funkcji. W tym przypadku narzucającym się wzorcem jest Tree a -> [a], z czego wynika, że funkcja fringe jest wielopostaciowa i dla dowolnego typu a, odwzorowuje drzewo elementów o typie a w ciąg elementów tegoż typu. Pełna definicja wygląda następująco:

fringe :: Tree a -> [a]<BR>
fringe (Leaf x) = [x]<BR>
fringe (Branch left right)         = fringe left ++ fringe right


Użyty powyżej symbol '++' jest infiksowym operatorem konkatenacji (łączenia) dwóch ciągów (jego pełną definicję podamy w rozdziale 9.1). Definicję tej funkcji, podobnie do wcześniejszej funkcji length, oparliśmy na mechanizmie dopasowywania szablonu, przy czym tym razem szablony wywodzą się od zdefiniowanych przez użytkownika konstruktorów: Leaf i Branch. [Formalne parametry łatwo odróżnić po tym, że są pisane z małej litery.]

Synonimy typów


Dla wygody, Haskell umożliwia definiowanie synonimów dla istniejących typów (ang. type synonyms), to jest nowych nazw dla powszechnie używanych typów. Tworzenie synonimów ma miejsce poprzez użycie słowa kluczowego type (§4.2.2). Przykładowo:

type String = [Char]
type Name = String
type Address = None | Addr String
type Person = (Name, Address)


Synonimy nie definiują nowych typów, tylko zwyczajnie udostępniają nowe nazwy dla istniejących typów. Np. wzorzec Person -> Name jest dokładnym odpowiednikiem (String, Address) -> String. Najczęściej nowe nazwy są krótsze, a co ważniejsze, obecność synonimów może zwiększać czytelność kodu. Możemy również tworzyć synonimy typów wielopostaciowych:

type AssocList a b = [ (a, b) ]


Jest to typ "ciągu asocjacyjnego" który łączy wartości typu a z wartościami typu b (inaczej mówiąc, jest to ciąg którego elementy są parami. - przyp. tłum.)

Wbudowane typy nie są wyjątkowe


Do tej pory pokazaliśmy kilka wbudowanych typów, takich jak ciągi, typy pokrywające, liczby całkowite i litery. Pokazaliśmy również sposób definiowania nowych. Pytanie brzmi - czy, poza odrębną składnią, typy wbudowane są w jakikolwiek sposób wyjątkowe? Odpowiedź brzmi nie. Odrębny sposób zapisu jest wprowadzony dla wygody i utrzymania historycznej zgodności, lecz nie ma on semantycznych konsekwencji.

Aby to uwypuklić, możemy zastanowić się, jakby wyglądały deklaracje tych wbudowanych typów, jeśli w definicjach moglibyśmy używać ich odrębnego zapisu. Na przykład, definicja typu Char mogłaby wyglądać następująco:

type Char = 'a' | 'b' | 'c' | ...
| 'A' | 'B' | 'C' | ... -- To nie jest poprawny
| '1' | '2' | '3' | ... -- kod Haskell'a!
... 


Nazwy użytych przez nas konstruktorów, takie jak 'a', nie są poprawne składniowo, moglibyśmy to poprawić w następujący sposób:

type Char = Ca | Cb | Cc | ...
         | CA | CB | CC | ...
         | C1 | C2 | C3 | ...
         ... 


Pomimo tego, że takie konstruktory jak Ca są dość zwięzłe, to stanowią one raczej niekonwencjonalny sposób reprezentacji liter.

Rozpisanie takiego pseudo-kodu, pomaga przejrzeć przez odrębną składnię. Teraz widzimy, że typ Char jest zwyczajnie typem wyliczeniowym, składającym się z dużej liczby sygnalnych konstruktorów. Z tego wynika, że w definicjach funkcji możemy stosować mechanizm dopasowywania szablonu względem liter, dokładnie tak, jak byśmy postępowali z dowolnym konstruktorem typu.

[Ten przykład demonstruje sposób wstawiania komentarzy do kodu; wszystko co następuje po znakach -- do końca wiersza jest ignorowane. Ponadto Haskell udostępnia komentarze zagnieżdżone, które mają postać {=...=} i mogą wystąpić w dowolnym miejscu (§2.2).]

Podobnie możemy zdefiniować typy liczb całkowitych  Int i Integer:

data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532       -- pseudo-kod
data Integer =         ... | -2 | -1 | 0 | 1 | 2 | ... 


Liczby -65532 i 65532 są najmniejszą i największą liczbą całkowitą w danej implementacji. Typ wyliczeniowy Int jest znacznie liczniejszy od typu Char, niemniej nadal jest skończony w przeciwieństwie do pseudo-kodu Integer, którego stanowi nieskończone wyliczenie.

Łatwo przychodzi też definiowanie typów pokrywających:

data (a, b) = (a, b)                       -- pseudo kod
data (a, b, c) = (a, b, c)
data (a, b, c, d) = (a, b, c, d)
          .                   .
          .                   .
          .                   . 


Każda z powyższych deklaracji definiuje typ pokrywający o określonej długości, gdzie znaki (...) odgrywają podwójną rolę konstruktora danych i konstruktora typu. Pionowe kropki następujące po ostatniej deklaracji odzwierciedlają fakt, że w Haskell'u typy pokrywające mogą być dowolnej długości.

Szczególnie ciekawa jest definicja ciągu, a to z powodu obecnej tu rekursji:

data [a] = [ ] | a : [a] 


W tej chwili czytelnie widać to, co już wcześniej powiedzieliśmy, mianowicie: [ ] jest ciągiem pustym, a ":" jest infiksowym konstruktorem ciągu (prawo skojarzeniowym), więc [1, 2, 3] jest odpowiednikiem ciągu 1: 2: 3: [ ]. Ponadto, typem [ ] jest [a], a typem ":" jest a -> [a] -> [a].

[Tą drogą zdefiniowany powyżej ":" jest składniowo poprawny - infiksowe konstruktory są dopuszczalne w deklaracjach z użyciem słowa kluczowego data, i są one odróżniane od infiksowych operatorów (dla celów dopasowywania szablonu), co więcej, ich nazwy muszą rozpoczynać się od znaku ":" (w trywialny sposób konstruktor ":" spełnia ten wymóg)]

W tym miejscu czytelnik powinien być w stanie dostrzec, unaocznioną przez powyższe definicje, różnicę pomiędzy ciągiem a typem pokrywającym. W szczególności warto zaznaczyć rekurencyjną naturę ciągu, którego elementy są jednolitego typu w odróżnieniu od nie-rekurencyjnej natury typu pokrywającego, którego długość (w konkretnym przypadku) jest stała a elementy mogą należeć do różnych typów.

dla (e1,e2,...,en), nł2, jeśli ei należy do typu ti, to pokrycie należy do typu (t1,t2,...,tn).

dla [ e1,e2,...,en], nł2, każdy ei musi należeć do tego samego typu t, a ciąg należy do typu [t].

Fabrykatory i ciągi arytmetyczne


Obok omówionych przed chwila konstruktorów ciągów, Haskell udostępnia wyrażenie zwane fabrykatorem ciągu (ang. list comprehension), które omówimy na przykładzie:

 [ f x | x <- xs ] 

(w tym kontekście symbol "|" należy odczytywać jako "takich że" - przyp. tłum.). Całe powyższe wyrażenie możemy odczytać jako "ciąg wszystkich f x, takich, że x należy do xs". Zbieżność do notacji zbioru nie jest przypadkowa. Fraza x <- xs jest zwana generatorem (ang. generator), przy czym można użyć kilku generatorów, tak jak poniżej:

[ (x, y) | x <- xs, y <-ys ]


Ten fabrykator ciągu, należy odczytywać jako zbiór par (x, y), takich że x należy do xs natomiast y należy do ys, czyli jest to produkt kartezjański dwóch ciągów xs i ys. Elementy są wybierane tak jakby generatory były zagnieżdżone od lewej do prawej (gdzie generator najbardziej oddalony na prawo zmienia się najszybciej); więc jeśli xs to [1, 2] a ys to [3, 4], wynikiem będzie [(1, 3), (1, 4), (2, 3), (2, 4)].

Obok generatorów można umieszczać logiczne wyrażenia zwane strażnikami (ang. guards). Strażnicy narzucają ograniczenia na wygenerowane obiekty. Jako przykład podajemy zwięzłą definicję ulubionego przez wszystkich algorytmu sortowania:

quicksort [ ] = [ ]
quicksort (x : xs) = quicksort [ y | y <- xs, y<x ]
                                     ++ [x]
                                     ++ quicksort [ y | y <- xs, y>=x ] 


Aby ułatwić korzystanie z ciągów, Haskell udostępnia specjalną składnię dla ciągów arytmetycznych (ang. arithmetic sequences), co najłatwiej pokazać na przykładach:

 [1..10] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1,3..10] => [1, 3, 5, 7, 9]
[1,3..] => [1, 3, 5, 7, 9, ... (nieskończony ciąg) 


Do tematu ciągów arytmetycznych powrócimy jeszcze w rozdziale 8.2 oraz przy okazji ciągów nieskończonych w rozdziale 3.4

Napisy


Kolejnym udogodnieniem w korzystaniu z typów wbudowanych, jest korzystanie z literałów. Napis "hello" jest w istocie skrótową postacią ciągu liter ['h', 'e', 'l', 'l', 'o']. Faktycznie "hello" należy do typu String, gdzie String jest przedefiniowanym synonimem:
type String = [Char]


To oznacza, że w odniesieniu do literałów możemy posługiwać się polimorficznymi funkcjami, przykładowo:
"hello" ++ " world" => "hello world"

4 komentarze

Ktos 2007-01-06 12:22

Sformatowałem to zgodnie z nowym Coyote, poprawcie jeśli gdzieś się machnąłem, albo niekonsekwentny byłem.

Dryobates 2003-01-01 18:04

Więcej, więcej !!
Czekam na resztę tłumacznia i przykłady.

LKS 2002-12-30 14:04

Nareszcie po długich bojach (ponad 2-godzinnych) udało mi się doprowadzić artykuł do jako takiego wyglądu. Jeżeli podczas czytania znajdziecie jakiś błąd to dajcie znać - postaram się go poprawić.

ps. Wiem, że w Operze są źle wyświetlane znaki z czcionki Symbol np. <font face=Symbol>Ţ</font> :)

lofix 2002-12-30 01:17

ale ty masz sesje z tym człowieku :P