Haskell/Wersja do druku

Ania

Haskell

Aktualna, edytowalna wersja tego podręcznika jest dostępna w Wikibooks, bibliotece wolnych podręczników pod adresem
https://pl.wikibooks.org/wiki/Haskell

Całość tekstu jest objęta licencją CC-BY-SA 3.0.

Udziela się zezwolenia do kopiowania, rozpowszechniania lub modyfikacji tego dokumentu zgodnie z zasadami Licencji Creative Commons Uznanie autorstwa-Na tych samych warunkach 3.0 Unported lub dowolnej późniejszej wersji licencji opublikowanej przez Creative Commons, która zawiera te same elementy co niniejsza licencja. Treść licencji dostępna jest pod adresem http://creativecommons.org/licenses/by-sa/3.0/legalcode.

Spis treści

1. Wprowadzenie
2. Witaj inny świecie!
3. Zmienne i funkcje
4. Typy danych
5. Listy i krotki
6. Funkcje rekurencyjne
7. Więcej na temat funkcji
8. Operatory
9. Dopasowanie wzorców i instrukcje warunkowe
10. Funkcje działające na listach
11. Typy definiowane przez użytkownika

Wprowadzenie

Haskell : Język programowania funkcyjnego

Haskell jest nowoczesnym językiem funkcyjnym ogólnego przeznaczenia stworzonym po to, aby połączyć wszystkie atuty programowania funkcyjnego w jednym eleganckim, silnym i ogólnie dostępnym języku programowania.

Czystość

Haskell, w przeciwieństwie do niektórych języków funkcyjnych, jest językiem czysto funkcyjnym. Najważniejszą cechą tego języka jest to, iż nie pozwala na żadne efekty uboczne.

Leniwe wartościowanie

Inną ważną cechą języka Haskell jest to, iż jest to język „leniwy” („not-strict”). Oznacza to, że wartość żadnego wyrażenia nie jest wyznaczana dopóki nie jest potrzebna. Można, na przykład, zdefiniować nieskończenie długą listę liczb pierwszych tworzoną w niekończącej się rekurencji. Wyznaczone zostaną tylko te elementy listy, które są aktualnie potrzebne. Pozwala to na wiele bardzo eleganckich rozwiązań wielu problemów. Przykładem może być zdefiniowanie listy możliwych rozwiązań oraz przefiltrowanie jej, usuwając rozwiązania niedopuszczalne. Pozostała lista będzie więc zawierała rozwiązania dopuszczalne. Leniwe wartościowanie czyni tę operację bardzo przejrzystą. Jeśli potrzebujemy tylko pierwsze rozwiązanie możemy odczytać pierwszy element z listy – leniwe wartościowanie zagwarantuje nam, że nic nie zostanie policzone niepotrzebnie.

Silne typowanie

Haskell jest językiem stosującym silne typowanie. Oznacza to, że niemożliwa jest na przykład przypadkowa konwersja Double do Int. Prowadzi to do zmniejszenia liczby powstałych błędów. Czasami może to być nieco kłopotliwe, ale nie zdarza się to na tyle często, żeby można było uznać to za poważną niedogodność. W praktyce często pomaga to w zlokalizowaniu błędów w kodzie. W językach, które pozwalają na taką niejawną konwersję, często pojawiają się problemy, kiedy kompilator potraktuje Double jako Int, wskutek czego na przykład wynikiem dzielenia 1/2 jest liczba 0.

W przeciwieństwie do wielu języków stosujących silne typowanie, typy w Haskellu są automatycznie rozpoznawane. Oznacza to, że bardzo rzadko konieczne jest deklarowanie typu funkcji. Często takie definicje służą jedynie dokumentacji kodu. Haskell stara się wywnioskować typ z kontekstu w jakim zmienna została użyta. Następnie sprawdzana jest zgodność typów we wszystkich operacjach, aby wykluczyć niedopasowania typów.

Język Python stosuje zasadę "duck typing"; oznacza to „jeśli chodzi i mówi jak kaczka, oznacza to, że jest kaczką”. Haskell posiada nieco inny mechanizm. Jeśli jakaś wartość „chodzi i mówi jak kaczka”, wtedy zostanie potraktowana jak kaczka, ale jeśli później zacznie się zachowywać jak małpa, już podczas kompilacji zostanie zgłoszony błąd.

Haskell i błędy

Programy napisane w Haskellu zawierają mniej błędów, ponieważ Haskell:

• jest językiem czystym – nie ma efektów ubocznych – za każdym razem, gdy wywołamy funkcję z takimi samymi parametrami, zwróci ona taką samą wartość;
• stosuje silne typowanie – nie ma niejawnych przekształceń typów;
• jest zwięzły – programy są krótsze, dzięki czemu łatwiej jest analizować poszczególne funkcje i lokalizować błędy;
• jest językiem wysokiego poziomu – programy napisane w Haskellu często są bardzo podobne do opisu algorytmu. Pisząc funkcje na wyższym poziomie abstrakcji, zostawiając szczegóły kompilatorowi, zmniejszamy szanse pojawienia się błędów;
• zarządza pamięcią – programista nie musi się martwić o zwisające wskaźniki, odśmiecanie itp. – kompilator wykonuje to za niego; programista zajmuje się jedynie implementacją algorytmu, a nie zarządzaniem pamięcią;
• jest modularny – Haskell oferuje bardzo wiele metod łączenia modułów. Jeśli dwie proste funkcje działają poprawnie i połączymy je w odpowiedni sposób w bardziej rozbudowaną funkcję, mamy pewność, że nowo powstała funkcja również działa poprawnie;

Haskell vs OOP (Programowanie obiektowe)

Język Haskell, podobnie jak języki obiektowe, umożliwia tworzenie abstrakcyjnych struktur danych, polimorfizm i enkapsulację.

Enkapsulacja danych jest realizowana poprzez umieszczenie każdego typu danych w osobnym module, z którego eksportowany jest tylko interfejs i tylko ten interfejs jest widziany na zewnątrz modułu. Dzięki temu, że tylko funkcje będące częścią interfejsu mogą być użyte „na zewnątrz” – szczegóły implementacji mogą zostać ukryte wewnątrz modułu. W Haskellu typ danych oraz funkcje działające na tych danych nie są zgrupowane wewnątrz „obiektu”, ale wewnątrz modułu.

Polimorfizm jest realizowany poprzez zastosowanie tzw. klas typów. Klasy typów są w Haskellu dokładnie tym, czego można się spodziewać po ich nazwie. Są zbiorem zasad, które musi spełnić typ danych, aby mógł być traktowany jako instancja tej klasy. Można zdefiniować typ „Pies” będący instancją klasy typów „Zwierzę”. Wszystkie funkcje, które mogą zostać zastosowane w stosunku do zmiennej typu „Zwierze”, równie dobrze mogą zostać zastosowane do zmiennej typu „Pies”.

Haskell umożliwia więc polimorfizm oraz enkapsulację. Nie pozwala jednak na grupowanie danych i funkcji na nich działających w pojedynczy obiekt. Należy również pamiętać, że funkcje mogą być częścią typu danych - funkcje w Haskellu są przecież danymi tak samo jak zmienne typu Int czy String!

Szybkość języka Haskell

Program napisany w języku Haskell i skompilowany przy użyciu GHC wykonuje się z prędkością porównywalną do C czy C++. Różnice w szybkości są jednak tak małe, że prawie bez znaczenia. Oczywiście nie dotyczy to aplikacji takich jak np. kodery MPEG, czy inne aplikacje wykonujące złożone obliczenia, które większość czasu wykonania spędzają na wykonywaniu małej części kodu. W takich przypadkach zdecydowanie lepszym rozwiązaniem jest zastosowanie języka C++.

Zgodnie z jedną z wersji zasady „80/20”, przeciętna aplikacja poświęca 80% czasu na wykonanie 20% kodu. Oznacza to, że duża część funkcji systemu jest tak mało istotna, że optymalizacja ich nie ma sensu. Może się okazać, że tylko kilka funkcji jest na tyle ważnych, że warto poświęcić czas na ich udoskonalanie. Te funkcje mogą zostać napisane np. w języku C/C++ oraz wykorzystane w Haskellu za pomocą odpowiedniego interfejsu. Czasami warto zrezygnować z szybkości działania aplikacji na rzecz produktywności, stabilności i łatwości utrzymania kodu. Czas pracy programisty jest przecież kosztowniejszy niż czas pracy procesora.

