Haskell Language
elenchi
Ricerca…
Sintassi
costruttore di liste vuote
[] :: [a]
costruttore di liste non vuote
(:) :: a -> [a] -> [a]
head - restituisce il primo valore di una lista
head :: [a] -> a
last - restituisce l'ultimo valore di una lista
last :: [a] -> a
tail - restituisce una lista senza il primo elemento
tail :: [a] -> [a]
init - restituisce una lista senza l'ultimo elemento
init :: [a] -> [a]
xs !! i - restituisce l'elemento in un indice i nella lista xs
(!!) :: Int -> [a] -> a
take n xs - restituisce una nuova lista contenente n primi elementi della lista xs
take :: Int -> [a] -> [a]
mappa :: (a -> b) -> [a] -> [b]
filtro :: (a -> Bool) -> [a] -> [a]
(++) :: [a] -> [a]
concat :: [[a]] -> [a]
Osservazioni
- Il tipo
[a]
è equivalente a[] a
. -
[]
costruisce la lista vuota. -
[]
in una definizione di funzione LHS, ad es.f [] = ...
, è il modello di lista vuoto. -
x:xs
costruisce una lista in cui un elementox
è anteposto alla listaxs
-
f (x:xs) = ...
è una corrispondenza di modello per una lista non vuota dovex
è la testa exs
è la coda. -
f (a:b:cs) = ...
ef (a:(b:cs)) = ...
sono gli stessi. Sono una corrispondenza di modello per un elenco di almeno due elementi in cui il primo elemento èa
, il secondo elemento èb
e il resto dell'elenco ècs
. -
f ((a:as):bs) = ...
NON è uguale af (a:(as:bs)) = ...
Il primo è un pattern match per una lista non vuota di liste, dovea
è la testa della testa,as
è la coda della testa, ebs
è la coda. -
f (x:[]) = ...
ef [x] = ...
sono gli stessi. Sono una corrispondenza di modello per un elenco di esattamente un elemento. -
f (a:b:[]) = ...
ef [a,b] = ...
sono gli stessi. Sono una corrispondenza di modello per un elenco di esattamente due elementi. -
f [a:b] = ...
è una corrispondenza di modello per un elenco di esattamente un elemento in cui l'elemento è anche un elenco.a
è la testa dell'elemento eb
è la coda dell'elemento. -
[a,b,c]
è uguale a(a:b:c:[])
. La notazione elenco standard è solo zucchero sintattico per i costruttori(:)
e[]
. - Puoi usare
all@(x:y:ys)
per fare riferimento all'intera lista comeall
(o qualsiasi altro nome che scegli) invece di ripetere(x:y:ys)
nuovo.
Elenca i letterali
emptyList = []
singletonList = [0] -- = 0 : []
listOfNums = [1, 2, 3] -- = 1 : 2 : [3]
listOfStrings = ["A", "B", "C"]
Elenco di concatenazione
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)
Elenco delle nozioni di base
Il costruttore di tipi per gli elenchi nel Preludio Haskell è []
. La dichiarazione del tipo per un elenco contenente i valori di tipo Int
è scritta come segue:
xs :: [Int] -- or equivalently, but less conveniently,
xs :: [] Int
Le liste in Haskell sono sequenze omogenee , vale a dire che tutti gli elementi devono essere dello stesso tipo. A differenza delle tuple, il tipo di lista non è influenzato dalla lunghezza:
[1,2,3] :: [Int]
[1,2,3,4] :: [Int]
Le liste sono costruite usando due costruttori :
[]
costruisce una lista vuota.(:)
, pronunciato "contro", antepone gli elementi a un elenco. Consingx
(un valore di tipoa
) suxs
(un elenco di valori dello stesso tipoa
) crea una nuova lista, la cui testa (il primo elemento) èx
, e tail (il resto degli elementi) èxs
.
Possiamo definire semplici elenchi come segue:
ys :: [a]
ys = []
xs :: [Int]
xs = 12 : (99 : (37 : []))
-- or = 12 : 99 : 37 : [] -- ((:) is right-associative)
-- or = [12, 99, 37] -- (syntactic sugar for lists)
Nota che (++)
, che può essere usato per costruire liste, è definito ricorsivamente in termini di (:)
e []
.
Liste di elaborazione
Per elaborare gli elenchi, possiamo semplicemente creare una corrispondenza dei modelli sui costruttori del tipo di lista:
listSum :: [Int] -> Int
listSum [] = 0
listSum (x:xs) = x + listSum xs
Possiamo abbinare più valori specificando un modello più elaborato:
sumTwoPer :: [Int] -> Int
sumTwoPer [] = 0
sumTwoPer (x1:x2:xs) = x1 + x2 + sumTwoPer xs
sumTwoPer (x:xs) = x + sumTwoPer xs
Si noti che nell'esempio precedente, abbiamo dovuto fornire una corrispondenza di modello più esauriente per gestire i casi in cui una lista di lunghezza dispari viene fornita come argomento.
Haskell Prelude definisce molti built-in per la gestione di liste, come map
, filter
, ecc. Dove possibile, dovresti usarli invece di scrivere le tue funzioni ricorsive.
Accedere agli elementi negli elenchi
Accedi al n ° elemento di una lista (a base zero):
list = [1 .. 10]
firstElement = list !! 0 -- 1
Nota che !!
è una funzione parziale, quindi alcuni input producono errori:
list !! (-1) -- *** Exception: Prelude.!!: negative index
list !! 1000 -- *** Exception: Prelude.!!: index too large
C'è anche Data.List.genericIndex
, una versione sovraccaricata di !!
, che accetta qualsiasi valore Integral
come indice.
import Data.List (genericIndex)
list `genericIndex` 4 -- 5
Se implementate come liste a collegamento singolo, queste operazioni richiedono O (n) tempo. Se frequenti gli elementi per indice, probabilmente è meglio usare Data.Vector
(dal pacchetto vettoriale ) o altre strutture dati.
Intervalli
Creare una lista da 1 a 10 è semplice usando la notazione degli intervalli:
[1..10] -- [1,2,3,4,5,6,7,8,9,10]
Per specificare un passaggio, aggiungi una virgola e l'elemento successivo dopo l'elemento iniziale:
[1,3..10] -- [1,3,5,7,9]
Nota che Haskell prende sempre il passo come la differenza aritmetica tra i termini e che non puoi specificare più dei primi due elementi e del limite superiore:
[1,3,5..10] -- error
[1,3,9..20] -- error
Per generare un intervallo in ordine decrescente, specificare sempre il passaggio negativo:
[5..1] -- []
[5,4..1] -- [5,4,3,2,1]
Poiché Haskell non è severo, gli elementi dell'elenco vengono valutati solo se sono necessari, il che ci consente di utilizzare elenchi infiniti. [1..]
è una lista infinita a partire da 1. Questo elenco può essere associato a una variabile o passato come argomento di funzione:
take 5 [1..] -- returns [1,2,3,4,5] even though [1..] is infinite
Fai attenzione quando utilizzi intervalli con valori a virgola mobile, perché accetta effetti di transizione fino a metà delta, per evitare problemi di arrotondamento:
[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
Le gamme funzionano non solo con i numeri ma con qualsiasi tipo che implementa la classe di caratteri Enum
. Date alcune variabili enumerabili a
, b
, c
, la sintassi dell'intervallo equivale a chiamare questi metodi Enum
:
[a..] == enumFrom a
[a..c] == enumFromTo a c
[a,b..] == enumFromThen a b
[a,b..c] == enumFromThenTo a b c
Ad esempio, con Bool
è
[False ..] -- [False,True]
Si noti lo spazio dopo False
, per evitare che questo deve essere analizzato come una qualifica nome del modulo (ossia False..
sarebbe stato analizzato come .
Da un modulo False
).
Funzioni di base sugli elenchi
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]
foldl
Ecco come viene implementata la piega sinistra. Notare come l'ordine degli argomenti nella funzione di passo viene invertito rispetto a foldr
(la piega a destra):
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
La piega a sinistra, foldl
, associa a sinistra. Questo è:
foldl (+) 0 [1, 2, 3] -- is equivalent to ((0 + 1) + 2) + 3
Il motivo è che foldl
viene valutato in questo modo (guarda il passo induttivo di 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)
L'ultima riga è equivalente a ((0 + 1) + 2) + 3
. Questo perché (fab)
è lo stesso di (a `f` b)
in generale, e quindi ((+) 0 1)
è lo stesso di (0 + 1)
in particolare.
foldr
Ecco come viene implementata la piega giusta:
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
La piega a destra, foldr
, associa a destra. Questo è:
foldr (+) 0 [1, 2, 3] -- is equivalent to 1 + (2 + (3 + 0))
Il motivo è che foldr
viene valutato in questo modo (guarda il passo induttivo di 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 ))
L'ultima riga è equivalente a 1 + (2 + (3 + 0))
, perché ((+) 3 0)
è uguale a (3 + 0)
.
Trasformando con `map`
Spesso desideriamo convertire o trasformare i contenuti di una collezione (una lista o qualcosa di attraversabile). In Haskell usiamo la 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]
Filtro con `filtro`
Dato un elenco:
li = [1,2,3,4,5]
possiamo filtrare una lista con un predicato usando 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]
Ovviamente non si tratta solo di numeri:
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]
Elenchi zippati e decompressi
zip prende due liste e restituisce una lista di coppie corrispondenti:
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)]
Zippare due liste con una funzione:
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]
Decompressione di un elenco:
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
> unzip [(1,2),(3,4),(5,6)]
> ([1,3,5],[2,4,6])