haskell - tres - ¿Cómo puedo obtener el n-ésimo elemento de una lista?

rotacion de listas en haskell

Question

¿Cómo puedo acceder a una lista por índice en Haskell, análogo a este código C?

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

Answer 1

El tipo de datos de lista estándar de Haskell para todos forall t. [t] forall t. [t] en la implementación se parece mucho a una lista canónica de enlaces C, y comparte sus propiedades esencialmente. Las listas vinculadas son muy diferentes de las matrices. En particular, el acceso por índice es una operación O (n) lineal, en lugar de O (1) de tiempo constante.

Si necesita acceso aleatorio frecuente, considere el estándar Data.Array .

!! es una función insegura parcialmente definida, lo que provoca un colapso de los índices fuera de rango. Tenga en cuenta que la biblioteca estándar contiene algunas funciones parciales ( head , last , etc.). Para mayor seguridad, use un tipo de opción Maybe o el módulo Safe .

Ejemplo de una función de indexación razonablemente eficaz, robusta (para índices ≥ 0):

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

Trabajando con listas enlazadas, a menudo los ordinales son convenientes:

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

Answer 2

La respuesta directa ya fue dada: !! Use !! .

Sin embargo, los novatos a menudo tienden a abusar de este operador, que es caro en Haskell (porque trabajas en listas vinculadas individuales, no en matrices). Hay varias técnicas útiles para evitar esto, la más fácil es usar zip. Si escribe zip ["foo","bar","baz"] [0..] , obtiene una nueva lista con los índices "adjuntos" a cada elemento de un par: [("foo",0),("bar",1),("baz",2)] , que a menudo es exactamente lo que necesita.

Answer 3

Mira here , operador !! .

Es decir, [1,2,3]!!1 le da 2 , ya que las listas están indexadas en 0.

Answer 4

No estoy diciendo que su pregunta o la respuesta sean incorrectas, pero tal vez le gustaría saber sobre la maravillosa herramienta que es Hoogle para ahorrarse tiempo en el futuro: con Hoogle, puede buscar funciones de biblioteca estándar que coinciden con una firma determinada. ¡Entonces, sin saber nada !! , en su caso, podría buscar "algo que tome una Int y una lista de elementos que regresen una y tal como sea", es decir,

Int -> [a] -> a

Lo y behold , con !! como el primer resultado (aunque la firma de tipo en realidad tiene los dos argumentos en reversa en comparación con lo que buscamos). Limpio, ¿eh?

Además, si su código se basa en la indexación (en lugar de consumir desde el principio de la lista), las listas pueden no ser la estructura de datos adecuada. Para O (1) acceso basado en índices hay alternativas más eficientes, como arrays o vectors .

Answer 5

Puedes usar !! , pero si quieres hacerlo de manera recursiva, a continuación hay una forma de hacerlo:

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

Answer 6

Una alternativa al uso (!!) es usar el paquete de lens y su función de element y operadores asociados. La lens proporciona una interfaz uniforme para acceder a una amplia variedad de estructuras y estructuras anidadas más allá de las listas. A continuación me centraré en proporcionar ejemplos y pasaré por alto las firmas de tipo y la teoría detrás del paquete de lens . Si desea saber más sobre la teoría, un buen lugar para comenzar es el archivo léame en el repositorio github .

Acceder a listas y otros tipos de datos

Obtener acceso al paquete de lentes

En la línea de comando:

$ 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

Accediendo a las listas

Para acceder a una lista con el operador infijo

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

A diferencia del (!!) esto no arrojará una excepción al acceder a un elemento fuera de límites y devolverá Nothing lugar. A menudo se recomienda evitar funciones parciales como (!!) o head ya que tienen más casos de esquina y es más probable que causen un error de tiempo de ejecución. Puede leer un poco más sobre por qué para evitar funciones parciales en esta página wiki .

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

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

Puede forzar la técnica de la lente para que sea una función parcial y lanzar una excepción cuando esté fuera de límites utilizando el operador (^?!) lugar del operador (^?) .

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

Trabajar con tipos distintos de listas

Sin embargo, esto no solo se limita a las listas. Por ejemplo, la misma técnica funciona en trees del paquete de containers estándar.

 > 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

Ahora podemos acceder a los elementos del árbol en primer orden:

> 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

También podemos acceder a las sequences del paquete de containers :

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

Podemos acceder a las matrices indexadas int estándar del paquete vectors , al texto del paquete de text estándar, a las cadenas de bytestring paquete de bytestring estándar y a muchas otras estructuras de datos estándar. Este método estándar de acceso se puede extender a sus estructuras de datos personales convirtiéndolos en una instancia de la clase de tipos Taversable , consulte una lista más larga de ejemplos de Traversables en la documentación de Lens. .

Estructuras anidadas

Cavar en estructuras anidadas es simple con el hackage de lentes. Por ejemplo, acceder a un elemento en una lista de listas:

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

Esta composición funciona incluso cuando las estructuras de datos anidados son de diferentes tipos. Entonces, por ejemplo, si tuviera una lista de árboles:

> :{
 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

Puede anidar arbitrariamente profundamente con tipos arbitrarios siempre que cumplan con el requisito de Traversable . Así que acceder a una lista de árboles de secuencias de texto no es sudar.

Cambiar el enésimo elemento

Una operación común en muchos idiomas es asignar a una posición indexada en una matriz. En python puedes:

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

El paquete de lens brinda esta funcionalidad con el operador (.~) . Aunque a diferencia de Python, la lista original no está mutada, más bien se devuelve una nueva lista.

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

element 3 .~ 9 es solo una función y el operador (&) , parte del paquete de lens , es solo aplicación de función inversa. Aquí está con la aplicación de función más común.

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

La asignación nuevamente funciona perfectamente bien con el anidamiento arbitrario de Traversable s.

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