Należy również pamiętać, że optymalizacja algorytmu może dać lepsze rezultaty niż optymalizacja kodu. Jeśli aplikacja w Haskellu zostanie napisana w znacznie krótszym czasie niż w języku C++, pozostanie więcej czasu na pracę nad poprawą samego algorytmu.

Dlaczego Haskell nie jest popularny?

Większość osób zaczyna programowanie od jednego z języków imperatywnych. Przejście z jednego języka imperatywnego do innego nie stanowi większego problemu. Programowanie w języku funkcyjnym, a tym bardziej czysto funkcyjnym takim jak Haskell, wymaga całkowitej zmiany sposobu myślenia o problemie. W Haskellu nie ma pętli, zmienne nie zmieniają swoich wartości… są funkcje, wszechobecna rekurencja i dodatkowe ograniczenia. Z tego powodu wiele osób rezygnuje z języków funkcyjnych już na początku nauki, zanim jeszcze poznają ich możliwości.

Witaj inny świecie!

Programy

Implementacje

Kod napisany w języku Haskell może być wykonywany w trybie wsadowym (kompilowanie) lub interaktywnym (interpretowanie). Tryb interaktywny jest doskonałym rozwiązaniem do eksperymentowania i nauki. Istnieją trzy najpopularniejsze implementacje języka Haskell:

• Hugs - bardzo szybki interpreter, nie pozwala na utworzenie samodzielnych programów oraz na definiowanie funkcji w środowisku (tylko w plikach). Dostępny dla większości systemów operacyjnych.
• GHC - Pozwala na interpretacje programów (wolniej niż Hugs) oraz kompilację (bardzo szybki kod wynikowy). Umożliwia definiowanie funkcji w środowisku. Dobre wsparcie dla stosowania funkcji z innych języków.
• NHC - rzadko stosowany. Umożliwia jedynie kompilowanie programów. Tworzy małe i szybkie pliki wykonywalne.

W dalszej części stosowany będzie GHC - Glasgow Haskell Compiler, dostępny pod adresem http://haskell.org/ghc. Interpreter uruchamiamy poleceniem ghci lub ghc interactive. Po uruchomieniu na ekranie pojawia się ekran powitalny, oraz linia poleceń (Prelude>). Aby zakończyć działanie ghci w lini poleceń wpisujemy :quit.

Dodatkowe programy

• narzędzia do tworzenie projektów
  • Cabal
  • stack
  • Halcyon
• programy do tworzenia dokumentacji kodu
  • Haddock

Start i zakończenie

GHCI

Uruchamiamy GHC w trybie interaktywnym : linii poleceń wpisujemy :

ghci

Otrzymujemy :

GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude>

Wyjście z GHCI :

Prelude> :quit
Leaving GHCi

albo za pomocą skrótu klawiszowego control-D.

GHC

Sprawdzamy jaką wersję kompilatora mamy

ghc --info
[("Project name","The Glorious Glasgow Haskell Compilation System")
,("Project version","6.12.1")
,("Booter version","6.12.1")
,("Stage","2")
,("Have interpreter","YES")
,("Object splitting","YES")
,("Have native code generator","YES")
,("Support SMP","YES")
,("Unregisterised","NO")
,("Tables next to code","YES")
,("Win32 DLLs","")
,("RTS ways","l debug  thr thr_debug thr_l thr_p  dyn debug_dyn thr_dyn thr_debug_dyn")
,("Leading underscore","NO")
,("Debug on","False")
,("LibDir","/usr/lib/ghc-6.12.1")
]

cabal

cabal oznacza:

• program konsolowy do obsługi programów i bibliotek napisanych w języku Haskell = cabal-install ( aka Cabal-the-tool)
• formatem plików zawierających informacje o projekcie/programie, np. my-project.cabal ( aka Cabal-the-spec )
• bibliotekę ( framework) implementującą ww specyfikację ( aka Cabal-the-library )

stack

Możemy korzystać z Haskella w Bashu za pośrednictwem stacka

Przykład:

  stack new hello-haskell
  cd hello-haskell
  stack setup
  stack build
  stack exec hello-haskell

Stacka wykorzystuje pliki:

• stack.yaml
• *.cabal

Witaj świecie!

Naukę nowego języka programowania najczęściej zaczyna się od programu wypisującego na ekranie powitanie „Witaj świecie!”. W Haskellu można to zrobić na kilka sposobów: Wpisując bezpośrednio w linii poleceń łańcuch znaków ograniczony cudzysłowami

 Prelude> "Witaj swiecie"
 "Witaj swiecie"

Interpreter „obliczy” wartość podanego wyrażenia – łańcucha znaków – i wypisze ją. Innym sposobem jest wypisanie łańcucha znaków bezpośrednio na standardowe wyjście:

Prelude> putStrLn "Witaj swiecie"
Witaj swiecie

Używając GHC można skompilować kod do pliku wykonywalnego poleceniem: $ ghc -o witaj witaj.hs oraz uruchomić

$ ./witaj
"Witaj swiecie"

Komentarze

Podobnie jak większość języków programowania Haskell umożliwia umieszczanie wewnątrz kodu komentarzy, które są ignorowane przez kompilator (lub interpreter). Komentarz może się składać z jednej linii tekstu:

-- komentarz w jednej linii

lub z większego fragmentu tekstu

{- 
dłuższy komentarz
składający się
z kilku linii
-}

Obliczanie silni

Poprzedni program nie jest jednak najlepszym programem do rozpoczęcia nauki języka funkcyjnego. Kolejny przykład będzie już bardziej typowy dla tej grupy języków. Będzie to funkcja wyznaczająca wartość silni. Jedno z możliwych rozwiązań wygląda następująco:

Prelude> let silnia n = if n == 0 then 1 else n * silnia (n-1)

Za pomocą słowa let zdefiniowana została funkcja silnia przyjmująca jeden parametr n. Następnie wykorzystana została instrukcja warunkowa:

if warunek then wartość1 else wartość2

która w zależności od tego czy warunek został spełniony zwróci wartość1 lub wartość2. Funkcję silnia można zdefiniować w osobnym pliku i załadować do GHCi. W tym celu należy utworzyć plik silnia.hs. W pliku tym można umieścić taką definicją funkcji jaka została przedstawiona powyżej, ale bez słowa let, które jest poleceniem interpretera, a nie elementem języka. Można nieco zmienić tę definicję, dzięki czemu będzie wyglądała bardziej elegancko:

silnia::Int -> Int
silnia 0 = 1
silnia n = n * silnia (n-1)

Pierwsza linia nie jest obowiązkowa, określa ona typ wartości przyjmowanej i zwracanej przez funkcję silnia. Chociaż określenie typów nie jest wymagane, warto je stosować jako dokumentację kodu. Określanie typów często pomaga w lokalizowaniu błędów. Nazwy typów w Haskellu zaczynają się od wielkiej litery. Funkcje zdefiniowane w pliku silnia.hs można załadować do interpretera za pomocą polecenia :load (lub krócej :l) i używać w następujący sposób:

Prelude> :load silnia.hs
[1 of 1] Compiling Main			( silnia.hs, interpreter )
Ok., module loaded: Main.
*Main> silnia 4
24

Dopisanie na końcu pliku silnia.hs jeszcze jednej linii

main = print (silnia 4)

pozwoli na skompilowanie tego pliku i utworzenie pliku wykonywalnego

$ ghc -o silnia silnia.hs
$ ./silnia
24

Funkcja print odpowiada za konwersję wartości Int do wartości String

Zmienne i funkcje

Stałe

Interpreter GHCi pozwala na wykonywanie operacji arytmetycznych poprzez bezpośrednie wpisanie ich w linii poleceń interpretera. Na przykład można obliczyć pole koła o promieniu 5 w następujący sposób:

Prelude> 3.14159265358979323846264338327950 * 5 * 5
78.53981633974483

Jeśli następnie chcielibyśmy obliczyć obwód tego koła, konieczne było by ponowne wpisanie wartości liczby pi. GHCi pozwala na definiowanie stałych za pomocą słowa kluczowego let. Po jednokrotnym zdefiniowaniu wartości pi można używać jej w dalszych obliczeniach. Nazwy stałych (oraz funkcji) muszą rozpoczynać się od małej litery.

