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