Comment puis-je accéder à une liste par index en Haskell, analogue à ce code C?

int a[] = { 34, 45, 56 };
return a[1];

Regardez ici , l'opérateur utilisé est !!.

Ie [1,2,3]!!1vous donne 2, puisque les listes sont indexées à 0.

Je ne dis pas qu'il y a quelque chose de mal avec votre question ou la réponse donnée, mais peut-être que vous aimeriez en savoir plus sur le merveilleux outil qu'est Hoogle pour vous faire gagner du temps à l'avenir: avec Hoogle, vous pouvez rechercher des fonctions de bibliothèque standard qui correspondent à une signature donnée. Donc, sans rien savoir !!, dans votre cas, vous pourriez rechercher "quelque chose qui prend une Intet une liste de tout ce qui est et renvoie un seul tel quel", à savoir

Int -> [a] -> a

Et voilà , avec !!comme premier résultat (bien que la signature de type ait en fait les deux arguments inversés par rapport à ce que nous recherchions). Neat, hein?

De plus, si votre code repose sur l'indexation (au lieu de consommer du début de la liste), les listes peuvent en fait ne pas être la structure de données appropriée. Pour l'accès basé sur l'index O (1), il existe des alternatives plus efficaces, telles que des tableaux ou des vecteurs .

Une alternative à l'utilisation (!!)consiste à utiliser le package de l' objectif et sa elementfonction et les opérateurs associés. La lentille fournit une interface uniforme pour accéder à une grande variété de structures et de structures imbriquées au-dessus et au-delà des listes. Ci-dessous, je me concentrerai sur la fourniture d'exemples et je passerai sous silence à la fois les signatures de type et la théorie derrière le paquet de lentilles . Si vous voulez en savoir plus sur la théorie, un bon point de départ est le fichier readme dans le dépôt github .

Accès aux listes et autres types de données

Accéder à l'ensemble de l'objectif

Sur la ligne de commande:

$ cabal install lens
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
> import Control.Lens

Accéder aux listes

Pour accéder à une liste avec l'opérateur infixe

> [1,2,3,4,5] ^? element 2  -- 0 based indexing
Just 3

Contrairement à (!!)cela, cela ne lèvera pas d'exception lors de l'accès à un élément hors limites et reviendra à la Nothingplace. Il est souvent recommandé d'éviter les fonctions partielles comme (!!)ou headcar elles ont plus de cas d'angle et sont plus susceptibles de provoquer une erreur d'exécution. Vous pouvez en savoir un peu plus sur les raisons d'éviter les fonctions partielles sur cette page wiki .

> [1,2,3] !! 9
*** Exception: Prelude.(!!): index too large

> [1,2,3] ^? element 9
Nothing

Vous pouvez forcer la technique de la lentille à être une fonction partielle et lever une exception en dehors des limites en utilisant l' (^?!)opérateur au lieu de l' (^?)opérateur.

> [1,2,3] ^?! element 1
2
> [1,2,3] ^?! element 9
*** Exception: (^?!): empty Fold

Travailler avec des types autres que des listes

Cela ne se limite cependant pas aux listes. Par exemple, la même technique fonctionne sur les arbres du package de conteneurs standard .

 > import Data.Tree
 > :{
 let
  tree = Node 1 [
       Node 2 [Node 4[], Node 5 []]
     , Node 3 [Node 6 [], Node 7 []]
     ]
 :}
> putStrLn . drawTree . fmap show $tree
1
|
+- 2
|  |
|  +- 4
|  |
|  `- 5
|
`- 3
   |
   +- 6
   |
   `- 7

Nous pouvons maintenant accéder aux éléments de l'arbre dans l'ordre en profondeur:

> tree ^? element 0
Just 1
> tree ^? element 1
Just 2
> tree ^? element 2
Just 4
> tree ^? element 3
Just 5
> tree ^? element 4
Just 3
> tree ^? element 5
Just 6
> tree ^? element 6
Just 7

Nous pouvons également accéder aux séquences depuis le package conteneurs :

> import qualified Data.Sequence as Seq
> Seq.fromList [1,2,3,4] ^? element 3
Just 4

Nous pouvons accéder aux tableaux indexés standard int à partir du package vectoriel , au texte du package texte standard , aux chaînes d' octets du package bytestring standard et à de nombreuses autres structures de données standard. Cette méthode d'accès standard peut être étendue à vos structures de données personnelles en en faisant une instance de la classe de types Taversable , voir une liste plus longue d'exemples de Traversables dans la documentation Lens. .

Structures imbriquées

Creuser dans des structures imbriquées est simple avec le piratage de l'objectif . Par exemple, accéder à un élément dans une liste de listes:

> [[1,2,3],[4,5,6]] ^? element 0 . element 1
Just 2
> [[1,2,3],[4,5,6]] ^? element 1 . element 2
Just 6

Cette composition fonctionne même lorsque les structures de données imbriquées sont de types différents. Donc par exemple si j'avais une liste d'arbres:

> :{
 let
  tree = Node 1 [
       Node 2 []
     , Node 3 []
     ]
 :}
> putStrLn . drawTree . fmap show $ tree
1
|
+- 2
|
`- 3
> :{
 let 
  listOfTrees = [ tree
      , fmap (*2) tree -- All tree elements times 2
      , fmap (*3) tree -- All tree elements times 3
      ]            
 :}