Prelude> let pi = 3.14159265358979323846264338327950
Prelude> pi
3.141592653589793

Liczby są „obcinane” do 16 cyfr jedynie podczas wyświetlania.

Prelude> pi * 5 * 5
78.53981633974483

Jeśli chcielibyśmy również promień zastąpić stałą r możemy napotkać pewien problem.

 Prelude> let r = 5
 Prelude> pi*r*r
 <interactive>:1:5:
    Couldn't match expected type `Double' 
	against `Integer'
      Expected type: Double
      Inferred type: Integer
    In the second argument of `(*)', namely `r'
    In the first argument of `(*)', namely `r', namely `pi * r'

Problem ten spowodowany jest ścisłą kontrolą zgodności typów, a dokładniej tym, że Haskell nie pozwala na pomnożenie liczby typu Double przez liczbę typu Integer. Rozwiązaniem tego problemu może być zdefiniowanie stałej r jako liczby rzeczywistej:

Prelude> let r = 5.0

Stałe nie muszą być definiowane bezpośrednio jako liczby. Mogą być zdefiniowane na przykład jako wyrażenie arytmetyczne:

Prelude> let poleKola = pi * r * r
Prelude> poleKola
78.53981633974483

Należy jednak pamiętać, że wartość stałej jest niezmienna (tym się różni od występujących w innych językach tzw. zmiennych). Niemożliwe jest więc obliczenie pola koła o promieniu 2 w następujący sposób:

Prelude> let r = 2.0
Prelude> poleKola
78.53981633974483

Funkcje

Wygodnym rozwiązaniem tego problemu jest zdefiniowanie funkcji przyjmującej jako parametr długość promienia koła.

Prelude> let poleKola r = pi * r * r
Prelude> poleKola 5
78.53981633974483
Prelude> poleKola 1
3.141592653589793

Stała r wewnątrz funkcji poleKola jest stałą lokalną. Wartość stałej globalnej o tej samej nazwie nie ma żadnego wpływu na działanie funkcji.

Warto zauważyć, że tym razem możliwe jest obliczenie pola koła o promieniu 5 (nie musi to być 5.0). Typ wartości liczbowej jest ustalany na podstawie kontekstu w jakim występuje. Podczas definicji stałej r nie było możliwe wywnioskowanie, że ma to być liczba rzeczywista. Podczas wywołania funkcji poleKola z parametrem jest to możliwe. Parametr przekazany do funkcji jest mnożony przez liczbę rzeczywistą (pi), więc powinien być liczbą tego samego typu. Dzięki temu Haskell traktuje liczbę 5 jako Double.

Oczywiście możliwe jest zdefiniowanie funkcji przyjmującej więcej niż jeden parametr, na przykład obliczającej pole prostokąta:

Prelude> let poleProstokata a b = a * b 
Prelude> poleProstokata 2 4
8

Można również zdefiniować funkcję, która do wyznaczenia wartości wykorzysta inne funkcje. Na przykład funkcja licząca objętość prostopadłościanu

Prelude> let objProstopadloscianu a b h = poleProstokata a b * h
Prelude> objProstopadloscianu 1 2 3
6

Funkcje liczące pola graniastosłupów

Powyżej zostały zdefiniowane funkcje obliczające pole koła i prostokąta. Na ich podstawie w prosty sposób można zdefiniować funkcje wyznaczające objętość różnych graniastosłupów. Objętość dowolnego graniastosłupa obliczamy mnożąc pole podstawy razy wysokość. Na początek napiszmy więc taką funkcję:

Prelude>let objGran polePodst h = polePodst * h

Teraz możemy już zdefiniować funkcje liczącą objętość prostopadłościanu, walca lub sześcianu:

Prelude> let objProstopadloscianu a b h = objGran (poleProstokata a b) h
Prelude> let objWalca r h = objGran (poleKola r) h
Prelude> let objSzescianu a = objGran (poleProstokata a a) a

Typy danych

Typy danych w Haskellu

Typ jest zbiorem pewnych wartości. Na przykład typ Bool składa się z wartości True i False. Każda wartość (jak również funkcja) w Haskellu ma ściśle określony typ. Jawne definiowanie typów nie jest konieczne, ponieważ Haskell sam rozpoznaje typ wartości. Warto jednak jawnie określać typ wyrażenia, ponieważ bardzo ułatwia to analizę i dokumentację kodu oraz usuwanie błędów.

Najprostszym sposobem na poznanie typów jest użycie polecenia interpretera, dzięki któremu możemy sprawdzić typ dowolnego wyrażenia. Poleceniem tym jest :type, lub krócej :t.

Prelude> :t "Witaj inny swiecie!"
"Witaj inny swiecie!" :: [Char]

Symbol :: może być odczytywany jako "jest typu". "Witaj inny swiecie!" jest więc listą znaków.

Stosując symbol :: możemy zapisać:

1 :: Integer 
1.5 :: Double
True :: Bool
'a' :: Char
"Witaj" :: String
"Witaj" :: [Char]

Dwie ostatnie linie przedstawiają ten sam łańcuch znaków. Na pierwszy rzut oka może się wydawać, że zostały zdefiniowane jako zmienne innych typów. Jest to jeden z przykładów wykorzystania mechanizmu synonimów typów dostępnego w Haskellu. String jest synonimem [Char] i oznacza tutaj dokładnie to samo co [Char]. Mechanizm synonimów typów zostanie omówiony w dalszej części rozdziału.

Rodzaje typów

• liczbowe ( class Num )
  • podstawowe ( ang. standard or primitive numeric types )
    • Int
    • Integer
    • Float
    • Double
  • pochodne ( ang. Constructed types)
    • complex
    • ratio
• algebraiczne (ang. Algebraic data type = ADT )

Podział wg implementacji:

• abstrakcyjne
  • polimorficzne
  • monomorficzne : Integer, Float
• konkretne ( ang. Concrete data type )

Typy podstawowe

Typy całkowite

W Haskellu dostępne są dwa typy całkowite:

• Int (fixed-precision) - liczby całkowite z zakresu [-2^29 .. 2^29-1],
• Integer (arbitrary-precision) - wartością Integer może być dowolna liczba całkowita (zarówno ujemna jak i dodatnia).

Typy rzeczywiste

Dostępne są dwa typy liczb rzeczywistych:

• Float - liczba zmiennoprzecinkowa pojedynczej precyzji,
• Double - liczba zmiennoprzecinkowa podwójnej precyzji.

Typ znakowy

Typ pojedynczego znaku to char. Jest to typ wyliczeniowy, którego wartości reprezentują znaki Unicode.

Bool - zmienne logiczne

Podobnie jak w innych językach, do reprezentowania zmiennych logicznych służy typ Bool. Jest to typ wyliczeniowy zawierający dwie wartości False (fałsz - 0) i True (prawda - 1).

Typ relacji między elementami

Ordering, typ relacji, w większości języków programowania nie jest obecny. Jest to typ wyliczeniowy posiadający trzy wartości:

• LT (less than - mniejszy niż)
• EQ (equal - równy)
• GT (greater than - większy niż)

Wartości tego typu są zwracane między innymi przez funkcję compare porównującą dwa elementy.

Prelude> compare 1 2
LT

Typy strukturalne

Typy strukturalne to listy i krotki. Listy to struktury homogeniczne, natomiast krotki heterogeniczne. Rozmiar listy nie jest określony - można dołączać do niej kolejne elementy. Rozmiar krotki jest ściśle określony podczas jej tworzenia. Nie jest możliwe dołączanie elementów do istniejącej krotki.

Przykład listy:

Prelude> :t ['a','b','c']
['a','b','c'] :: [Char]

i krotki:

Prelude> :t (True,"Haskell")
(True,"Haskell") :: (Bool,[Char])

Typy funkcji

Nie tylko zmienne, ale również funkcje mają w Haskellu swój typ. Na typ funkcji składają się typy przyjmowanych przez nią parametrów oraz typ wartości zwracanej przez funkcję. Typy te podajemy w następujący sposób:

nazwa_funkcji :: TypParam_1 -> TypParam_2 -> ... -> TypParam_n -> TypWartosciZwracanej

na przykład definicje funkcji inc zwiększającej wartość liczby Int o jeden, oraz funkcji add dodającej dwie liczby Double wyglądają następująco:

inc :: Int -> Int
add :: Double -> Double -> Double

