Haskell/Wersja do druku

1

Haskell/Wersja do druku

Ania

Haskell

Aktualna, edytowalna wersja tego podręcznika jest dostępna w Wikibooks, bibliotece wolnych podręczników pod

adresem

http:/

/

en.

wikipedia.

org/

wiki/

%3Ahaskell

Całość tekstu jest objęta licencją GNU Free Documentation License.

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.

Haskell/Wersja do druku

2

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/Wersja do druku

3

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 staje się coraz bardziej 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. Język nie jest

tylko narzędziem, jest sposobem myślenia. 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.

Szkoda, że tak się dzieje, gdyż rekurencja pozwala na bardzo zgrabne sformułowanie rozwiązań wielu problemów.

Programowanie przy użyciu stałych zapobiega szerokiej klasie trudnych do wyśledzenia błędów. Używanie funkcji

pozwala na uniknięcie niepotrzebnego rozrostu klas i interfejsów. A rygor typów znacznie pomaga w tworzeniu

niezawodnego oprogramowania.

Witaj inny świecie!

Kompilatory i interpretery

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 - wolniejszy niż Hugs. Pozwala na interpretacje programów oraz kompilację. 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.

Haskell/Wersja do druku

4

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.

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

Haskell/Wersja do druku

5

interpretera, a nie elementem języka. Można nieco ją 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

Ćwiczenie

1. Napisz funkcję przyjmującą jako parametr liczbę całkowitą n i wyznaczającą sumę dodatnich liczb parzystych mniejszych lub

równych n (reszta z dzielenia liczby a przez b uzyskujemy za pomocą: mod a b).

2. Napisz funkcję znajdującą największy wspólny dzielnik dla dwóch dodatnich liczb całkowitych.

3. Napisz funkcję wyznaczającą (z definicji) n-ty element ciągu Fibbonacciego.

Zmienne i funkcje

Zmienne

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 zmiennych za pomocą słowa let. Po jednokrotnym zdefiniowaniu wartości pi

można używać jej w dalszych obliczeniach. Nazwy zmiennych (oraz funkcji) muszą rozpoczynać się od małej litery.

Prelude> let pi = 3.14159265358979323846264338327950

Prelude> pi

Haskell/Wersja do druku

6

3.141592653589793

Liczba pi jest „obcinana” do 16 cyfr jedynie podczas wyświetlania.

Prelude> pi * 5 * 5

78.53981633974483

Jeśli chcielibyśmy również promień zastąpić zmienną 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

zmiennej r jako liczby rzeczywistej:

Prelude> let r = 5.0

Zmienne 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ść zmiennej jest niezmienna. 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

Zmienną poleKola (podobnie jak inne zmienne) można potraktować jak funkcję nieprzyjmującą żadnych parametrów. Zgodnie z zasadą

referencyjnej przeźroczystości funkcja wywołana z takim samym zestawem parametrów (w tym przypadku lista parametrów jest pusta)

zawsze zwróci tą samą wartość. Zmienna r jest zmienną globalną, a działanie funkcji nie może być zależne od żadnej zmiennej globalnej.

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

Haskell/Wersja do druku

7

Zmienna r wewnątrz funkcji poleKola jest zmienną lokalną. Wartość zmiennej 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 zmiennej 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> 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

Ćwiczenie

1. Zdefiniuj funkcję przyjmującą imię i witającą się (np. po podaniu imienia Tomek funkcja zwraca "Witaj Tomek!"). Do łączenia

łańcuchów znaków służy operator ++.

2. Utwórz funkcję obliczającą odległość dwóch punktów na płaszczyźnie (funkcja będzie przyjmować 4 współrzędne x1, y1, x2 i y2).

Następnie napisz funkcję, która będzie przyjmować współrzędne wierzchołków trójkąta (6 liczb) oraz zwróci obwód trójkąta. Funkcja

obliczająca obwód powinna wykorzystywać funkcję wyznaczającą odległość punktów.

Haskell/Wersja do druku

8

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.

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.

Haskell/Wersja do druku

9

Typ znakowy

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

