haskell - for - category theory pdf

¿Qué significa componer dos Functors?

Question

El ejercicio 5 de Haskell Typeclassopedia Sección 3.2 solicita una prueba o un contraejemplo en la declaración

La composición de dos Functors es también un Functor.

Al principio pensé que se trataba de componer los métodos fmap definidos por dos instancias distintas de un Functor , pero eso no tiene sentido, ya que los tipos no coincidirían tanto como puedo decir. Para dos tipos f y f'' , los tipos de fmap serían fmap :: (a -> b) -> fa -> fb y fmap :: (a -> b) -> f'' a -> f'' b , Y eso realmente no parece composable. Entonces, ¿qué significa componer dos Functors ?

Answer 1

De lo que se habla es de la composición de constructores de tipos como [] y Maybe , no de la composición de funciones como fmap . Entonces, por ejemplo, hay dos formas de componer [] y Maybe :

newtype ListOfMabye a = ListOfMaybe [Maybe a]
newtype MaybeOfList a = MaybeOfList (Maybe [a])

La afirmación de que la composición de dos Functors es un Functor significa que hay una forma específica de escribir una instancia de Functor para estos tipos:

instance Functor ListOfMaybe where
    fmap f (ListOfMaybe x) = ListOfMaybe (fmap (fmap f) x) 

instance Functor MaybeOfList where
    fmap f (MaybeOfList x) = MaybeOfList (fmap (fmap f) x)

De hecho, la plataforma Haskell viene con el módulo Data.Functor.Compose que le proporciona un tipo de Data.Functor.Compose que lo hace "gratis":

import Data.Functor.Compose

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

Compose es particularmente útil con la extensión GeneralizedNewtypeDeriving :

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype ListOfMaybe a = ListOfMaybe (Compose [] Maybe a)
   -- Now we can derive Functor and Applicative instances based on those of Compose
   deriving (Functor, Applicative)

Tenga en cuenta que la composición de dos Applicative es también un Applicative . Por lo tanto, dado que [] y Maybe are Applicative s, también lo son Compose [] Maybe y ListOfMaybe . La composición de Applicative s es una técnica realmente pulcra que se está volviendo cada vez más común en estos días, como alternativa a los transformadores de mónada para los casos en los que no se necesita todo el poder de las mónadas.

Answer 2

La composición de dos funciones es cuando se coloca una función dentro de otra función, como

round (sqrt 23)

Esta es la composición de las dos funciones round y sqrt . De manera similar, la composición de dos funtores es cuando se coloca un funtor dentro de otro funtor, como

Just [3, 5, 6, 2]

La lista es un functor, y también lo es Maybe. Puede obtener alguna intuición de por qué su composición también es un functor si intenta averiguar qué debería hacer fmap con el valor anterior. ¡Por supuesto que debe mapearse sobre el contenido del functor interno!

Answer 3

Realmente ayuda pensar acerca de la interpretación categórica aquí, un functor F: C -> D lleva objetos (valores) y morfismos (funciones) a objetos y morfismos de una categoría C a objetos y morfismos en una categoría D

Para un segundo functor G : D -> E la composición de los funtores G . F : C -> E G . F : C -> E simplemente toma el codominio de la transformación F fmap como el dominio de la transformación G fmap . En Haskell esto se logra con un pequeño tipo de desenvolvimiento.

import Data.Functor

newtype Comp f g a = Comp { unComp :: f (g a) }

compose :: f (g a) -> Comp f g a
compose = Comp

decompose :: Comp f g a -> f (g a)
decompose = unComp

instance (Functor f, Functor g) => Functor (Comp f g) where
  fmap f = compose . fmap (fmap f) . decompose

Answer 4

Un Functor proporciona dos asignaciones: una en el nivel de tipo, tipos de mapeo a tipos (este es el x en la instance Functor x where ), y uno en el nivel de cálculo, funciones de mapeo a las funciones (este es el x en fmap = x ). Está pensando en componer el mapeo a nivel de término, pero debería pensar en componer el mapeo a nivel de tipo; por ejemplo, dado

newtype Compose f g x = Compose (f (g x))

puedes escribir

instance (Functor f, Functor g) => Functor (Compose f g)

? ¿Si no, porque no?