Synonimy typów

Synonimy typów umożliwiają nadanie własnej nazwy dla dowolnego typu. Wykorzystanie synonimów typów jest możliwe tylko w zewnętrznym pliku.

Poniżej utworzony został typ przechowujący dwie współrzędne punktu (x,y) oraz funkcja obliczająca odległość między tymi punktami.

 type Punkt = (Double, Double)

 odleglosc :: Punkt -> Punkt -> Double
 odleglosc (x1,y1) (x2,y2) = sqrt ( (x1-x2)^2 + (y1-y2)^2 )

Przykładem zastosowania synonimów typów jest String, czyli synonim tablicy znaków [Char].

Typy polimorficzne

Typ polimorficzny oznacza rodzinę typów. Na przykład, [a] jest rodziną typów zawierającą listy dowolnych typów. Jeśli utworzymy listę zawierającą wartości dowolnego typu, lista ta będzie należała do rodziny [a]. Lista wartości Int (np. [1,2,3]), lista znaków (np. ['a','b','c']), jak również lista list (np. [[1,1],[1,2]]) czy lista krotek (np. [(1,'a'),(2,'b')]) należą do rodziny [a].

Identyfikatory takie jak zastosowana powyżej litera a są nazywane zmiennymi wartości i w przeciwieństwie do nazw typów, są pisane z małej litery.

Listy, bardzo często używane w programowaniu funkcyjnym, są doskonałym przykładem do zademonstrowania polimorfizmu. Aby wyznaczyć liczbę elementów w liście możemy zastosować funkcję length, na przykład:

Prelude> length [1,2,3]
3

Sprawdźmy teraz jaki jest typ tej funkcji:

Prelude> :t length 
length :: [a] -> Int

Jak widać funkcja ta przyjmuje listę dowolnego typu i zwraca liczbę całkowitą. Dzięki polimorfizmowi funkcja length może zostać zastosowana dla dowolnej tablicy ([Int], [Char], [ [Int] ] itp). Nie potrzeba definiować osobnych funkcji dla tablic różnych typów.

Inną funkcją polimorficzną jest funkcja head zwracająca pierwszy element listy.

Prelude> head [1,2,3]
1
Prelude> :t head
head :: [a] -> a

Jak widać funkcja head przyjmuje listę elementów dowolnego typu i zwraca element tego samego typu.

Zobacz również

Klasy typów w Haskellu

• Typy definiowane przez użytkownika
• klasy typów

Listy i krotki

Listy

Listy są obecne prawie w każdym programie napisanym w języku Haskell. Są to homogeniczne struktury danych. Lista pozwala na przechowywanie dowolnej liczby elementów tego samego typu. Listy są otoczone nawiasami kwadratowymi, a ich elementy oddzielone przecinkami.

Prelude> let imiona = [„Zosia”, „Kasia”, „Małgosia”]
Prelude> let liczby = [3,4,5]

Listy mogą być tworzone poprzez połączenie elementu i innej listy za pomocą dwukropka (cons operator)

Prelude> 2 : liczby
[2,3,4,5]
Prelude> 0 : 1 : 2 : liczby
[0,1,2,3,4,5]

Należy pamiętać, że operator (:) nie dołącza elementu do istniejącej listy, a tworzy nową listę na podstawie starej oraz dołączanego elementu. Nowy element może zostać dodany tylko na początku nowej listy.