> listOfTrees ^? element 1 . element 0
Just 2
> listOfTrees ^? element 1 . element 1
Just 4

Vous pouvez imbriquer arbitrairement profondément avec des types arbitraires tant qu'ils répondent à l' Traversableexigence. Donc, accéder à une liste d'arbres de séquences de texte n'est pas un problème.

Changer le nième élément

Une opération courante dans de nombreuses langues consiste à attribuer une position indexée dans un tableau. En python, vous pouvez:

>>> a = [1,2,3,4,5]
>>> a[3] = 9
>>> a
[1, 2, 3, 9, 5]

L' ensemble de lentilles confère cette fonctionnalité à l' (.~)opérateur. Bien que contrairement à python, la liste d'origine ne soit pas mutée, une nouvelle liste est renvoyée.

> let a = [1,2,3,4,5]
> a & element 3 .~ 9
[1,2,3,9,5]
> a
[1,2,3,4,5]

element 3 .~ 9est juste une fonction et l' (&)opérateur, qui fait partie de l' ensemble de l' objectif , n'est qu'une application de fonction inverse. Le voici avec l'application de fonction la plus courante.

> (element 3 .~ 9) [1,2,3,4,5]
[1,2,3,9,5]

L'affectation fonctionne à nouveau parfaitement bien avec l'imbrication arbitraire de Traversables.

> [[1,2,3],[4,5,6]] & element 0 . element 1 .~ 9
[[1,9,3],[4,5,6]]

La réponse directe a déjà été donnée: utiliser !!.

Cependant, les débutants ont souvent tendance à abuser de cet opérateur, qui est cher dans Haskell (car vous travaillez sur des listes chaînées uniques, pas sur des tableaux). Il existe plusieurs techniques utiles pour éviter cela, la plus simple est d'utiliser zip. Si vous écrivez zip ["foo","bar","baz"] [0..], vous obtenez une nouvelle liste avec les indices "attachés" à chaque élément d'une paire [("foo",0),("bar",1),("baz",2)]:, ce qui est souvent exactement ce dont vous avez besoin.

Vous pouvez utiliser !!, mais si vous voulez le faire de manière récursive, voici une façon de le faire:

dataAt :: Int -> [a] -> a
dataAt _ [] = error "Empty List!"
dataAt y (x:xs)  | y <= 0 = x
                 | otherwise = dataAt (y-1) xs

Le type de données de liste standard de Haskell forall t. [t]dans l'implémentation ressemble étroitement à une liste chaînée canonique C et partage ses propriétés essentiellement. Les listes liées sont très différentes des tableaux. Plus particulièrement, l'accès par index est une opération O (n) linéaire, au lieu d'une opération à temps constant O (1).

Si vous avez besoin d'un accès aléatoire fréquent, considérez la Data.Arraynorme.

!!est une fonction partiellement définie non sécurisée, provoquant un crash pour les indices hors limites. Sachez que la bibliothèque standard contient certaines de ces fonctions partielles ( head, last, etc.). Pour des raisons de sécurité, utilisez un type d'option Maybeou le Safemodule.

Exemple de fonction d'indexation totale (pour les indices ≥ 0) raisonnablement efficace et robuste:

data Maybe a = Nothing | Just a

lookup :: Int -> [a] -> Maybe a
lookup _ []       = Nothing
lookup 0 (x : _)  = Just x
lookup i (_ : xs) = lookup (i - 1) xs

En travaillant avec des listes liées, les ordinaux sont souvent pratiques:

nth :: Int -> [a] -> Maybe a
nth _ []       = Nothing
nth 1 (x : _)  = Just x
nth n (_ : xs) = nth (n - 1) xs