Haskell Language
lijsten

Syntaxis

1. lege lijstconstructor

   [] :: [a]

2. niet-lege lijstconstructor

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

3. head - retourneert de eerste waarde van een lijst

   head :: [a] -> a

4. last - retourneert de laatste waarde van een lijst

   last :: [a] -> a

5. staart - geeft een lijst terug zonder het eerste item

   tail :: [a] -> [a]

6. init - retourneert een lijst zonder het laatste item

   init :: [a] -> [a]

7. xs !! i - geef het element terug in een index i in lijst xs

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

8. neem n xs - retourneer een nieuwe lijst met n eerste elementen van de lijst xs

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

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

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

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

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

Opmerkingen

Lijst met literatuur

emptyList     = []

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

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

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

Lijstaaneenschakeling

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)

Lijst basics

De typeconstructeur voor lijsten in de Haskell Prelude is [] . De typeaangifte voor een lijst met waarden van type Int is als volgt geschreven:

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

Lijsten in Haskell zijn homogene reeksen , dat wil zeggen dat alle elementen van hetzelfde type moeten zijn. In tegenstelling tot tupels, wordt het lijsttype niet beïnvloed door lengte:

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

Lijsten worden samengesteld met behulp van twee constructors :

• [] een lege lijst.

• (:) , uitgesproken als "nadelen", voegt elementen toe aan een lijst. Door x (een waarde van type a ) op xs tellen (een lijst met waarden van hetzelfde type a ) wordt een nieuwe lijst gemaakt, waarvan het hoofd (het eerste element) x is en de staart (de rest van de elementen) xs .

We kunnen eenvoudige lijsten als volgt definiëren:

ys :: [a]
ys = []

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

Merk op dat (++) , dat kan worden gebruikt om lijsten samen te stellen, recursief wordt gedefinieerd in termen van (:) en [] .

Lijsten verwerken

Om lijsten te verwerken, kunnen we eenvoudig patroonovereenkomst maken op de constructors van het lijsttype:

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

We kunnen meer waarden matchen door een uitgebreider patroon op te geven:

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

Merk op dat we in het bovenstaande voorbeeld een uitputtende patroonovereenkomst moesten bieden om gevallen te behandelen waarin een oneven lengtelijst als argument wordt gegeven.

De Haskell Prelude definieert vele ingebouwde ins voor het verwerken van lijsten, zoals map , filter , enz .. Waar mogelijk, zou u deze moeten gebruiken in plaats van uw eigen recursieve functies te schrijven.

Toegang tot elementen in lijsten

Toegang tot het n de element van een lijst (op nul gebaseerd):

list = [1 .. 10]

firstElement = list !! 0           -- 1

Merk op dat !! is een gedeeltelijke functie, dus bepaalde ingangen produceren fouten:

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

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

Er is ook Data.List.genericIndex , een overbelaste versie van !! , die elke Integral waarde als index accepteert.

import Data.List (genericIndex)

list `genericIndex` 4              -- 5

Wanneer geïmplementeerd als afzonderlijk gekoppelde lijsten, nemen deze bewerkingen O (n) tijd in beslag. Als u vaak toegang hebt tot elementen per index, is het waarschijnlijk beter om Data.Vector (uit het vectorpakket ) of andere gegevensstructuren te gebruiken.

ranges

Het maken van een lijst van 1 tot 10 is eenvoudig met behulp van bereiknotatie:

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

Om een stap op te geven, voegt u een komma en het volgende element toe na het startelement:

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

Merk op dat Haskell altijd de stap neemt als het rekenkundige verschil tussen termen, en dat u niet meer dan de eerste twee elementen en de bovengrens kunt opgeven:

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

Geef altijd de negatieve stap op om een bereik in aflopende volgorde te genereren:

[5..1]     -- []

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

Omdat Haskell niet-streng is, worden de elementen van de lijst alleen geëvalueerd als ze nodig zijn, waardoor we oneindige lijsten kunnen gebruiken. [1..] is een oneindige lijst beginnend bij 1. Deze lijst kan worden gekoppeld aan een variabele of worden doorgegeven als functieargument:

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

Wees voorzichtig bij het gebruik van bereiken met drijvende-kommawaarden, omdat het overloop tot halfdelta accepteert, om afrondingsproblemen te voorkomen:

[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

Bereiken werken niet alleen met getallen, maar met elk type dat Enum typeclass implementeert. Gegeven enkele opsombare variabelen a , b , c , is de syntaxis van het bereik gelijk aan het aanroepen van deze Enum methoden:

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

Met Bool bijvoorbeeld

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

Let op de spatie na False , om te voorkomen dat deze wordt ontleed als een kwalificatienaam van een module (dwz False.. zou worden ontleed als . Van een module False ).

Basisfuncties op lijsten

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

Dit is hoe de linker vouw wordt geïmplementeerd. Merk op hoe de volgorde van de argumenten in de stapfunctie wordt omgedraaid vergeleken met foldr (de juiste vouw):

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  

Links vouwen, foldl , associeert naar links. Dat is:

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

De reden is dat foldl wordt geëvalueerd (kijk naar de inductieve stap van 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)

De laatste regel is gelijk aan ((0 + 1) + 2) + 3 . Dit komt omdat (fab) hetzelfde is als (a `f` b) in het algemeen, en dus ((+) 0 1) is hetzelfde als (0 + 1) in het bijzonder.

foldr

Dit is hoe de juiste vouw wordt geïmplementeerd:

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

Rechts vouwen, foldr , naar rechts associeert. Dat is:

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

De reden is dat foldr wordt geëvalueerd (kijk naar de inductieve stap van 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   ))

De laatste regel is gelijk aan 1 + (2 + (3 + 0)) , omdat ((+) 3 0) hetzelfde is als (3 + 0) .

Transformeren met `map`

Vaak willen we de inhoud van een verzameling (een lijst of iets dat verhandelbaar is) converteren of transformeren. In Haskell gebruiken we 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]

Filteren met `filter`

Een lijst gegeven:

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

we kunnen een lijst filteren met een predikaat met behulp van 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]

Natuurlijk gaat het niet alleen om cijfers:

 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]

Lippende en uitgepakte lijsten

zip neemt twee lijsten en retourneert een lijst met overeenkomstige paren:

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)]

Twee lijsten met een functie ritsen:

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]

Een lijst uitpakken:

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

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