Haskell Language
Listy
Szukaj…
Składnia
konstruktor pustej listy
[] :: [a]
niepusty konstruktor listy
(:) :: a -> [a] -> [a]
head - zwraca pierwszą wartość listy
head :: [a] -> a
last - zwraca ostatnią wartość listy
last :: [a] -> a
tail - zwraca listę bez pierwszego elementu
tail :: [a] -> [a]
init - zwraca listę bez ostatniego elementu
init :: [a] -> [a]
xs !! i - zwraca element o indeksie i na liście xs
(!!) :: Int -> [a] -> a
weź n xs - zwraca nową listę zawierającą n pierwszych elementów listy xs
take :: Int -> [a] -> [a]
mapa :: (a -> b) -> [a] -> [b]
filtr :: (a -> Bool) -> [a] -> [a]
(++) :: [a] -> [a]
concat :: [[a]] -> [a]
Uwagi
- Typ
[a]
jest równoważny z[] a
. -
[]
tworzy pustą listę. -
[]
w definicji funkcji LHS, np.f [] = ...
, jest pustym wzorcem listy. -
x:xs
tworzy listę, w której elementx
jest dodawany do listyxs
-
f (x:xs) = ...
to dopasowanie wzorca dla niepustej listy, gdziex
to głowa, axs
to ogon. -
f (a:b:cs) = ...
if (a:(b:cs)) = ...
są takie same. Są dopasowaniem wzorca dla listy co najmniej dwóch elementów, gdzie pierwszym elementem jesta
, drugim elementem jestb
, a resztą listy jestcs
. -
f ((a:as):bs) = ...
NIE jest tym samym cof (a:(as:bs)) = ...
Pierwsza z nich jest dopasowaniem do wzorca dla niepustej listy list, gdziea
jest głową głowy,as
ogonem głowy, abs
jest ogonem. -
f (x:[]) = ...
f [x] = ...
są takie same. Są dopasowaniem wzorca dla listy dokładnie jednego elementu. -
f (a:b:[]) = ...
f [a,b] = ...
są takie same. Są dopasowaniem wzorca dla listy dokładnie dwóch elementów. -
f [a:b] = ...
jest dopasowaniem wzorca dla listy dokładnie jednego elementu, gdzie element jest również listą.a
jest głową elementu, ab
jest ogonem elementu. -
[a,b,c]
jest taki sam jak(a:b:c:[])
. Standardowa notacja listy to po prostu cukier składniowy dla konstruktorów(:)
i[]
. - Możesz użyć
all@(x:y:ys)
, aby odnieść się do całej listy jakoall
(lub dowolnej innej wybranej nazwy) zamiast powtarzać(x:y:ys)
ponownie.
Lista literałów
emptyList = []
singletonList = [0] -- = 0 : []
listOfNums = [1, 2, 3] -- = 1 : 2 : [3]
listOfStrings = ["A", "B", "C"]
Łączenie list
listA = [1, 2, 3]
listB = [4, 5, 6]
listAThenB = listA ++ listB -- [1, 2, 3, 4, 5, 6]
(++) xs [] = xs
(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)
Podstawy listy
Konstruktor typów list w Preludium Haskell to []
. Deklaracja typu dla listy zawierającej wartości typu Int
jest zapisana w następujący sposób:
xs :: [Int] -- or equivalently, but less conveniently,
xs :: [] Int
Listy w Haskell są jednorodnymi sekwencjami , co oznacza, że wszystkie elementy muszą być tego samego typu. W przeciwieństwie do krotek długość listy nie ma wpływu na typ listy:
[1,2,3] :: [Int]
[1,2,3,4] :: [Int]
Listy są konstruowane przy użyciu dwóch konstruktorów :
[]
tworzy pustą listę.(:)
, wymawiane jako „minus”, dodaje elementy do listy. Uwzględnieniex
(wartość typua
) naxs
(lista wartości tego samego typua
) tworzy nową listę, której głowa (pierwszy element) tox
, a ogon (reszta elementów) toxs
.
Możemy zdefiniować proste listy w następujący sposób:
ys :: [a]
ys = []
xs :: [Int]
xs = 12 : (99 : (37 : []))
-- or = 12 : 99 : 37 : [] -- ((:) is right-associative)
-- or = [12, 99, 37] -- (syntactic sugar for lists)
Zauważ, że (++)
, którego można użyć do budowania list, zdefiniowano rekurencyjnie w kategoriach (:)
i []
.
Przetwarzanie list
Aby przetworzyć listy, możemy po prostu dopasować do wzorca konstruktorów typu listy:
listSum :: [Int] -> Int
listSum [] = 0
listSum (x:xs) = x + listSum xs
Możemy dopasować więcej wartości, określając bardziej skomplikowany wzór:
sumTwoPer :: [Int] -> Int
sumTwoPer [] = 0
sumTwoPer (x1:x2:xs) = x1 + x2 + sumTwoPer xs
sumTwoPer (x:xs) = x + sumTwoPer xs
Zauważ, że w powyższym przykładzie musieliśmy podać bardziej wyczerpujące dopasowanie wzorca, aby obsłużyć przypadki, w których jako argument podano listę o nieparzystej długości.
Preludium Haskell definiuje wiele wbudowanych funkcji do obsługi list, takich jak map
, filter
itp. Tam, gdzie to możliwe, powinieneś ich używać zamiast pisać własne funkcje rekurencyjne.
Dostęp do elementów na listach
Uzyskaj dostęp do n- tego elementu listy (od zera):
list = [1 .. 10]
firstElement = list !! 0 -- 1
Zauważ, że !!
jest funkcją częściową, więc niektóre dane wejściowe powodują błędy:
list !! (-1) -- *** Exception: Prelude.!!: negative index
list !! 1000 -- *** Exception: Prelude.!!: index too large
Istnieje również Data.List.genericIndex
, przeciążona wersja !!
, który przyjmuje dowolną wartość Integral
jako indeks.
import Data.List (genericIndex)
list `genericIndex` 4 -- 5
Po zaimplementowaniu jako pojedynczo połączonych list, operacje te trwają O (n) . Jeśli często uzyskujesz dostęp do elementów według indeksu, prawdopodobnie lepiej jest użyć Data.Vector
(z pakietu wektorowego ) lub innych struktur danych.
Zakresy
Utworzenie listy od 1 do 10 jest proste przy użyciu notacji zakresu:
[1..10] -- [1,2,3,4,5,6,7,8,9,10]
Aby określić krok, dodaj przecinek i następny element po elemencie początkowym:
[1,3..10] -- [1,3,5,7,9]
Zauważ, że Haskell zawsze przyjmuje krok jako arytmetyczną różnicę między terminami i że nie można podać więcej niż dwóch pierwszych elementów i górnej granicy:
[1,3,5..10] -- error
[1,3,9..20] -- error
Aby wygenerować zakres w kolejności malejącej, zawsze określ krok ujemny:
[5..1] -- []
[5,4..1] -- [5,4,3,2,1]
Ponieważ Haskell nie jest ścisły, elementy listy są oceniane tylko wtedy, gdy są potrzebne, co pozwala nam korzystać z nieskończonych list. [1..]
jest nieskończoną listą zaczynającą się od 1. Ta lista może być powiązana ze zmienną lub przekazana jako argument funkcji:
take 5 [1..] -- returns [1,2,3,4,5] even though [1..] is infinite
Zachowaj ostrożność przy stosowaniu zakresów z wartościami zmiennoprzecinkowymi, ponieważ akceptuje ono przelewanie do połowy delty, aby uniknąć problemów z zaokrąglaniem:
[1.0,1.5..2.4] -- [1.0,1.5,2.0,2.5] , though 2.5 > 2.4
[1.0,1.1..1.2] -- [1.0,1.1,1.2000000000000002] , though 1.2000000000000002 > 1.2
Zakresy działają nie tylko z liczbami, ale z dowolnym typem, który implementuje klasę Enum
. Biorąc pod uwagę niektóre wymienne zmienne a
, b
, c
, składnia zakresu jest równoważna z wywołaniem tych metod Enum
:
[a..] == enumFrom a
[a..c] == enumFromTo a c
[a,b..] == enumFromThen a b
[a,b..c] == enumFromThenTo a b c
Na przykład z Bool
jest
[False ..] -- [False,True]
Zwróć uwagę na spację po False
, aby zapobiec analizowaniu jej jako kwalifikacji nazwy modułu (tzn. False..
byłby analizowany jako .
Z modułu False
).
Podstawowe funkcje na listach
head [1..10] -- 1
last [1..20] -- 20
tail [1..5] -- [2, 3, 4, 5]
init [1..5] -- [1, 2, 3, 4]
length [1 .. 10] -- 10
reverse [1 .. 10] -- [10, 9 .. 1]
take 5 [1, 2 .. ] -- [1, 2, 3, 4, 5]
drop 5 [1 .. 10] -- [6, 7, 8, 9, 10]
concat [[1,2], [], [4]] -- [1,2,4]
złożyć
W ten sposób realizowany jest lewy pas. Zauważ, jak kolejność argumentów w funkcji kroku jest odwrócona w porównaniu do foldr
(prawy fold):
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs -- = foldl f (acc `f` x) xs
Lewa fałda, foldl
, kojarzy się z lewą. To jest:
foldl (+) 0 [1, 2, 3] -- is equivalent to ((0 + 1) + 2) + 3
Powodem jest to, że foldl
jest oceniany w ten sposób (spójrz na krok indukcyjny foldl
):
foldl (+) 0 [1, 2, 3] -- foldl (+) 0 [ 1, 2, 3 ]
foldl (+) ((+) 0 1) [2, 3] -- foldl (+) (0 + 1) [ 2, 3 ]
foldl (+) ((+) ((+) 0 1) 2) [3] -- foldl (+) ((0 + 1) + 2) [ 3 ]
foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [] -- foldl (+) (((0 + 1) + 2) + 3) []
((+) ((+) ((+) 0 1) 2) 3) -- (((0 + 1) + 2) + 3)
Ostatnia linia odpowiada ((0 + 1) + 2) + 3
. Wynika to z faktu, że (fab)
jest ogólnie taki sam jak (a `f` b)
, a zatem ((+) 0 1)
jest taki sam, jak w szczególności (0 + 1)
.
foldr
Oto jak realizowany jest prawy fold:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs) -- = x `f` foldr f z xs
Prawy fold, foldr
, kojarzy się z prawym. To jest:
foldr (+) 0 [1, 2, 3] -- is equivalent to 1 + (2 + (3 + 0))
Powodem jest to, że foldr
jest oceniany w ten sposób (spójrz na krok indukcyjny foldr
):
foldr (+) 0 [1, 2, 3] -- foldr (+) 0 [1,2,3]
(+) 1 (foldr (+) 0 [2, 3]) -- 1 + foldr (+) 0 [2,3]
(+) 1 ((+) 2 (foldr (+) 0 [3])) -- 1 + (2 + foldr (+) 0 [3])
(+) 1 ((+) 2 ((+) 3 (foldr (+) 0 []))) -- 1 + (2 + (3 + foldr (+) 0 []))
(+) 1 ((+) 2 ((+) 3 0)) -- 1 + (2 + (3 + 0 ))
Ostatni wiersz odpowiada 1 + (2 + (3 + 0))
, ponieważ ((+) 3 0)
jest taki sam jak (3 + 0)
.
Przekształcanie za pomocą `map`
Często chcemy przekonwertować lub przekształcić zawartość kolekcji (listy lub czegoś, co można przejść). W Haskell używamy map
:
-- Simple add 1
map (+ 1) [1,2,3]
[2,3,4]
map odd [1,2,3]
[True,False,True]
data Gender = Male | Female deriving Show
data Person = Person String Gender Int deriving Show
-- Extract just the age from a list of people
map (\(Person n g a) -> a) [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
[31,29]
Filtrowanie za pomocą „filtra”
Podana lista:
li = [1,2,3,4,5]
możemy filtrować listę z predykatem za pomocą filter :: (a -> Bool) -> [a] -> [a]
:
filter (== 1) li -- [1]
filter (even) li -- [2,4]
filter (odd) li -- [1,3,5]
-- Something slightly more complicated
comfy i = notTooLarge && isEven
where
notTooLarge = (i + 1) < 5
isEven = even i
filter comfy li -- [2]
Oczywiście nie chodzi tylko o liczby:
data Gender = Male | Female deriving Show
data Person = Person String Gender Int deriving Show
onlyLadies :: [Person] -> Person
onlyLadies x = filter isFemale x
where
isFemale (Person _ Female _) = True
isFemale _ = False
onlyLadies [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
-- [Person "Ellie" Female 29]
Zipowanie i rozpakowywanie list
zip bierze dwie listy i zwraca listę odpowiednich par:
zip [] _ = []
zip _ [] = []
zip (a:as) (b:bs) = (a,b) : zip as bs
> zip [1,3,5] [2,4,6]
> [(1,2),(3,4),(5,6)]
Spakowanie dwóch list za pomocą funkcji:
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith (+) [1,3,5] [2,4,6]
> [3,7,11]
Rozpakowywanie listy:
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
> unzip [(1,2),(3,4),(5,6)]
> ([1,3,5],[2,4,6])