Funtores, funtores aplicativos y monoides

26 Sep 2015 Xook & Do View Markdown source

As of March 2020, School of Haskell has been switched to read-only mode.

Sections

En este tutorial veremos clases de tipos un poco más avanzadas. Comenzaremos con la clase Functor, continuaremos con la clase Applicative, después Semigroup y al final monoid. Estudiar las clases Functor y Applicative nos prepararán para el siguiente tutorial sobre la clase Monad. En Haskell, es común que la definición de una clase de tipo esté acompañada de "leyes" que se tienen que cumplir a implementar dichas clases. Las leyes de la clase Functor y Applicative no son las más sencillas, por lo que también estudiaremos en este tutorial las clases Semigroup y Monoid, cuyas leyes son bastante simples. También existe una relación entre los monoides y los mónadas comúnmente expresada con la frase: "Un mónada es sólo un monoide en la categoría de endofuntores", eso pertenece a la rama de teoría de categorías, lo cual es un tema muy aparte.

Funtores (Functor)

La clase Functor puede ser implementada por todas aquellas estructuras de datos a las cuales se les pueda aplicar una función a todos sus elementos.

La especificación de la clase Functor es la siguiente:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

fmap es la función que mapea una función a todos los elementos del tipo que implemente la clase. En el tipo de fmap ((a -> b) -> f a -> f b ), se puede ver que el primer parámetro es una función a -> b, esa es la que se aplica a todos los elementos dentro de f y el segundo parámetro es el functor, f a.

Leyes de los funtores

A veces no basta con dar una implementación para las funciones de una clase; a veces se tienen que seguir ciertas leyes. La clase Functor tiene dos leyes:

  • Ley de identidad fmap id = id, es decir, si intentamos mapear id sobre los elementos de algún contenedor, nos debe de dar lo mismo a que si no hubiésemos hecho nada (sin efectos secundarios).
  • fmap (f.g) x = fmap f (fmap g x) En teoría, cada implementación de una clase debe de venir acompañada de demostraciones matemáticas que demuestren que se cumplen las leyes. En el último tutorial veremos como usar QuickCheck para demostrar con cierta confiabilidad que se cumplen las leyes; es decir, no son demostraciones sino simples pruebas con alta probabilidad de confiabilidad.

Listas como funtores

Un ejemplo que ahora debería de ser fácil de entender son las listas; de hecho, la única razón por la que la función se llama fmap y no simplemente map es porque map ya está reservado para listas, pero hacen exactamente lo mismo.

Si la función map no existiera, podríamos implementar Functor para listas de esta manera:

instance Functor [] where
  fmap _ [] = []
  fmap f (x:xs) = f x : fmap xs

Pero map sí existe y esta es precísamente su definición:

map _ [] = []
map f (x:xs) = f x : fmap xs

Por lo que la implementación de fmap para listas es simplemente:

instance Functor [] where
  fmap = map

Un ejemplo de su uso:

main =
  do
    print $ fmap (+ 1) []
    print $ fmap (+ 1) [1,2,3]

En el prelude de Haskell ya viene incluida la implementación de Functor para [], por lo que uno no tiene que escribirla para usarla.

Maybe como funtor

El tipo Maybe es otra instancia de Functor. En el prelude de Haskell también ya viene incluida la implementación de Functor para Maybe, por lo que uno no tienes que escribirla para usarla.

Su implementación es obvia:

instance Functor Mabye where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

Un ejemplo de su uso:

main =
  do
    print $ fmap (+ 1) Nothing
    print $ fmap (+ 1) (Just 0)

Nuestra implementación de Functor para un árbol binario etiquetado

Si modelamos un árbol binario etiquetado así:

data LBTree a = InternalNode a (LBTree a) (LBTree a) | Leaf (Maybe a)

Podriamos hacerlo miembro de la clase Functor de la siguiente manera:

instance Functor LBTree where
fmap f (InternalNode x left right) = InternalNode (f x) (fmap f left) (fmap f right)
fmap f (Leaf Nothing) = Leaf Nothing
fmap f (Leaf (Just x)) = Leaf (Just f x)

Y para demostrar su funcionalidad, reutilizaremos este ejemplo

data LBTree a = InternalNode a (LBTree a) (LBTree a) | Leaf (Maybe a) deriving Show

instance Functor LBTree where
  fmap f (InternalNode x left right) = InternalNode (f x) (fmap f left) (fmap f right)
  fmap _ (Leaf Nothing) = Leaf Nothing
  fmap f (Leaf (Just x)) = Leaf (Just (f x))

