Haskell Language
listor

Syntax

1. tom lista konstruktör

   [] :: [a]

2. icke-tom listkonstruktör

   (:) :: a -> [a] -> [a]

3. head - returnerar det första värdet på en lista

   head :: [a] -> a

4. last - returnerar det sista värdet på en lista

   last :: [a] -> a

5. tail - returnerar en lista utan den första artikeln

   tail :: [a] -> [a]

6. init - returnerar en lista utan den sista artikeln

   init :: [a] -> [a]

7. xs !! i - returnera elementet vid ett index i i listan xs

   (!!) :: Int -> [a] -> a

8. ta n xs - returnera ny lista som innehåller n första element i listan xs

   take :: Int -> [a] -> [a]

9. karta :: (a -> b) -> [a] -> [b]

10. filter :: (a -> Bool) -> [a] -> [a]

11. (++) :: [a] -> [a]

12. concat :: [[a]] -> [a]

Anmärkningar

Lista bokstäver

emptyList     = []

singletonList = [0]               -- = 0 : []

listOfNums    = [1, 2, 3]         -- = 1 : 2 : [3]

listOfStrings = ["A", "B", "C"]

Lista sammankoppling

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)

Lista grunderna

Typkonstruktören för listor i Haskell Prelude är [] . Typdeklarationen för en lista med värden av typ Int skrivs enligt följande:

xs :: [Int]    -- or equivalently, but less conveniently,
xs :: [] Int

Listor i Haskell är homogena sekvenser , det vill säga att alla element måste vara av samma typ. Till skillnad från tuplingar påverkas listtyp inte av längden:

[1,2,3]   :: [Int]
[1,2,3,4] :: [Int]

Listor är konstruerade med två konstruktörer :

• [] skapar en tom lista.

• (:) , uttalas "nackdelar", beror elementen i en lista. Om du gillar x (ett värde av typ a ) till xs (en lista med värden av samma typ a ) skapas en ny lista, vars huvud (det första elementet) är x , och svansen (resten av elementen) är xs .

Vi kan definiera enkla listor enligt följande:

ys :: [a]
ys = []

xs :: [Int]
xs = 12 : (99 : (37 : []))   
-- or  = 12 : 99 : 37 : []     -- ((:) is right-associative)
-- or  = [12, 99, 37]          -- (syntactic sugar for lists)

Observera att (++) , som kan användas för att bygga listor definieras rekursivt i termer av (:) och [] .

Behandlar listor

För att bearbeta listor kan vi helt enkelt mönstermatchning på konstruktörerna av listtypen:

listSum :: [Int] -> Int
listSum []          = 0
listSum (x:xs) = x + listSum xs

Vi kan matcha fler värden genom att ange ett mer detaljerat mönster:

sumTwoPer :: [Int] -> Int
sumTwoPer [] = 0
sumTwoPer (x1:x2:xs) = x1 + x2 + sumTwoPer xs
sumTwoPer (x:xs) = x + sumTwoPer xs

Observera att i exemplet ovan var vi tvungna att tillhandahålla en mer uttömmande mönstermatchning för att hantera fall där en udda längdlista ges som ett argument.

Haskell Prelude definierar många inbyggda för hanteringslistor, som map , filter osv. Om möjligt bör du använda dessa istället för att skriva dina egna rekursiva funktioner.

Få åtkomst till element i listor

Öppna det n: a elementet i en lista (nollbaserat):

list = [1 .. 10]

firstElement = list !! 0           -- 1

Observera att !! är en partiell funktion, så vissa ingångar ger fel:

list !! (-1)     -- *** Exception: Prelude.!!: negative index  

list !! 1000     -- *** Exception: Prelude.!!: index too large

Det finns också Data.List.genericIndex , en överbelastad version av !! , som accepterar alla Integral värden som index.

import Data.List (genericIndex)

list `genericIndex` 4              -- 5

När de genomförs som enskilda länkade listor tar dessa operationer O (n) tid. Om du ofta tillgång element med index, är det förmodligen bättre att använda Data.Vector (från vektorpaketet) eller andra datastrukturer.

Ranges

Att skapa en lista från 1 till 10 är enkelt att använda intervallnotation:

[1..10]    -- [1,2,3,4,5,6,7,8,9,10]

För att ange ett steg, lägg till ett komma och nästa element efter startelementet:

[1,3..10]  -- [1,3,5,7,9]

Observera att Haskell alltid tar steget som den aritmetiska skillnaden mellan termer och att du inte kan specificera mer än de två första elementen och den övre gränsen:

[1,3,5..10] -- error
[1,3,9..20] -- error

För att generera ett intervall i fallande ordning anger du alltid det negativa steget:

[5..1]     -- []

[5,4..1]   -- [5,4,3,2,1]

Eftersom Haskell inte är strikt utvärderas elementen i listan endast om de behövs, vilket gör att vi kan använda oändliga listor. [1..] är en oändlig lista som börjar från 1. Denna lista kan vara bunden till en variabel eller skickas som ett funktionsargument:

take 5 [1..]   -- returns [1,2,3,4,5] even though [1..] is infinite

Var försiktig när du använder områden med flytande punktvärden, eftersom det accepterar överbelastningar upp till halvdelta för att avskärma avrundningsproblem:

[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

Områden fungerar inte bara med siffror utan med vilken typ som helst som implementerar Enum typklass. Med tanke på en mängd variabler a , b , c , är intervallsyntaxen likvärdig med att kalla dessa Enum metoder:

[a..]    == enumFrom a
[a..c]   == enumFromTo a c
[a,b..]  == enumFromThen a b
[a,b..c] == enumFromThenTo a b c

Till exempel med Bool det

 [False ..]      -- [False,True]

Lägg märke till utrymmet efter False , för att förhindra att detta tolkas som en modulnamnkvalifikation (dvs. False.. skulle tolkas som . Från en modul False ).

Grundläggande funktioner på listor

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

Så implementeras den vänstra vikningen. Lägg märke till hur ordningen på argumenten i stegfunktionen vänds jämfört med foldr (den högra vikten):

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  

Vänster vikning, foldl , associerar till vänster. Det är:

foldl (+) 0 [1, 2, 3]     -- is equivalent to ((0 + 1) + 2) + 3

Anledningen är att foldl utvärderas så här (titta på foldl induktiva steg):

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)

Den sista raden motsvarar ((0 + 1) + 2) + 3 . Detta beror på att (fab) är densamma som (a `f` b) i allmänhet, och ((+) 0 1) är desamma som (0 + 1) i synnerhet.

foldr

Så här implementeras den rätta vikningen:

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

Den högra vikningen, foldr , associerar till höger. Det är:

foldr (+) 0 [1, 2, 3]      -- is equivalent to 1 + (2 + (3 + 0))

Anledningen är att foldr utvärderas så här (titta på det induktiva steget för 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   ))

Den sista raden motsvarar 1 + (2 + (3 + 0)) , eftersom ((+) 3 0) är densamma som (3 + 0) .

Transformering med "karta"

Ofta vill vi konvertera eller omvandla innehållet i en samling (en lista eller något som går igenom). I Haskell använder vi 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]

Filtrering med "filter"

Får en lista:

 li = [1,2,3,4,5]

vi kan filtrera en lista med ett predikat med 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]

Naturligtvis handlar det inte bara om siffror:

 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]

Zippa och lossa listor

zip tar två listor och returnerar en lista med motsvarande 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)]

Zippa två listor med en funktion:

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]

Lossa upp en lista:

unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

> unzip [(1,2),(3,4),(5,6)]
> ([1,3,5],[2,4,6])