Haskell Language
Des listes

Syntaxe

1. constructeur de liste vide

   [] :: [a]

2. constructeur de liste non vide

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

3. head - renvoie la première valeur d'une liste

   head :: [a] -> a

4. last - renvoie la dernière valeur d'une liste

   last :: [a] -> a

5. tail - renvoie une liste sans le premier élément

   tail :: [a] -> [a]

6. init - renvoie une liste sans le dernier élément

   init :: [a] -> [a]

7. xs !! i - renvoie l'élément à un index i dans la liste xs

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

8. take n xs - retourne une nouvelle liste contenant n premiers éléments de la liste xs

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

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

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

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

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

Remarques

Liste des littéraux

emptyList     = []

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

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

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

Concaténation de liste

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)

Liste des bases

Le constructeur de type pour les listes dans le Prelude Haskell est [] . La déclaration de type pour une liste contenant des valeurs de type Int est écrite comme suit:

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

Les listes dans Haskell sont des séquences homogènes , c'est-à-dire que tous les éléments doivent être du même type. Contrairement aux tuples, le type de liste n’est pas affecté par la longueur:

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

Les listes sont construites en utilisant deux constructeurs :

• [] construit une liste vide.

• (:) , prononcé "contre", ajoute des éléments à une liste. Conserver x (une valeur de type a ) sur xs (une liste de valeurs du même type a ) crée une nouvelle liste dont la tête (le premier élément) est x et tail (le reste des éléments) est xs .

Nous pouvons définir des listes simples comme suit:

ys :: [a]
ys = []

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

Notez que (++) , qui peut être utilisé pour construire des listes, est défini récursivement en termes de (:) et [] .

Listes de traitement

Pour traiter des listes, nous pouvons simplement créer des correspondances sur les constructeurs du type liste:

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

Nous pouvons faire correspondre plus de valeurs en spécifiant un modèle plus élaboré:

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

Notez que dans l'exemple ci-dessus, nous avons dû fournir une correspondance de modèle plus exhaustive pour gérer les cas où une liste de longueurs impaires est donnée en argument.

Le Prelude Haskell définit de nombreux éléments intégrés pour gérer les listes, comme map , filter , etc. Dans la mesure du possible, vous devriez les utiliser au lieu d'écrire vos propres fonctions récursives.

Accéder aux éléments dans les listes

Accéder à la n - ième élément d'une liste (base zéro):

list = [1 .. 10]

firstElement = list !! 0           -- 1

Notez que !! est une fonction partielle, de sorte que certaines entrées produisent des erreurs:

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

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

Il y a aussi Data.List.genericIndex , une version surchargée de !! , qui accepte toute valeur Integral comme index.

import Data.List (genericIndex)

list `genericIndex` 4              -- 5

Lorsqu'elles sont implémentées sous forme de listes à liens uniques, ces opérations prennent du temps O (n) . Si vous accédez fréquemment à des éléments par index, il est probablement préférable d'utiliser Data.Vector (à partir du package vectoriel ) ou d'autres structures de données.

Gammes

Créer une liste de 1 à 10 est simple en utilisant la notation par intervalle:

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

Pour spécifier une étape, ajoutez une virgule et l'élément suivant après l'élément start:

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

Notez que Haskell prend toujours le pas comme différence arithmétique entre les termes et que vous ne pouvez pas spécifier plus que les deux premiers éléments et la limite supérieure:

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

Pour générer une plage dans l'ordre décroissant, spécifiez toujours l'étape négative:

[5..1]     -- []

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

Comme Haskell est non strict, les éléments de la liste ne sont évalués que s’ils sont nécessaires, ce qui nous permet d’utiliser des listes infinies. [1..] est une liste infinie à partir de 1. Cette liste peut être liée à une variable ou passée en argument de fonction:

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

Soyez prudent lorsque vous utilisez des plages avec des valeurs à virgule flottante, car il accepte les retombées jusqu'à la moitié du delta, pour éviter les problèmes d'arrondi:

[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

Les plages ne fonctionnent pas uniquement avec des nombres mais avec n'importe quel type qui implémente la classe Enum . Étant donné certaines variables énumérables a , b , c , la syntaxe de la plage est équivalente à l'appel de ces méthodes Enum :

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

Par exemple, avec Bool c'est

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

Notez l'espace après False , pour éviter que cela soit analysé comme une qualification de nom du module (c. -à- False.. serait analysé comme . D'un module False ).

Fonctions de base sur les listes

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]

plier

C'est comme ça que le pli gauche est implémenté. Notez que l'ordre des arguments dans la fonction step est foldr par rapport à foldr (le pli droit):

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  

Le pli gauche, foldl , s'associe à gauche. C'est:

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

La raison en est que foldl est évalué comme ça (regardez le pas inductif de 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)

La dernière ligne est équivalente à ((0 + 1) + 2) + 3 . C'est parce que (fab) est identique à (a `f` b) en général, et donc ((+) 0 1) est le même que (0 + 1) en particulier.

foldr

Voici comment le bon pli est mis en œuvre:

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

Le bon pli, foldr , s'associe à droite. C'est:

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

La raison en est que foldr est évalué comme ça (regardez le pas inductif de 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   ))

La dernière ligne est équivalente à 1 + (2 + (3 + 0)) , car ((+) 3 0) est identique à (3 + 0) .

Transformer avec `map`

Nous souhaitons souvent convertir ou transformer le contenu d'une collection (une liste ou quelque chose pouvant être traversé). Dans Haskell, nous utilisons 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]

Filtrage avec `filter`

Donné une liste:

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

nous pouvons filtrer une liste avec un prédicat utilisant 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]

Bien sûr, il n'y a pas que des chiffres:

 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]

Listes de décompression et de décompression

zip prend deux listes et renvoie une liste de paires correspondantes:

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

Compacter deux listes avec une fonction:

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]

Décompression d'une liste:

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

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