example = InternalNode 2
            (InternalNode 7
              (Leaf (Just 2))
              (InternalNode 6
                (Leaf (Just 5))
                (Leaf (Just 11))))
            (InternalNode 5
              (Leaf Nothing)
              (InternalNode 9
                (Leaf (Just 4))
                (Leaf Nothing)))

main = print $ fmap (* 10) example

Funtores aplicativos (Applicative Functor)

Los funtores aplicativos son parecidos a los funtores, pero con la diferencia de que el "contenedor" puede albergar funciones también y que el operador <*>, lo que sería fmap, pero para funtores, mapea una función que se encuentra en un contenedor; quizás quede más claro si comparamos los tipos de fmap y <*>: <*> :: {-h-}f{-/h-} (a -> b) -> f a -> f b fmap :: (a -> b) -> f a -> f b

Dado que Maybe es una instancia de un funtor, además de poder hacer esto:

fmap (+ 1) (Just 2) = Just 3

También podemos hacer esto:

(<*>) (Just (+ 1)) (Just 2) = Just 3
-- Or in its more natural usage, as an infix operator:
Just (+ 1) <*> Just 2 = Just 3

Para poder introducir una función dentro de un contenedor, usamos la función pure que junto con <*> forman la clase Applicative.

Pudimos haber escrito el ejemplo pasado como:

pure (+ 1) <*> Just 2 = Just 3

La definición completa de Applicative es:

class Functor f => Applicative f where
  pure :: (a -> b) -> f (a -> b)

  <*> :: f (a -> b) -> f a -> f b

  <$> :: (a -> b) -> f a -> f b
  h <$> f = pure h <*> f

El operador <$> contiene una definición default que se deriva de pure y <*>, por lo que no es necesario implementarla, basta con implementar pure y <*>. La utilidad de <$> es la de ahorrarnos tener que llamar primero a pure antes de poder aplicarle un valor usando <*>a la función que deseamos meter dentro del contenedor. Por ejemplo:

import Control.Applicative  -- The Applicative class is defined in the Control.Applicative module
main =
  do
    print $ {-hi-}pure{-/hi-} (+ 1) {-hi-}<*>{-/hi-} Just 2
    print $ (+ 1) {-hi-}<$>{-/hi-} Just 2

Leyes de los funtores aplicativos

Además de las leyes inherentes de ser un funtor, un funtor aplicativo debe de cumplir con estas leyes:

  • Ley de identidad

    pure id <*> x = x, similar a la primer ley de los functores

  • fmap g x = pure g <*> x

Esta otra ley relaciona a los functores con los functores aplicativos al poner a fmap, pure y a <*> en la misma ecuación:

  • Homomorfismo

    El término homomorfismo proviene de teoría de categorías; un homomorfismo es una función que mapea de un objeto a otro con la misma estructura matemática. Esta es la ley: pure f <*> pure x = pure (f x)

  • Intercambio

    En la expresión u <*> pure y no debe importar si primero se ejecuta (<*>) u o si primero se ejecuta pure y, la ley dice así: u <*> pure y = pure (\f -> f y) <*> u

  • Composición

    Esta es la ley: u <*> (v <*> w) = pure (.) <*> u <*> v <*> w, pero no queda muy clara su intención. Yo la reescribiría de esta manera: C f1 <*> (C f2 <*> C x) = pure ((f1.f2) x) donde C es el contenedor. Así queda más claro que la intención de la ley es expresar que se podría primero realizar la composición entre f1 y f2, después la aplicación de x y al final meter todo en un contenedor con pure, pues a pesar de que en Haskell no existen sentencias, solo expresiones, al momento de la verdad (al momento de la ejecución) sí existe cierto orden de ejecución, por lo que a veces es necesario expresiar que el orden de ejecución de las partes de una expresión no debería de importar.

Maybe como funtor aplicativo

Ya hemos usado a Maybe como funtor y su implementación no debe resultar extraña:

import Control.Applicative

instance Applicative Maybe where
  pure f = Just f
  Nothing <*> _ = Nothing
  _ <*> Nothing = Nothing
  Just f <*> Just x = Just (f x)

Y aquí un ejemplo de cada caso:

import Control.Applicative
import Data.Char

e1 :: Maybe String
e1 = Nothing <*> Just "hi"      

e2 :: Maybe String
e2 = Just (map toUpper) <*> Nothing

e3 :: Maybe String
e3 = Just (map toUpper) <*> Just "hi"

e4 :: Maybe String
e4 = pure (map toUpper) <*> Just "hi"

e5 :: Maybe String
e5 = map toUpper <$> Just "hi"

main =
  do
    print e1
    print e2
    print e3
    print e4
    print e5

Listas como funtor aplicativo

