Haskell Language
Liza

Sintaxis

1. constructor de lista vacía

   [] :: [a]

2. constructor de listas no vacías

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

3. head - devuelve el primer valor de una lista

   head :: [a] -> a

4. last - devuelve el último valor de una lista

   last :: [a] -> a

5. cola - devuelve una lista sin el primer elemento

   tail :: [a] -> [a]

6. init - devuelve una lista sin el último elemento

   init :: [a] -> [a]

7. xs !! i - devuelve el elemento en un índice i en la lista xs

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

8. take n xs - devuelve una nueva lista que contiene n primeros elementos de la lista xs

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

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

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

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

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

Observaciones

Lista de literales

emptyList     = []

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

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

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

Concatenación de listas

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)

Conceptos básicos de la lista

El constructor de tipos para listas en el preludio de Haskell es [] . La declaración de tipo para una lista que contiene valores de tipo Int se escribe de la siguiente manera:

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

Las listas en Haskell son secuencias homogéneas , es decir, todos los elementos deben ser del mismo tipo. A diferencia de las tuplas, el tipo de lista no se ve afectado por la longitud:

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

Las listas se construyen utilizando dos constructores :

• [] construye una lista vacía.

• (:) , pronunciado "contras", antepone elementos a una lista. Al considerar x (un valor de tipo a ) sobre xs (una lista de valores del mismo tipo a ) se crea una nueva lista, cuya cabecera (el primer elemento) es x , y la cola (el resto de los elementos) es xs .

Podemos definir listas simples de la siguiente manera:

ys :: [a]
ys = []

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

Tenga en cuenta que (++) , que puede usarse para crear listas, se define recursivamente en términos de (:) y [] .

Procesando listas

Para procesar las listas, simplemente podemos hacer un patrón de coincidencia en los constructores del tipo de lista:

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

Podemos hacer coincidir más valores especificando un patrón más elaborado:

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

Tenga en cuenta que en el ejemplo anterior, tuvimos que proporcionar una coincidencia de patrón más exhaustiva para manejar los casos en los que se proporciona una lista de longitud impar como argumento.

Haskell Prelude define muchos elementos incorporados para el manejo de listas, como map , filter , etc. Siempre que sea posible, debe usarlos en lugar de escribir sus propias funciones recursivas.

Accediendo a elementos en listas

Acceda al elemento n th de una lista (basado en cero):

list = [1 .. 10]

firstElement = list !! 0           -- 1

Tenga en cuenta que !! Es una función parcial, por lo que ciertas entradas producen errores:

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

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

También hay Data.List.genericIndex , una versión sobrecargada de !! , que acepta cualquier valor Integral como índice.

import Data.List (genericIndex)

list `genericIndex` 4              -- 5

Cuando se implementan como listas enlazadas individualmente, estas operaciones llevan tiempo O (n) . Si accede con frecuencia a los elementos por índice, probablemente sea mejor usar Data.Vector (del paquete vectorial ) u otras estructuras de datos.

Gamas

Crear una lista del 1 al 10 es simple usando la notación de rango:

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

Para especificar un paso, agregue una coma y el siguiente elemento después del elemento de inicio:

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

Tenga en cuenta que Haskell siempre toma el paso como la diferencia aritmética entre términos, y que no puede especificar más que los primeros dos elementos y el límite superior:

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

Para generar un rango en orden descendente, especifique siempre el paso negativo:

[5..1]     -- []

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

Debido a que Haskell no es estricto, los elementos de la lista se evalúan solo si son necesarios, lo que nos permite utilizar listas infinitas. [1..] es una lista infinita que comienza desde 1. Esta lista se puede vincular a una variable o pasar como un argumento de función:

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

Tenga cuidado al usar rangos con valores de punto flotante, ya que acepta derrames hasta la mitad delta, para evitar los problemas de redondeo:

[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

Los rangos no solo funcionan con números, sino con cualquier tipo que implemente Enum typeclass. Dadas algunas variables enumerables a , b , c , la sintaxis del rango es equivalente a llamar a estos métodos Enum :

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

Por ejemplo, con Bool es

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

Observe el espacio después de False , para evitar que esto se analiza como un nombre de módulo de clasificación (es decir False.. se analiza como . Desde un módulo False ).

Funciones básicas en listas

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]

pliegue

Así es como se implementa el pliegue izquierdo. Observe cómo el orden de los argumentos en la función de paso se invierte en comparación con foldr (el pliegue derecho):

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  

El pliegue izquierdo, foldl , se asocia a la izquierda. Es decir:

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

La razón es que foldl se evalúa de esta manera (mire el paso inductivo 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 última línea es equivalente a ((0 + 1) + 2) + 3 . Esto se debe a que (fab) es lo mismo que (a `f` b) en general, y por lo tanto ((+) 0 1) es lo mismo que (0 + 1) en particular.

plegar

Así es como se implementa el pliegue correcto:

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

El pliegue derecho, foldr , se asocia a la derecha. Es decir:

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

La razón es que foldr se evalúa de esta manera (observe el paso inductivo 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 última línea es equivalente a 1 + (2 + (3 + 0)) , porque ((+) 3 0) es lo mismo que (3 + 0) .

Transformando con `map`

A menudo, deseamos convertir o transformar el contenido de una colección (una lista o algo que se pueda recorrer). En Haskell usamos el 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]

Filtrado con `filter`

Dada una lista:

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

podemos filtrar una lista con un predicado usando 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]

Por supuesto que no se trata solo de números:

 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]

Listas de cierre y descompresión

zip toma dos listas y devuelve una lista de pares correspondientes:

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

Comprimiendo dos listas con una función:

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]

Descomprimir una lista:

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

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