Notacja umożliwiająca zapis listy za pomocą nawiasów kwadratowych i przecinków została stworzona jedynie dla wygody użytkowników (jest to tzw. lukier syntaktyczny, z ang. syntactic sugar). Zapis [3,4,5] jest równoznaczny z zapisem 3:4:5:[]. Dwa nawiasy kwadratowe oznaczają listę pustą. Każdą listę można zbudować w taki właśnie sposób – dołączając poszczególne elementy do listy pustej. Nie możliwe jest natomiast zastosowanie operatora (:) w następujący sposób:

 Prelude> True:False
 <interactive>:1:5:
    Couldn't match `[Bool]' against `Bool'
      Expected type: [Bool]
      Inferred type: Bool
    In the second argument of `(:)', namely `False'
    In the definition of `it': it = True : False

Nowa lista musi być tworzona na bazie innej, istniejącej już listy (może nią być lista pusta).

Język Haskell oferuje wiele funkcji operujących na listach. Dwie chyba najważniejsze z nich to head i tail, zwracające odpowiednio głowę (pierwszy element) i ogon listy (to co zostanie po usunięciu głowy).

Prelude> head [1,2,3,4]
1
Prelude> tail [1,2,3,4]
[2,3,4]

String – lista znaków

Wartość typu String jest w Haskellu po prostu listą złożoną z poszczególnych znaków (Char). Typ String jest w Haskellu synonimem [Char]. Stringi mogą być tworzone na trzy sposoby:

Prelude>”Haskell”
”Haskell”
Prelude>’H’:’a’:’s’:’k’:’e’:’l’:’l’:[]
”Haskell”
Prelude>[’H’,’a’,’s’,’k’,’e’,’l’,’l’]
”Haskell”

Wartości typu String znajdują się pomiędzy cudzysłowami, natomiast znaki (typu Char) pomiędzy apostrofami.

Sekwencje arytmetyczne

Aby ułatwić pracę z listami Haskell udostępnia możliwość prostego tworzenia list będących sekwencjami arytmetycznymi. Aby utworzyć taką listę należy podać dwa pierwsze elementy listy, a następnie po dwóch kropkach ostatni element listy. Sekwencja jest tworzona na podstawie różnicy pomiędzy dwoma pierwszymi elementami listy. Możliwe jest utworzenie zarówno sekwencji o rosnących, jak i malejących wartościach elementów.

Prelude>[1,2..10]
[1,2,3,4,5,6,7,8,9,10]
Prelude>[5,3..(-1)]
[5,3,1,-1]

Jeżeli ostatni element listy nie zostanie podany, Haskell utworzy listę o "nieskończonej" długości. Jest to możliwe dzięki leniwemu wartościowaniu. Wyznaczony zostanie tylko ten element listy, który będzie w danej chwili potrzebny.

Prelude>[1,2..]

Listy list, czyli tablice wielowymiarowe

Ponieważ lista składa się z elementów dowolnego typu, możliwe jest utworzenie listy, której elementami będą inne listy. Lista taka może być wykorzystywana jako tablica dwuwymiarowa.

Prelude> [[1,2,3],[2,3,4],[3,4,5]]
[[1,2,3],[2,3,4],[3,4,5]]

Powyżej została zdefiniowana tablica dwuwymiarowa o wielkości 3x3. Zdefiniowana w ten sposób tablica nie musi być tablicą prostokątną (lub tak jak w tym przypadku kwadratową). Dwie listy przechowujące elementy tego samego typu, nie zależnie od długości listy, są zmiennymi tego samego typu. Możliwe jest więc utworzenie tablicy, której wiersze będą różnej długości. Poniżej została utworzona tablica trójkątna górna.

Prelude> [[1,2,3],[3,4],[5]]
[[1,2,3],[3,4],[5]]

Podobnie jak w innych językach, możliwe jest tworzenie struktur danych odpowiadających tablicom wielowymiarowym (np. trójwymiarowym).

Prelude> [ [ [1,2],[3,4] ] , [ [5,6],[7,8] ] ]
[[[1,2],[3,4]],[[5,6],[7,8]]]

Krotki (Tuples)

Krotki to heterogeniczne struktury danych. Są wykorzystywane wtedy, kiedy wiadomo dokładnie ile elementów i jakiego typu chcemy przechować. Zmienne wewnątrz jednej krotki nie muszą (w przeciwieństwie do list) być tego samego typu. Krotkę zapisujemy podobnie jak listę, jednak zamiast nawiasów kwadratowych używamy nawiasów okrągłych.

Prelude> („Michał”,17)
Prelude> („Jan”, „Kowalski”,1980, „Częstochowa”, False)

Krotki mają ściśle określoną liczbę elementów. Nie możliwe jest więc dołączenie czegokolwiek do krotki. Krotki zawierające dwa elementy są nazywane parami.

Pary

Krotki zawierające pary są bardzo często wykorzystywane (np. współrzędne punktu na płaszczyźnie, imię + wiek). Aby ułatwić pracę ze zmiennymi tego typu język Haskell dostarcza dwie funkcje, które pozwalają odczytać wartości elementów pary:

Prelude> fst (3,4)
3
Prelude> snd (3,4)
4

Krotki w krotkach

Podobnie jak w przypadku list, również krotki mogą być częścią innych krotek.

Przykładem takiego zastosowania krotek może być struktura zawierająca dane samochodu, jego właściciela oraz na przykład datę wygaśnięcia polisy na ten samochód (dzień, miesiąc, rok). Dane właściciela to osobna krotka zawierająca imię, nazwisko, oraz wiek. Kolejną krotką są dane samochodu. W jej skład wchodzą marka, model i rok produkcji.

Prelude> (("Jan","Kowalski",35),("Opel","Tigra",1999), 10, 1, 2008)

Połączenie list i krotek

Ponieważ krotki i listy są pewnymi typami danych, możliwe jest utworzenie listy zawierającej krotki, krotki zawierającej listy, lub innych dowolnych kombinacji tych struktur danych.

Utworzona w poprzednim przykładzie struktura mogłaby być wykorzystana w programie dla zakładu ubezpieczeń. Jak wiadomo, zakład ubezpieczeń ubezpiecza zazwyczaj więcej niż jeden samochód. Do wygodnego przechowywania większej liczby takich krotek może zostać wykorzystana lista.

 Prelude> [(("Jan","Kowalski",35),("Opel","Tigra",1999), 10, 1, 2008),
           (("Dyzio","Marzyciel",23),("Mercedes","SLK 280",2006), 5, 4, 2007)]

Gdy chcemy zbudować strukturę przechowującą imię, nazwisko i oceny danego ucznia, wygodnym rozwiązaniem będzie wykorzystanie krotki składającej się z list, oraz dwóch Stringów. Każda lista będzie odpowiadać jednemu przedmiotowi.

Prelude> ( "Jaś","Kowalski",[4,4,5],[],[3,2,4],[5,5,5,4],[3,3,2],[2])

Jeśli potrzebne by było przechowanie danych całej klasy, nic nie stoi na przeszkodzie, aby utworzyć listę takich krotek. Następnie można by utworzyć krotkę przechowującą nazwę klasy oraz listę wyników uczniów... Później listę klas i ich osiągnięć w szkole... Listę szkół w mieście itd.

Funkcje rekurencyjne

Rekurencja

Chyba każdy program (poza "Hello world") napisany w języku imperatywnym wykorzystuje jakiegoś rodzaju pętle. Działanie pętli kończy się, gdy zostanie spełniony (lub nie spełniony) pewien warunek. Wiąże się to ze zmianą wartości zmiennej będącej licznikiem pętli. Jak wiadomo, zmiana wartości zmiennej w Haskellu nie jest możliwa, a więc zastosowanie pętli staje się również niemożliwe. Wszystkie zadania, które w językach imperatywnych są wykonywane w pętli, w Haskellu można zrealizować wykorzystując rekurencję.

Silnia

Wspomnianym już wcześniej przykładem, który doskonale obrazuje działanie rekurencji, jest funkcja obliczająca wartość silni z danej liczby. Zadaniem funkcji jest pomnożenie wszystkich liczb naturalnych mniejszych lub równych danej liczbie. Na przykład silnia z liczby 5 to 5 * 4 * 3 * 2 * 1 = 120.

Aby zobrazować działanie rekurencji przyjrzyjmy się silni z dwóch kolejnych liczb:

silnia 5 =  5 * 4 * 3 * 2 * 1
silnia 4 =      4 * 3 * 2 * 1

Jak widać silnia z liczby 5 jest równa silni z liczby 4 pomnożonej przez liczbę 5.

silnia 5 = 5 * silnia 4

Można uogólnić ten zapis w następujący sposób:

silnia n = n * silnia (n-1)

Rekurencyjna definicja funkcji potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego), oraz przypadku ogólnego (rekurencyjnego). Jeśli funkcja rekurencyjna nie ma zdefiniowanego przypadku bazowego jej działanie nigdy się nie zakończy. Powyżej zdefiniowany został przypadek ogólny. Pozostało więc jeszcze zdefiniowanie przypadku bazowego. Będzie nim obliczenie wartości silni dla liczby 0. Zastosowanie ogólnej definicji dla liczby 0 wyglądałoby następująco:

silnia 0 = 0 * silnia (-1)

Zapis ten jest błędny, ponieważ nie możliwe jest obliczenie silni z liczby ujemnej. Zgodnie z definicją silni:

silnia 0 = 1

Pełna definicja funkcji wyznaczającej silnię jest więc następująca:

silnia 0 = 1
silnia n = n * silnia (n-1)

Rekurencyjne mnożenie dwóch liczb

Z pewnością każdy programista, zarówno piszący w językach imperatywnych jak i funkcyjnych, aby pomnożyć dwie liczby a i b napisze po prostu a * b. Mnożenie można jednak zapisać w sposób rekurencyjny. Wykorzystamy do tego definicję podawaną dzieciom w szkole podstawowej. Aby pomnożyć liczbę a razy liczbę b, weź liczbę a i dodaj do siebie b razy. Na przykład 6*4 = 6+6+6+6. Podobnie jak w poprzednim przykładzie, zapiszmy dwa przykłady mnożenia.

6 * 4 = 6 + 6 + 6 + 6
6 * 3 =     6 + 6 + 6 

Tak samo jak w przypadku silni zapis ten możemy uogólnić:

a * b = a + a * (b-1)

Pozostaje jeszcze zdefiniowanie przypadku bazowego. Będzie to mnożenie przez liczbę 0. Dowolna liczba pomnożona przez 0 daje 0.

a * 0 = 0

Funkcja pomnoz zapisana w Haskellu będzie więc wyglądać następująco:

pomnoz a 0 =  0
pomnoz a b =  a + pomnoz a (b-1)

Więcej na temat funkcji

Funkcje

"Curried functions"

Funkcje "curried" to funkcje przyjmujące N parametrów, które możemy traktować jako funkcje przyjmujące jeden parametr i zwracające funkcje przyjmującą N-1 parametrów.

Poniższa definicja przedstawia funkcję, która dodaje dwa przekazane jej argumenty:

add :: Integer -> Integer -> Integer
add a b = a + b

Jest to przykład funkcji "curried". Definicję typu powyższej funkcji można zapisać jako:

add :: Integer -> (Integer -> Integer)
add a b = a + b

jest to funkcja przyjmująca parametr typu Integer oraz zwracająca funkcję typu Integer->Integer (przyjmującą i zwracającą liczbę całkowitą)

Użycie tej funkcji:

add a b

jest więc równoznaczne z:

(add a) b

Zastosowanie add do pierwszego argumentu zwraca nową funkcję, która jest stosowana do drugiego argumentu.

Currying jest możliwy dzięki temu, że

• użycie funkcji wiąże w lewo, więc f x y jest równoznaczne z (f x) y
• operator -> wiąże w prawo, więc a->a->a jest równoznaczne z a->(a->a)

Wykorzystując własności funkcji "curried" można szybko i wygodnie definiować nowe funkcje poprzez tzw. częściowe użycie już istniejących funkcji. Na przykład, aby zdefiniować funkcję realizującą inkrementację wystarczy napisać:

inc = add 1

Powyższy przykład pokazuje jedną z sytuacji, w których funkcja może być traktowana jako wartość zwracana przez inną funkcję. Kolejny przykład przedstawia sytuację, w której funkcja jest przekazywana jako argument innej funkcji.

map :: (a->b)->[a]->[b]
map f [] = []
map f (x:xs)= f x : map f xs

Przykład ten pokazuje jeszcze jedną ważną własność funkcji. Użycie funkcji ma wyższy priorytet niż jakikolwiek operator infiksowy. Dzięki temu

f x : map f xs 

jest równoznaczne z

(f x) : (map f xs)

Funkcje wyższego rzędu (higher-order functions)

Przykładem zastosowania funkcji map może być:

map (add 1) [1,2,3]
[2,3,4]

Funkcja map wykorzystuje inną funkcję (funkcję zwracaną przez add 1). Tego typu funkcje nazywane są funkcjami wyższego rzędu.

Funkcje wyższego rzędu są stosowane w językach funkcyjnych bardzo często. Bez ich istnienia w zasadzie ciężko sobie wyobrazić sens programowania funkcyjnego.

Kolejny przykład to funkcja wyznaczająca liczbę elementów listy spełniających warunek "p".

numOf p xs = length (filter p xs)

Zarówno funkcja filter, jak i numOf są funkcjami wyższego rzędu.

Funkcje Lambda

Wszystkie definiowane dotychczas funkcje posiadały swoją nazwę oraz równania opisujące działanie tej funkcji. Haskell umożliwia również definiowanie funkcji nienazwanych (anonimowych). Realizowane jest to za pomocą tzw. "lambda abstraction". Na przykład funkcja realizująca inkrementację może być zapisana następująco:

\x -> x+1

Funkcje lambda równie dobrze mogą przyjmować więcej niż 1 argument.

\x -> \y -> x+y 

Powyższa funkcja wykonuje dodawanie dwóch liczb. Można ją również zdefiniować w krótszy sposób:

\x y -> x+y

Funkcje lambda mogą być również użyte do definiowania funkcji nazwanych. Na przykład

add = \x y -> x+y

jest równoznaczne z

add x y = x+y

Funkcje lambda są bardzo wygodne podczas wykorzystania funkcji wyższego rzędu. W jednym z powyższych przykładów została wykorzystana funkcja map, która za pomocą funkcji inc zwiększała o 1 każdy z elementów listy. Do jej wykorzystania konieczna była osobna definicja funkcji inc. Funkcje lambda pozwalają na zdefiniowanie funkcji zwiększającej element o 1 bezpośrednio podczas użycia funkcji map.

map (\x -> x+1) [1,2,3]

Obsługa błędów - funkcja error

Podstawowa obsługa błędów w Haskellu jest realizowana za pomocą funkcji error. Funkcja ta przyjmuje komunikat w postaci łańcucha znaków i (w rozsądnych implementacjach Haskella) wypisuje ten komunikat na ekran jako błąd programu. Na przykład definicja funkcji head z the Standard Prelude wygląda następująco:

head (x:xs)             =  x
head  []                =  error "head{PreludeList}: head []"

Funkcję error można oczywiście stosować we własnych funkcjach, na przykład:

podziel a 0 = error "próbujesz dzielić przez zero!"
podziel a b = a/b

Operatory

Operatory matematyczne i logiczne

operator	działanie
+	dodawanie
-	odejmowanie
*	mnożenie
/	dzielenie
^,^^,**	potęgowanie
&&	AND
||	OR
<	mniejszy niż
<=	mniejszy lub równy
>	większy niż
>=	większy lub równy
==	równy
/=	różny

Operatory działające na listach

operator	działanie
++	konkatenacja list
:	dodanie elementu (głowy) do listy, "cons" operator
!!	operator indeksowania
..	specyfikacja zakresu listy

Przykłady użycia

Operator konkatenacji (++) łączy dwie listy dodając drugą na koniec pierwszej:

Prelude> [1,2,3] ++ [4,5]
[1,2,3,4,5]

"Cons" operator tworzy nową listę poprzez dołączenie nowego elementu na początek listy.

Prelude> 1:[2,3,4,5]
[1,2,3,4,5]

Operator indeksowania (!!) zwraca element listy o podanym indeksie. Elementy indeksowane są od 0.

Prelude> ['a','b','c','d']!! 2
'c'

Operator (..) służy do tworzenia sekwencji arytmetycznych.

Prelude> [1..5]
[1,2,3,4,5]
Prelude> [1,3..5]
[1,3,5]

Operator (..) może być również zastosowany do tworzenia sekwencji o nieokreślonej długości.

Prelude> [1..]

Wykonanie powyższej instrukcji bezpośrednio w interpreterze nie jest jednak dobrym pomysłem. Interpreter będzie próbował wypisać na ekran całą listę, a ponieważ długość listy nie jest określona, wypisywane będą kolejne liczby, dopóki działanie interpretera nie zostanie przerwane.

Operatory definiowane przez użytkownika

Operatory infiksowe

Operatory infiksowe są funkcjami i podobnie jak "zwykłe" funkcje prefiksowe są definiowane za pomocą równań. Nazwy operatorów składają się z symboli, w przeciwieństwie do identyfikatorów funkcji, które są alfanumeryczne. Poniżej zdefiniowany został operator infiksowy (-^)

(-^) a b = b^a 

Prelude> 2 -^ 5
25

Jak widać identyfikator (nazwa) operatora jest zamknięta w nawiasach. Jednak podczas użycia operatora nawiasy już nie występują. Jeśli używając operatora jego nazwa zostanie umieszczona w nawiasach, operator ten zachowuje się jak zwykła funkcja prefiksowa, np.

Prelude> (-^) 2 5
25

Działanie tego operatora jest trochę sztuczne. Przykład ten ma na celu jedynie zaprezentowanie sposobu definicji takich operatorów.

Funkcje jako operatory infiksowe

Operatory infiksowe mogą być używane jako funkcje prefiksowe. Możliwa jest również sytuacja odwrotna. Zdefiniowana wcześniej dwuargumentowa funkcja prefiksowa add może być używana jak funkcja infiksowa.

Prelude> 2 `add` 3
5

Aby funkcja dwuargumentowa mogła być używana jako funkcja infiksowa, jej nazwa musi być ujęta w odwrotne apostrofy.

Sekcje - częściowe użycie operatorów infiksowych

Ponieważ operatory infiksowe są tak naprawdę funkcjami, podobnie jak w przypadku funkcji możliwe jest ich częściowe użycie, nazywane w tym przypadku sekcją. Dzięki zastosowaniu sekcji można zdefiniować na przykład funkcję realizującą inkrementację.

inc = (+1)

w podobny sposób można zdefiniować również dodawanie dwóch liczb:

add = (+)

Sekcje można tworzyć również z funkcji infiksowych, na przykład:

inc = (1 `add`)

Sekcje, podobnie jak funkcje lambda, stanowią bardzo wygodny mechanizm w połączeniu z funkcjami wyższego rzędu. Funkcja map zwiększająca swoje elementy o 1 może wyglądać następująco:

map (+1) [1,2,3,4]

Operatory prefiksowe

Jedynym operatorem prefiksowym występującym w języku Haskell jest operator minus (-), który jest równocześnie operatorem prefiksowym i infiksowym.

Priorytety operatorów

Priorytety operatorów decydują o tym, który operator ma pierwszeństwo wykonania przed innym. Priorytet operatora to liczba całkowita z zakresu od 0 do 9 włącznie (im wyższy tym silniejszy). Priorytet 10 jest zarezerwowany do wywołania funkcji.

Działanie priorytetów najłatwiej zaobserwować na podstawowych operatorach matematycznych. Operator + ma priorytet 6, natomiast operator * 7. Wynika z tego, że mnożenie będzie wykonane wcześniej niż dodawanie.

Prelude> 2 + 2 * 2
6

Jak widać kolejność działań została zachowana zgodnie z ich priorytetami. Jeśli priorytet dodawania byłby taki sam, lub większy niż priorytet mnożenia, wynikiem powyższego działania byłaby liczba 8.

Wynikiem działania 2*3*4 jest oczywiście 24. Nieco zaskakujący może być jednak wynik potęgowania 2^3^4. Można by się spodziewać wyniku 4096 (8^4). Wykonanie takiego działania daje jednak zupełnie inny rezultat:

Prelude> 2^3^4
2417851639229258349412352

Kolejność wykonania operatorów jest określona przez priorytet operatora oraz przez dodatkową właściwość "fixity", która decyduje czy operator wiąże w lewo ("left-associative"), w prawo ("right-associative") czy równorzędnie w obu kierunkach ("non-associative"). Operator * wiąże w lewo, więc najpierw wykonane zostało działanie 2*3, a następnie 6*4. Operator ^ zalicza się do grupy "right-associative" w związku z czym najpierw wykonane zostało działanie 3^4, a następnie 2^81.

Poniższa tabela przedstawia priorytety standardowych operatorów.

Priorytet	Left associative	Non-associative	Right associative
9	!!		.
8			^, ^^, **
7	*, /, `div`,`mod`, `rem`, `quot`
6	+, -
5			:, ++
4		==, /=, <, <=, >, >=,`elem`, `notElem`
3			&&
2			||
1	>>, >>=
0			$, $!, `seq`

Definiowanie zachowania operatorów

Haskell umożliwia tworzenie własnych operatorów oraz określanie sposobu w jaki mają się zachowywać. Do tego celu przeznaczone są trzy funkcje: infix (non-associative), infixl (left-associative) oraz infixr (right-associative). Funkcje te przyjmują jako parametr priorytet oraz identyfikator operatora. Na przykład:

infixr 5 ++
infixl 3 `add`

Standardowy operator ++ jest operatorem wiążącym w prawo i posiada priorytet 5, natomiast operator zdefiniowany przez użytkownika `add` wiąże w lewo i posiada priorytet 3. Jeśli priorytet operatora nie zostanie zdefiniowany ma on domyślną wartość 9.

Dopasowanie wzorców i instrukcje warunkowe

Dopasowanie wzorców

Tak naprawdę dopasowanie wzorców pojawiało się już wielokrotnie. Na przykład funkcja map:

map _ [] = []
map f (x:xs)= f x : map f xs

wykorzystuje 4 różne wzorce.

• _ - dzika karta (wild-card)
• [] - pusta lista
• f - dowolne wyrażenie
• (x:xs) - coś co może powstać za pomocą operatora cons (:)

Wzorcem może być dowolne wyrażenie będące konstruktorem określonego typu.

Poniższy przykład wykorzystuje wzorzec, który dopasowuje wyrażenie do określonych wartości:

fun :: ([a], Bool) -> Int -> Int
fun    ([], True) 1 = 0

Do wzorca dopasowana zostanie tylko krotka o dokładnie takich wartościach jakie zostały określone we wzorcu. Często potrzebujemy dopasować do danego wzorca kilka zestawów parametrów spełniających określone warunki.

Załóżmy, że chcemy napisać funkcję "podziel a b" działającą w następujący sposób:

• jeśli oba parametry będą równe 0 - funkcja zwróci 0
• jeśli drugi parametr będzie równy 1 - funkcja zwróci wartość pierwszego parametru (nie wykonując dzielenia)
• jeśli drugi parametr będzie równy 0 - funkcja zwróci błąd - dzielenie przez 0
• jeśli żaden z powyższych warunków nie będzie spełniony funkcja wykona dzielenie i zwróci wynik

Pierwszy warunek może zostać zrealizowany za pomocą wzorca podobnego do tego z poprzedniego przykładu:

podziel 0 0 = 0

W kolejnym przypadku pierwsza wartość może być dowolną liczbą, wartość drugiego parametru to 1.

podziel a 1 = a

Jeśli drugi z parametrów będzie równy 0 zostanie wywołana funkcja error. Na pierwszy rzut oka warunek ten wygląda podobnie do poprzedniego. W poprzednim przypadku jednak wartość pierwszego parametru była potrzebna do wyznaczenia wartości funkcji. Tutaj pierwszy parametr w żaden sposób nie jest wykorzystywany. Pozwala to na zastosowanie wzorca nazywanego dziką kartą (wild-card). Wzorzec ten oznaczony jest za pomocą symbolu "_".

podziel _ 0 = error "dzielenie przez zero"

Ostatni z warunków zrealizowany zostanie za pomocą wzorca, do którego dopasowane zostaną dowolne dwie liczby, które nie zostały dopasowane do powyższych wzorców.

podziel a b = a/b

Dopasowanie wzorców i listy

Mechanizm dopasowania wzorców jest bardzo przydatny podczas pracy z listami.

Jak wiadomo, jako wzorzec może zostać użyte dowolne wyrażenie będące konstruktorem określonego typu. Lista może być utworzona na 3 sposoby:

• poprzez wypisanie wszystkich jej elementów oddzielonych przecinkami np. [1,2,3]
• poprzez symbol listy pustej []
• poprzez operator cons (:), który tworzy listę danego elementu oraz starej listy np. 1:[2,3]

Wszystkie wymienione przypadki można wykorzystać podczas tworzenia wzorców.

Do wzorca [a,b,c] zostanie dopasowana każda lista trójelementowa. Wartości listy zostaną przypisane do odpowiednich identyfikatorów (a,b lub c).

Do wzorca [] zostanie dopasowana tylko i wyłącznie lista pusta.

Do wzorca (x:xs) zostanie dopasowana każda lista, którą da się utworzyć za pomocą operatora cons, a więc taka, która posiada co najmniej jeden element (listę pustą można utworzyć jedynie za pomocą symbolu "[]").

Oczywiście nic nie stoi na przeszkodzie, aby podczas tworzenia wzorców do których dopasowywane są listy używać dzikiej karty. Na przykład definicja funkcji tail zwracającej ogon listy nie musi znać wartości głowy listy.

tail (_:xs) = xs

Definicja funkcji head nie musi natomiast wiedzieć jak wygląda ogon. Ważna jest tylko wartość głowy.

head (x:_) = x

Operator cons może być stosowany wielokrotnie w jednym wzorcu. Definicja funkcji zwracającej trzeci element z listy może wyglądać następująco:

trzeci (_:_:x:_) = x

Wzorzec n+k

Jak wcześniej wspomniano, wzorzec to konstruktor dowolnego typu. Od tej reguły jest jednak wyjątek nazywany wzorcem "n+k".

fun (a+1) = a

Taka funkcja zostanie uznana za poprawną, mimo iż (a+1) nie jest konstruktorem żadnego typu. Konstrukcje tego typu są poprawne, ale powinno się ich unikać, gdyż są mało czytelne. Lepszym rozwiązaniem jest zapisanie funkcji w następujący sposób:

fun a = a-1

Wzorzec "as"

Czasami warto nadać pewnej części wzorca (lub całemu wzorcowi) identyfikator, który można wykorzystywać po prawej stronie równania. Na przykład funkcja dublująca pierwszy element listy może wyglądać tak:

fun (x:xs) = x:x:xs

Wzorzec x:xs pojawia sie w identycznej formie po lewej i po prawej stronie równania. Aby zwiększyć czytelność można nadać mu identyfikator za pomocą wzorca "as" (symbol "@"):

fun s@(x:xs) = x:s

Wzorzec "as" nie wpływa na działanie funkcji, a jedynie zwiększa czytelność kodu.

Stosowanie wzorców

W powyższych przykładach wzorce były używane w równaniach definiujących funkcję. Nie jest to jednak jedyne miejsce gdzie znajdują one zastosowanie. Wzorce stosowane są między innymi w:

• funkcjach lambda
• instrukcji case
• wyrażeniach where oraz let

Instrukcje warunkowe

if ... then

if <warunek> then <true-value> else <false-value>

Jeśli spełniony zostanie warunek zwracana jest wartość <true-value> w przeciwnym wypadku <false-value> Warto zauważyć, że <true-value> oraz <false-value> są wartościami zwracanymi przez wyrażenie if, a nie (jak w większości języków) sekwencjami instrukcji do wykonania.

case

case <wyrazenie> of
    <wzorzec_1> -> <wartosc_1>
    <wzorzec_2> -> <wartosc_2>
    ...
    <wzorzec_n> -> <wartosc_n>

Instrukcja "case" jest uogólnieniem instrukcji "if". Instrukcja "if" zwraca wartość w zależności od tego jaka jest wartość wyrażenia typu logicznego (warunku). Instrukcja "case" umożliwia zwrócenie różnych wartości w zależności od tego jaką wartość będzie miało wyrażenie dowolnego typu, a dokładniej mówiąc w zależności od tego do jakiego wzorca zostanie dopasowane. Instrukcję "if" można zapisać za pomocą "case" w następujący sposób:

case <warunek> of
    True  -> <true-value>
    False -> <false-value>

Poniższy przykład wykorzystuje instrukcję case do konwersji liczby na dzień tygodnia:

case i of
    1 -> "Poniedzialek"
    2 -> "Wtorek"
    3 -> "Środa"
    4 -> "Czwartek"
    5 -> "Piątek"
    6 -> "Sobota"
    7 -> "Niedziela"

Zmienna "i" dopasowana jest do jednej z liczb. Możliwe jest również dopasowanie do innych typów wzorców. Za pomocą instrukcji "case" możliwe jest zdefiniowanie funkcji "podziel" działającej tak samo jak zdefiniowana wcześniej funkcja. Nowa funkcja "podziel", w przeciwieństwie poprzedniej, przyjmuje parametry jako krotkę:

 podziel (a,b) = 
  case (a,b) of 
	     (0,0)-> 0
	     (_,1)-> a
	     (_,0)-> error "dzielenie przez zero"
	     (a,b)-> a/b

Guard - strażnicy

| <warunek_1> = <wartosc_1>
| <warunek_2> = <wartosc_2>
...
| <warunek_n> = <wartosc_n>

Instrukcje "if" oraz "case" mają swoje odpowiedniki w większości języków programowania. Strażnicy to instrukcja, którą możemy porównać do instrukcji "if" z dodatkowymi warunkami "if else". Przykładem wykorzystania strażników może być funkcja określająca znak liczby:

 sign a 
    | a>0 = "dodatnia"
    | a==0 = "zero"
    | a<0 = "ujemna"

Strażnicy to kolejne warunki odpowiadające "if else". Aby określić jaka wartość powinna być zwrócona jeśli żaden z warunków nie zostanie spełniony (odpowiednik "else") definiując ostatniego strażnika zamiast warunku należy wpisać "otherwise". Na przykład:

duzaCzyMala c | c >= 'a' && c <= 'z' = "Mała"
	      | c >= 'A' && c <= 'Z' = "Duża"
	      | otherwise            = "to nie litera!" 

Funkcje działające na listach

Standardowe funkcje operujące na listach

Język Haskell dostarcza zestaw standardowych funkcji i operatorów działających na listach. Poniżej zaprezentowane zostało kilka z nich oraz przykładowy sposób implementacji funkcji działającej w ten sam sposób co dana funkcja standardowa. W większości przypadków są to funkcje rekurencyjne.

head i tail - głowa i ogon listy

Funkcje head i tail zwracają odpowiednio głowę i ogon listy

Prelude> head [1,2,3]
1
Prelude> tail [1,2,3]
[2,3]

Definicje tych funkcji zostały przedstawione w rozdziale Dopasowanie wzorców i instrukcje warunkowe

Operator !!

Operator !! zwraca i-ty element listy

Prelude> [1,2,3,4] !! 2
3

Aby napisać taką funkcję, działającą tak jak operator !!, należy rozpatrzyć dwa przypadki:

• przypadek bazowy - dla indeksu równego 0 – zwrócona zostanie głowa listy.
• przypadek ogólny – rekurencyjnie wywołana zostanie funkcja, której jako parametry przekażemy ogon listy i indeks zmniejszony o jeden.

elem_nr (h:_) 0 = h
elem_nr (_:t) i = elem_nr t (i-1)

Długość listy

Funkcja length zwraca długość listy podanej jako parametr

Prelude> length [1,2,3,4]
4

Aby napisać funkcję działającą tak samo jak funkcja length należy wykorzystać to, iż długość ogona listy jest o jeden mniejsza od długości całej listy. Aby obliczyć długość listy należy więc obliczyć długość jej ogona i dodać do niej jeden. Wywoływana rekurencyjnie funkcja będzie musiała w pewnym momencie wyznaczyć długość listy pustej. Ten przypadek zostanie zdefiniowany osobno. Funkcja wywołana z argumentem będącym listą pustą powinna zwrócić 0.

dlugosc [] = 0
dlugosc (_:t) = 1 + dlugosc t

Operator konkatenacji

Do konkatenacji, czyli połączenia dwóch list w jedną służy operator ++

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

Implementacja funkcji wykonującej konkatenacje dwóch list jest zadaniem zdecydowanie trudniejszym. Należy pamiętać, że niemożliwe jest dołączenie elementu na końcu listy, a jedynie na jej początku. Funkcja musi więc dołączać elementy pierwszej listy do drugiej. Jako pierwszy do drugiej listy powinien być dołączony ostatni element pierwszej listy. Niestety odczyt elementu możliwy jest tylko na początku listy.

Aby zrealizować operację konkatenacji musimy więc dołączyć głowę pierwszej listy do listy powstałej z połączenia ogona pierwszej listy oraz całej drugiej listy. Podobnie jak w poprzednim przykładzie konieczne jest zdefiniowanie operacji konkatenacji dla przypadku gdy pierwsza z przekazanych list będzie listą pustą. W tym przypadku funkcja powinna zwrócić drugą listę.

konkatenacja [] l2 = l2
konkatenacja (h:t) l2 = h : (konkatenacja t l2)

Typy definiowane przez użytkownika

Typy definiowane przez użytkownika

Haskell dostarcza trzy sposoby definiowania nowych typów:

• data
• type
• newtype

Mechanizm synonimów (type) został opisany w rozdziale Typy danych. newtype to mechanizm wykorzystywany głownie do optymalizacji. W tym rozdziale przedstawione zostanie wykorzystanie słowa kluczowego data, dzięki któremu możemy definiować struktury oraz typy wyliczeniowe.

Przykład prostego typu wyliczeniowego

Przykładem prostego typu wyliczeniowego może być typ Sygnalizacja opisujący kolory sygnalizacji świetlnej:

data Sygnalizacja = Czerwone | Zolte | Zielone

Sygnalizacja jest tutaj konstruktorem typu, natomiast Czerwone, Zolte i Zielone to konstruktory wartości. Zarówno konstruktor typu, jak i konstruktory wartości w tym przypadku nie przyjmują parametrów.

Typ Sygnalizacja możemy użyć w funkcji coRobic:

coRobic::Sygnalizacja -> String
coRobic Czerwone = "Stój"
coRobic Zolte = "Uważaj"
coRobic Zielone = "Jedź"

Złożone typy definiowane przez użytkownika

Możemy tworzyć bardziej skomplikowane struktury danych, na przykład typ opisujący produkty w sklepie:

 data Produkty =
    Ksiazka String String Int Double     --tytul, autor, liczba stron, cena
    | Gazeta String Int Double           --tytuł, numer, cena
    | Zeszyt Int Double                  --liczba kartek, cena

Po utworzeni struktury można definiować zmienne typu Produkty. Konstruktor typu Produkty podobnie jak w poprzednim przykładzie nie wymaga podania parametrów, natomiast konstruktory Ksiazka, Gazeta oraz Zeszyt wymagają podania odpowiednich zestawów parametrów (odpowiednich dla każdej wartości)

 p1 :: Produkt
 p1 = Zeszyt 60 2.3

 p2 :: Produkt
 p2 = Gazeta "Ciekawa gazeta" 123 8.5

 p3 :: Produkt
 p3 = Ksiazka "Haskell to fajny jezyk" "Jas Kowalski" 450 70

Ponieważ Książka, Gazeta i Zeszyt są tego samego typu, można utworzyć funkcję, która będzie przyjmowała dowolny Produkt, na przykład funkcję zwracającą opis produktu:

 pokazProdukt :: Produkt -> String
 
 pokazProdukt (Ksiazka tytul autor l_stron cena) = tytul ++ "; autor: " ++ autor ++ "; "  ++ show 
 l_stron ++ " stron; " ++ show cena ++ "PLN"
 
 pokazProdukt (Gazeta tytul numer cena) = tytul ++ "; numer: " ++ show numer ++ "; " ++ show cena 
 ++ "PLN"
 
 pokazProdukt (Zeszyt l_kartek cena) = "Zeszyt " ++ show l_kartek ++ " kartkowy; " ++ show cena ++
 "PLN"

Typy rekursywne

Haskell pozwala na definicję rekursywnych typów danych (takich jak drzewo, kolejka itp.)

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

Jest to definicja polimorficznej struktury danych reprezentującej drzewo binarne. Element typu Tree mogą być:

• liśćmi (Leaf) - przechowują wartość typu a
• gałęziami (Branch) - składają się z dwóch innych drzew (które mogą być liśćmi lub innymi gałęziami)

Ponieważ jest to typ polimorficzny, konstruktor tego typu wymaga podania parametru. W tym przypadku jest to typ wartości przechowywanej w liściach drzewa. Również konstruktory Leaf oraz Branch wymagają podania odpowiedniego zestawu parametrów.

Zdefiniujmy teraz funkcję działającą na drzewie. Funkcja ta powinna odczytać wszystkie wartości przechowywane w liściach drzewa i zwrócić je w postaci listy:

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

Funkcja wywołana z parametrem będącym liściem zwraca listę jednoelementową zawierającą wartość przechowywaną w liściu. Funkcja wywołana z parametrem będącym gałęzią wywołuje rekurencyjnie tą samą funkcję w stosunku do dwóch swoich poddrzew oraz łączy listy uzyskane z tych wywołań.