Podobnie jak w wielu innych językach (np. C++), również w Haskellu pojedyncze znaki (Char) są w apostrofach, natomiast łańcuchy

znaków (String) w cudzysłowach.

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 then - mniejszy niż)

• EQ (equal - równy)

• GT (greater then - 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

Haskell/Wersja do druku

10

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.

Haskell/Wersja do druku

11

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]

Haskell/Wersja do druku

12

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]

Uwaga!

W przypadku liczb ujemnych konieczne jest umieszczenie ostatniego elementu listy w nawiasach

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..]

Uwaga!

Wykonanie powyższej instrukcji w interpreterze spowoduje próbę wypisania całej listy na ekran. W rezultacie interpreter będzie

wypisywał kolejne elementy listy dopóki nie przerwiemy jego działania

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.

Haskell/Wersja do druku

13

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]

Uwaga!

Dwie listy zawierające elementy różnych typów (np. [1,2,3] i ['a','b','c']), nie są strukturami tego samego typu. Nie możliwe jest więc

utworzenie tablicy, której pierwszym wierszem będzie na przykład lista liczb typu Integer, a drugim lista zmiennych typu Char

Prelude> [[1,2,3],['a','b','c']]

<interactive>:1:2

No instance for (Num Char)

arising from the literal `1' at <interactive>:1:2

Possible fix: add instance declaration for (Num Char)

In the expression: 1

In the expression: [1,2,3]

In the expression: [[1,2,3],['a','b','c']]

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.

Uwaga!

Typ krotki jest definiowany nie tylko przez jej wielkość, ale również przez typy obiektów które dana krotka zawiera. Krotki o różnych

typach obiektów składowych, są elementami różnych typów.

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

Uwaga!

Funkcje fst i snd działają tylko dla par. Nie jest możliwe stosowanie ich do krotek o innej liczbie elementów.

Haskell/Wersja do druku

14

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ę.

W językach imperatywnych rekurencja jest stosowana rzadko, między innymi ze względu na słabą wydajność. Kompilatory języków

funkcyjnych posiadają bardzo dobre mechanizmy optymalizacji dla rekurencji (np. optymizacja tail-call).

Haskell/Wersja do druku

15

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)

Funkcje należy zdefiniować w osobnym pliku (np. fun.hs) a następnie załadować ją do interpretera z pomocą polecenia :load (lub krócej

:l)

Prelude> :l fun.hs

Po załadowaniu można używać tej funkcji w interpreterze, na przykład:

Prelude> silnia 5

120

Uwaga!

Należy pamiętać, że język Haskell podczas wywołania funkcji analizuje po kolei kod programu, próbując dopasować parametry, z którymi

funkcja została wywołana do definicji w funkcji. Jeśli najpierw zdefiniowany zostałby przypadek ogólny funkcji, każde wywołanie

funkcji byłoby dopasowane do tego przypadku – również wywołanie z drugim parametrem równym 0. Kolejność definicji jest więc tutaj

bardzo ważna. Najpierw muszą zostać zdefiniowane przypadki bazowe (począwszy od najbardziej ściśle określonego), a dopiero na końcu
przypadek ogólny.

Haskell/Wersja do druku

16

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"

"Currying" to sposób transformacji funkcji przyjmującej wiele argumentów do funkcji przyjmującej jeden argument. Technika ta została

nazwana "currying" przez Christophera Strachey na cześć matematyka Haskella Curry, mimo iż została stworzona przez Mosesa

Schönfinkela i Gottloba Frege'a.

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:

Haskell/Wersja do druku

17

(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 x

jest równoznaczne z

(f x) : (map f x)

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.

Haskell/Wersja do druku

18

Funkcje Lambda

Rachunek lambda - system formalny używany do badania zagadnień związanych z podstawami matematyki jak rekurencja,

definiowalność funkcji, obliczalność, podstawy matematyki np. definicja liczb naturalnych itd. Rachunek Lambda został wprowadzony

przez Alonzo Churcha i Stephen Cole Kleene w 1930 roku. Rachunek lambda jest przydatny do badania algorytmów. Wszystkie

algorytmy, które dadzą się zapisać w rachunku lambda, dadzą się zaimplementować na maszynie Turinga i odwrotnie.

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

Haskell/Wersja do druku

19

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 zasięgu 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.

Haskell/Wersja do druku

20

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.

Haskell/Wersja do druku

21

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.

Haskell/Wersja do druku

22

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.

Uwaga!

Priorytet operatora `add` został ustalony na 3. Należy jednak pamiętać, że priorytet funkcji add nadal jest równy 10. Podczas stosowania

operatora `add` oraz operatora * najpierw wykonany zostanie operator *:

Prelude> 3 `add` 4 * 4

19

Zastosowanie add jako funkcji da jednak inny wynik:

Prelude> add 3 4 * 4

28

Użycie funkcji zawsze ma najwyższy priorytet.

Ćwiczenie

# Zdefiniuj operator +*+ wykonujący dodawanie dwóch liczb oraz zwiększający dodatkowo wynik o 1 (np. 2 +*+ 3 = 6) tak, aby był
wykonywany po dodawaniu i mnożeniu (1 + 2 +*+ 3 * 3 = 13).

1. Zdefiniuj nowy operator potęgowania ^^^, który dla działania 2 ^^^ 3 ^^^ 4 da wynik 4096 ( (2^3)^4 ).

Haskell/Wersja do druku

23

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

Haskell/Wersja do druku

24

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

Uwaga!

Operator (..) umożliwiający tworzenie sekwencji arytmetycznych nie jest konstruktorem listy. We wzorcach nie można wykorzystywać

wyrażeń typu [a,b..c] oraz [a,b..]

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

Haskell/Wersja do druku

25

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.

Uwaga!

"if" jest w Haskellu instrukcją, która zwraca pewną wartość. Wartość musi być zwrócona niezależnie od tego czy warunek będzie

spełniony, czy nie. W przeciwieństwie do wielu języków, Haskell wymaga użycia "else".

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:

Haskell/Wersja do druku

26

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

Uwaga!

Haskell nie wymaga stosowania średników na końcu linii. W pewnych przypadkach (między innymi w instrukcji case) wymagane jest

jednak stosowanie odpowiednich wcięć. Pierwszy znak po słowie "of" określa kolumnę w której powinny zaczynać się deklaracje

kolejnych wzorców.

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!"

Haskell/Wersja do druku

27

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

Haskell/Wersja do druku

28

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ź"

Haskell/Wersja do druku

29

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:

Haskell/Wersja do druku

30

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ń.

Ćwiczenie

1. Utwórz typ Klient, który posiada dwie wartości Indywidualny lub Firma. Klient indywidualny opisany jest za pomocą numeru klienta,

imienia, nazwiska, oraz numeru telefonu, firma natomiast za pomocą numeru klienta, nazwy firmy, NIPu, Regonu oraz numeru

telefonu. Napisz funkcję wyświetlającą informacje o kliencie.

2. Napisz definicję typu danych odpowiadającą kolejce. Zdefiniuj funkcję zwracającą wartość elementu przechowywanego w kolejce

oraz funkcję zwracającą kolejny element kolejki.

Źródła i autorzy artykułu

31

Źródła i autorzy artykułu

Haskell/Wersja do druku  Źródło: http://pl.wikibooks.org/w/index.php?oldid=58755  Autorzy: Derbeth

Źródła, licencje i autorzy grafik

Grafika:Fairytale messagebox info.png  Źródło: http://pl.wikibooks.org/w/index.php?title=Plik:Fairytale_messagebox_info.png  Licencja: GNU Lesser General Public License  Autorzy:
Amada44, Anime Addict AA, Bayo, Dake, Jon Harald Søby, ZooFari

Grafika:Nuvola apps important.svg  Źródło: http://pl.wikibooks.org/w/index.php?title=Plik:Nuvola_apps_important.svg  Licencja: GNU Lesser General Public License  Autorzy: User:Bastique

Licencja

Creative Commons Attribution-Share Alike 3.0 Unported
http:/

/

creativecommons.

org/

licenses/

by-sa/

3.

0/