Haskell/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.