Piensa en la lista en Haskell [5]. Es lo mismo que 5:[]. A la izquierda del : hay un valore, y a la derecha hay una lista. En este caso, una lista vacía. ¿Qué pasaría con la lista [4,5]? Bueno, es lo mismo que 4:(5:[]). Si miramos el primer :, vemos que también tiene un elemento a su izquierda y una lista a su derecha (5:[]). Lo mismo sucede para la lista 3:(4:(5:6:[])), que también podría escribirse como 3:4:5:6:[] (ya que : es asociativo por la derecha) o [3,4,5,6].
Podemos decir que una lista es o bien una lista vacia o bien un elemento unido con un : a otra lista (que puede ser una lista vacía o no).
Podemos usar los tipo de datos algebraicos para implementar nuestra propia lista:
data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
Se lee de la misma forma que se leía nuestra definición de lista en un párrafo anterior. Es o bien una lista vacía o bien una combinación de un elemento y otra lista. Si estás confundido con esto, quizás te sea más fácil entenderlo con la sintaxis de registro:
data List a = Empty | Cons { listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)
Puede que también estes confundido con el constructor Cons. Cons es otra forma de decir :. En realidad, en las listas, : es un constructor que toma un valor y otra lista y devuleve una lista. En otras palabras, tiene dos campos. Uno es del tipo a y otro es del tipo [a].
ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))
Cons 3 (Cons 4 (Cons 5 Empty))
Si hubiésemos llamado a nuestro constructor de forma infija podrías ver mejor como es simplemente :. Empty es como [] y 4 `Cons` (5 `Cons` Empty) es como 4:(5:[]).
Podemos definir funciones que automáticamente sean infijas si las nombramos únicamente con caracteres especiales. Podemos hacer lo mismo con los constructores, ya que son simplemente funciones que devuelve un tipo de dato concreto. Mira esto:
infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)
Antes de nada, vemos que hay una nueva construcción sintáctica, una declaración infija. Cuando definimos funciones como operadores, podemos usar esta cosntrucción para darles un determinado comportamiento (aunque no estamos obligados a hacerlo). De esta forma definimos el orden de precedencia de un operador y si asociativo por la izquierda o por la derecha. Por ejemplo, * es infixl 7 * y + es infixl 6 +. Esto siginifica que ambos son asociativos por la izquierda de forma que (4 * 3 * 2) es (4 * 3) * 2) pero * tiene un orden de precedencia mayor que +, por lo que 5 * 4 + 3 es equivalente a (5 * 4) + 3.
De qualquier modo, al final acabamos escribiendo a :-: (List a) en lugar de `` Cons a (List a)``. Ahora podemos escribir las listas así:
ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> 100 :-: a
(:-:) 100 ((:-:) 3 ((:-:) 4 ((:-:) 5 Empty)))
Haskell seguirá mostrando el constructor como una función prefija cuando derivemos Show, por este motivo aparecen los paréntesis alrededor del constructor (recuerda que 4 + 3 es igual que (+) 4 3).
Vamos a crear una función que una dos de nuestras listas. Así es como está definida la función ++ para listas normales:
infixr 5 ++
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
Así que copiamos esta definición y la aplicamos a nuestras listas:
infixr 5 .++
(.++) :: List a -> List a -> List a
Empty .++ ys = ys
(x :-: xs) .++ ys = x :-: (xs .++ ys)
Y así es como funciona:
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> let b = 6 :-: 7 :-: Empty
ghci> a .++ b
(:-:) 3 ((:-:) 4 ((:-:) 5 ((:-:) 6 ((:-:) 7 Empty))))
Fíjate que hemos utilizado un ajuste de patrón (x :-: xs). Esto función ya que el ajuste de patrones en realidad funciona ajustando constructores. Podemos ajustar un patrón :-: porque es un constructor de nuestro tipo de la misma forma que : es un constructor de las listas estándar. Lo mismo sucede para [].
Ya que el ajuste de patrones funciona (solo) con constructores de datos, podemos ajustar patrones como los constructores prefijos normales, constructores infijos o cosas como 8 o 'a', que al fin y al cabo son constructores de tipos numéricos y caracteres.