Maybe nos permitió poner una función dentro de un contenedor, pero ¿cuál sería el comportamiento de aplicar una lista de funciones a una lista de valores? Primero veamos un ejemplo y después lo explicaremos presentando la definición de los funtores aplicativos para listas.

import Control.Applicative
import Data.Char
main =
  do
    print $ [(+ 1), (* 2)] <*> [3,4,5]
    print $ [Prelude.map toUpper, (\x -> x ++ ", world!")] <*> ["hello", "hi"]

Podemos ver que cada función en la lista de la izquierda se aplica a cada elemento de la lista de la derecha. Si ahora vemos la implementación de de Applicative para listas, podemos comprobarlo:

import Control.Applicative

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs] -- for each f in fs, for ecah x in xs

Más allá de funciones de un solo parámetro

El tipo del operador <*> es f (a -> b) -> f a -> f b, pero eso no significa que sólo se puedan usar funciones de un sólo parámetro, pues la b podría sustituirse por otra función, digamos, c -> d. Por ejemplo:

import Control.Applicative

-- here we can see that f (a -> {-hi-}b{-/hi-}) gets substituted by Just (Int -> (Int -> Int)),
--   where f = Maybe, a = Int and {-hi-}b = (Int -> Int){-/hi-}
f1 :: Maybe (Int -> (Int -> Int))
f1 = pure (+)

f2 :: Maybe (Int -> Int)
f2 = f1 <*> Just 1

f3 :: Maybe Int
f3 = f2 <*> Just 2

main =
  do
    print $ f3
-- or all together
    print $ pure (+) <*> Just 1 <*> Just 2
-- and even simplier
    print $      (+) <$> Just 1 <*> Just 2

Semigrupos

Los semigrupos son un concepto del algebra que se representa en Haskell con la clase Semigroup, definida en Data.Semigroup. Un semigrupo es un conjunto de valores cerrados por una operación asociativa, es decir, que dados dos elementos del semigrupo, la operación asociativa regresa otro elemento del mismo semigrupo. En Haskell, la operación asociativa de un semigrupo es <>; esta es la definición completa de un semigrupo:

class Semigroup a where
  (<>) :: a -> a -> a

  sconcat :: NonEmpty a -> a
  sconcat (a :| as) = go a as where
    go b (c:cs) = b <> go c cs
    go b []     = b

NonEmpty a representa una lista no vacia: NonEmpty v = x :| xss donde xss es una listá común (posiblemente vacía). Entonces, sconcat es una función que dada una lista no vacía de as, los combina en un solo valor mediante <>.

Leyes de los semigrupos

La única regla que deben de cumplir los semigrupos es que <> debe de ser asociativa, por lo que los enteros junto con la resta, no pueden formar un semigrupo, pues no es lo mismo (1-2)-3 = -4 que 1-(2-3) = 2.

A continuación, una instancia de Semigroup que sí cumple con la ley de asociatividad para <>:

import Data.Semigroup
import Data.List.NonEmpty

instance Semigroup Int where
  (<>) = (+)

aNonEmptyList = (1 :| [2,3]) :: NonEmpty Int

main =
  do
    print $ (1::Int) <> 2
    print $ sconcat aNonEmptyList
    -- It is only necessary to specify the type of one number, the compiler will infer the rest

Monoides

Los monoides son un concepto de algebra que se representa en Haskell con la clase Monoid definida en Data.Monoid:

class Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
 
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

mappend es un operador binario que dado dos as regresa otra a, es decir, un monoide a está cerrado bajo la operación mappend.

Leyes de los monoides

Además de ofrecer implementaciones para mempty y mappend, se deben de cumplir dos leyes:

  • Identidad de mempty para el lado izquierdo y derecho: - mappend mempty x = x - mappend x mempty = x
  • Asociatividad de mappend. mappend (mappend x y) z = mappend x (mappend y z)

Por ejemplo, Int y la función + forman un monoide, donde Int es a, + es mappend y el 0 es mempty. Se podría comprobar facilmente que (+) 0 = id por lo que 0 cumple con los requisitos para ser el mempty de Int y (+). A continuación la demostración por inducción (probablemente la instancia mas senilla de la inducción matemática):

-- base case:
(+) 0 0 = 0           -- e1
-- for any n:
(+) 0 n = n           -- e2, since 0 + n = n
-- now we need to show that "(+) 0 (n + 1) = n + 1" holds:
(+) 0 (n + 1) = n + 1 -- e3, to be shown
  -- we know that (n + 1) = (0 + n) + 1 and that (0 + n) = (+) 0 n,
  -- so (+) 0 (n + 1) equals to:
  ((+) 0 n) + 1
  -- replacing ((+) 0 n) by the right hand side of e2:
  n + 1 -- which is what we wanted to proof of e3

