fmap - haskell do

Cómo(fmap. Fmap) typechecks

Question

He estado revisando un artículo ( http://comonad.com/reader/2012/abstracting-with-applicatives/ ) y encontré el siguiente fragmento de código allí:

newtype Compose f g a = Compose (f (g a)) deriving Show

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

¿Cómo hace realidad (fmap . fmap) typechecks?

Sus tipos son:

(.)  :: (a -> b) -> (r -> a) -> (r -> b)
fmap :: (a -> b) -> f a -> f b
fmap :: (a -> b) -> f a -> f b

Ahora desde aquí no puedo ver de ninguna manera en qué fmap . fmap fmap . fmap hará typecheck?

Answer 1

La expresión fmap . fmap fmap . fmap tiene dos instancias de fmap que, en principio, pueden tener diferentes tipos. Así que digamos que sus tipos son

fmap :: (x -> y) -> (g x -> g y)
fmap :: (u -> v) -> (f u -> f v)

Nuestro trabajo es unificar tipos (lo que equivale a fmap relaciones de igualdad entre estas variables de tipo) de modo que el lado derecho del primer fmap sea ​​el mismo que el lado izquierdo del segundo fmap . Esperemos que pueda ver que si configura u = gx y v = gy terminará con

fmap :: (  x ->   y) -> (   g x  ->    g y )
fmap :: (g x -> g y) -> (f (g x) -> f (g y))

Ahora el tipo de composición es

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Para que esto funcione, puede seleccionar a = x -> y b = gx -> gy c = f (gx) -> f (gy) para que el tipo pueda escribirse

(.) :: ((g x -> g y) -> (f (g x) -> f (g y)))    ->    ((x -> y) -> (g x -> g y))    ->    ((x -> y) -> (f (g x) -> f (g y)))

que es bastante difícil de manejar, pero es solo una especialización de la firma de tipo original para (.) . Ahora puedes verificar que todo coincida de tal manera que fmap . fmap fmap . fmap typechecks.

Una alternativa es abordarlo desde la dirección opuesta. Digamos que tienes un objeto que tiene dos niveles de functorialidad, por ejemplo

>> let x = [Just "Alice", Nothing, Just "Bob"]

y tienes alguna función que agrega bangs a cualquier cadena

bang :: String -> String
bang str = str ++ "!"

Te gustaría agregar el golpe a cada una de las cadenas en x . Puede pasar de String -> String a Maybe String -> Maybe String con un nivel de fmap

fmap bang :: Maybe String -> Maybe String

y puedes ir a [Maybe String] -> [Maybe String] con otra aplicación de fmap

fmap (fmap bang) :: [Maybe String] -> [Maybe String]

¿Eso hace lo que queremos?

>> fmap (fmap bang) x
[Just "Alice!", Nothing, Just "Bob!"]

Vamos a escribir una función de utilidad, fmap2 , que tome cualquier función f y le aplique fmap dos veces, para que podamos escribir fmap2 bang x lugar. Eso se vería así

fmap2 f x = fmap (fmap f) x

Ciertamente puedes soltar la x desde ambos lados.

fmap2 f = fmap (fmap f)

Ahora te das cuenta de que el patrón g (hx) es el mismo que (g . h) x para que puedas escribir

fmap2 f = (fmap . fmap) f

Así que ahora puedes soltar la f desde ambos lados.

fmap2 = fmap . fmap

cuál es la función en la que estabas interesado. Así que ves que fmap . fmap fmap . fmap simplemente toma una función, y le aplica fmap dos veces, para que pueda elevarse a través de dos niveles de funcionalidad.

Answer 2

Pregunta antigua, pero para mí, conceptualmente, fmap representa "tomar un a -> b y llevarlo ''un nivel hacia arriba'', hasta fa -> fb ".

Así que si tengo un a -> b , puedo fmap para darme un fa -> fb .

Si tengo un fa -> fb , puedo fmap nuevo para darme un g (fa) -> g (fa) . Levanta esa función fa -> fb a nuevas alturas --- un nuevo nivel.

Así que "fmapping" una vez levanta la función una vez. fmapping dos veces levanta esa función de elevación ... entonces, una elevación doble.

Poner en el lenguaje de la sintaxis haskell:

f                    ::         a   ->         b
fmap f               ::       f a   ->       f b
fmap (fmap f)        ::    g (f a)  ->    g (f b)
fmap (fmap (fmap f)) :: h (g (f a)) -> h (g (f b))

Observe cómo cada fmap sucesivo eleva el original a -> b a otro nivel nuevo. Asi que,

fmap               :: (a -> b) -> (      f a  ->        f b  )
fmap . fmap        :: (a -> b) -> (   g (f a) ->     g (f b) )
fmap . fmap . fmap :: (a -> b) -> (h (g (f a)) -> h (g (f a)))

Cualquier "función de orden superior" que devuelva una función de la misma aridad que su entrada puede hacer esto. Tome zipWith :: (a -> b -> c) -> ([a] -> [b] -> [c]) , que toma una función tomando dos argumentos y devuelve una nueva función tomando dos argumentos. Podemos encadenar zipWith s de la misma manera:

f                   ::   a   ->   b   ->   c
zipWith f           ::  [a]  ->  [b]  ->  [c]
zipWith (zipWith f) :: [[a]] -> [[b]] -> [[c]]

Asi que

zipWith           :: (a -> b -> c) -> ( [a]  ->  [b]  ->  [c] )
zipWith . zipWith :: (a -> b -> c) -> ([[a]] -> [[b]] -> [[c]])

liftA2 funciona prácticamente de la misma manera:

f                 ::      a  ->      b  ->      c
liftA2 f          ::    f a  ->    f b  ->    f c
liftA2 (liftA2 f) :: g (f a) -> g (f b) -> g (f c)

Un ejemplo bastante sorprendente que se le da un gran uso en la implementación moderna de la biblioteca de lentes es el siguiente:

f                                ::         a   -> IO          b
traverse f                       ::       f a   -> IO (      f b  )
traverse (traverse f)            ::    g (f a)  -> IO (   g (f b) )
traverse (traverse (traverse f)) :: h (g (f a)) -> IO (h (g (f b)))

Así que puedes tener cosas como:

traverse            :: (a -> m b) -> (   f a  -> m (   f b ))
traverse . traverse :: (a -> m b) -> (g (f a) -> m (g (f b)))

Answer 3

Primero vamos a cambiar los nombres de las variables de tipo para que sean únicos:

(.)  :: (a -> b) -> (r -> a) -> (r -> b)
fmap :: Functor f => (c -> d) -> f c -> f d
fmap :: Functor g => (x -> y) -> g x -> g y

Ahora el primer parámetro para . tiene el tipo a -> b y suministramos un argumento del tipo (c -> d) -> (fc -> fd) , por lo que a es c -> d y b es fc -> fd . Hasta ahora tenemos:

(.) :: Functor f => -- Left operand
                    ((c -> d) -> (f c -> f d)) ->
                    -- Right operand
                    (r -> (c -> d)) ->
                    -- Result
                    (r -> (f c -> f d))

El segundo parámetro para . tiene el tipo r -> a aka r -> (c -> d) y el argumento que damos tiene el tipo (x -> y) -> (gx -> gy) , entonces r convierte en x -> y , c convierte en gx y d convierte en gy . Así que ahora tenemos:

(.)       :: (Functor f, Functor g) => -- Left operand
                                       ((g x -> g y) -> (f (g x) -> f (g y))) -> 
                                       -- Right operand
                                       ((x -> y) -> (g x -> g y)) ->
                                       -- Result
                                       (x -> y) -> f (g x) -> f (g y)
fmap.fmap :: (Functor f, Functor g) => (x -> y) -> f (g x) -> f (g y)