La implementación de Monoid para Int, 0 y (+) es:

import Data.Monoid

instance Monoid Int where
  mempty = 0
  mappend = (+)

¿Qué crees que haga mconcat?

import Data.Monoid

instance Monoid Int where
  mempty = 0
  mappend = (+)

listOfInts = [1,2,3] :: [Int] -- we need to specify that those Nums are Ints.
main = print $ mconcat listOfInts

Así es, intuitivamente se podría decir que los junta a todos en un solo valor; formalmente se dice que mconcat hace, pues, lo que dice su definición: foldr mappend mempty.

Multiples instancias de la misma clase para el mismo tipo

Int también se podría hacer una instancia de Monoid usando (*) como mappend y 1 como mempty:

import Data.Monoid

instance Monoid Int where
  mempty = 1
  mappend = (*)

listOfInts = [1,2,3] :: [Int] -- we need to specify that those Nums are Ints.
main = print $ mconcat listOfInts

Pero, ¿qué pasa si queremos ambas instancias de Monoid para Int? una con mappend = (+) y otra con mappend = (*). No se puede, intentémoslo:

import Data.Monoid

instance Monoid Int where
  mempty = 0
  mappend = (+)
  
instance Monoid Int where
  mempty = 0
  mappend = (-)

listOfInts = [1,2,3] :: [Int]
main = print $ mconcat listOfInts
               -- ummm, do you mean "mconcat = foldr {-hi-}(+){-/hi-} 0 listOfInts"
               -- or "mconcat = foldr {-hi-}(-){-/hi-} 0 listOfInts"

El compilador dice algo de "instancias duplicadas de la clase Monoid para Int". Afortunadamente existe una solución, utilizar newtype.

newtype nos permite crear un tipo nuevo (no un simple sinónimo de tipo como con type); podemos entonces crear dos tipos nuevos a partir de Int y hacer cada uno una instancia de Monoid, uno con mappend a base de (+) y otro con mappend a base de (*):

import Data.Monoid

newtype IntMP = IntMP Int  -- for Monoid Int with mappend based on (+)
newtype IntMT = IntMT Int  -- for Monoid Int with mappend based on (*)

instance Show IntMP where
  show (IntMP x) = show x

instance Show IntMT where
  show (IntMT x) = show x

instance Monoid IntMP where
  mempty = IntMP 0
  IntMP x `mappend` IntMP y = IntMP (x + y)
  
instance Monoid IntMT where
  mempty = IntMT 0
  IntMT x `mappend` IntMT y = IntMT (x - y)

intsMPs = [IntMP 1, IntMP 2, IntMP 3]
intsMTs = [IntMT 1, IntMT 2, IntMT 3]

main =
  do
    print $ mconcat intsMPs
    print $ mconcat intsMTs

De hecho ya existe algo similar a IntMP y que no sólo es para Ints sino para toda la clase Num; se llaman Sum y funciona así

import Data.Monoid

intsAsSum = [0,1,2] :: [Sum Int]
floatsAsSum = [0,1,2] :: [Sum Float]
doublesAsSum = [0,1,2] :: [Sum Double]

main =
  do
    print $ mconcat intsAsSum
    print $ mconcat floatsAsSum
    print $ mconcat doublesAsSum

También existe Product:

import Data.Monoid

intsAsProduct = [0,1,2] :: [Product Int]
floatsAsProduct = [0,1,2] :: [Product Float]
doublesAsProduct = [0,1,2] :: [Product Double]

main =
  do
    print $ mconcat intsAsProduct
    print $ mconcat floatsAsSum
    print $ mconcat doublesAsSum

Listas como instancias de Monoid

Una vez sabiendo que las listas pueden ser instancias de Monoid, no debe de ser muy difícil imaginar que valor será mempty y cual mconcat. ¿Qué función recibe dos listas y produce una lista? (++), entonces (++) puede ser mconcat. Si (++) es mconcat, ¿cuál valor podría ser mempty tal que (++) mempty xs = xs para todo xs? La lista vacía ([]), obviamente.

Esta es la instancia de Monoid para las listas:

instance Monoid [] where
  mempty = []
  mconcat = (++)

Ahora podemos crear expresiones que son compatibles con cualquier monoide:

import Data.Monoid

f m1 m2 m3 m4 = (mappend m1 m2, mappend m3 m4)

main =
  do
    print $ f (1::Sum Int) (2::Sum Int) (3::Sum Int) (4::Sum Int)
    print $ f [1] [2] [3,4] [5]

Ejercicios

Ejercicios

Soluciones

Siguiente tutorial

Mónadas. Work in progress