haskell - keywords - meta tags generator
Un ejemplo de un tipo con tipo*->*que no puede ser una instancia de Functor (3)
Para ampliar mi (breve) comentario y la respuesta de Mikhail:
Dado (-> Int) , esperaría que fmap vea como tal:
(a -> Int) -> (a -> b) -> (b -> Int)
o:
(a -> Int) -> (a -> b) -> b -> Int
Es fácil demostrar que a partir de los tres argumentos (a -> Int) , (a -> b) , b no hay forma posible de llegar a Int (sin undefined ), por lo tanto de (a -> Int) , (a -> b) no hay forma de llegar (b -> Int) . Conclusión: no existe una instancia de Functor para (-> Int) .
Soy un principiante de Haskell, por lo que me disculpo si la respuesta es obvia, pero estoy trabajando en Typeclassopedia para comprender mejor las categorías. Al hacer los ejercicios para la sección de Functors, encontré este problema:
Dé un ejemplo de un tipo de tipo * -> * que no se pueda convertir en una instancia de Functor (sin usar indefinido).
Mi primer pensamiento fue definir algún tipo de definición infinitamente recurrente de fmap, pero ¿no sería eso esencialmente lo mismo que si undefined se usara undefined en la definición?
Si alguien pudiera explicar la respuesta sería muy apreciado.
¡Gracias!
Fuente del ejercicio original aquí, sección 3: http://www.haskell.org/haskellwiki/Typeclassopedia#Introduction
También tuve problemas con este, y encontré las respuestas de Ramon y Mikhail informativas, ¡gracias! Estoy poniendo esto en una respuesta en lugar de un comentario porque 500 caracteres es demasiado corto, y para el formato de código.
Estaba teniendo problemas para entender qué era la covariante de (a -> Int) y se me ocurrió este contraejemplo que muestra que los data K a = K (a -> Int) pueden ser una instancia de Functor (refutando la prueba de Ramon)
data K a = K (a -> Int)
instance Functor K where
fmap g (K f) = K (const 0)
Si se compila, debe ser correcto, ¿verdad? ;-) Pasé algún tiempo probando otras permutaciones. Darle la vuelta a la función simplemente lo hizo más fácil:
-- "o" for "output"
-- The fmapped (1st) type is a function output so we''re OK.
data K0 o = K0 (Int -> o)
instance Functor K0 where
fmap :: (oa -> ob) -> (K0 oa) -> (K0 ob)
fmap g (K0 f) = K0 (g . f)
Convertir el Int en una variable tipo lo redujo a la Sección 3.2, ejercicio 1, parte 2:
-- The fmapped (2nd) type argument is an output
data K1 a b = K1 (a -> b)
instance Functor (K1 a) where
fmap :: (b1 -> b2) -> K1 a b1 -> K1 a b2
fmap g (K1 f) = K1 (g . f)
Forzar al tipo fmapped a ser un argumento de la función fue la clave ... tal como dijo la respuesta de Mikhail, pero ahora lo entiendo ;-)
-- The fmapped (2nd) type argument is an input
data K2 a b = K2 (b -> a)
instance Functor (K2 o) where
fmap :: (ia -> ib) -> (K2 o ia) -> (K2 o ib)
-- Can''t get our hands on a value of type o
fmap g (K2 f) = K2 (const (undefined :: o))
-- Nor one of type ia
fmap g (K2 f) = K2 (const (f (undefined :: ia)))
Un ejemplo simple es
data K a = K (a -> Int)
Esto es lo que ghci nos dice que intentamos derivar automáticamente una instancia de Functor para K :
Prelude> :set -XDeriveFunctor
Prelude> data K a = K (a -> Int)
Prelude> :k K
K :: * -> *
Prelude> data K a = K (a -> Int) deriving Functor
<interactive>:14:34:
Can''t make a derived instance of `Functor K'':
Constructor `K'' must not use the type variable in a function argument
In the data type declaration for `K''
El problema es que la clase Functor estándar en realidad representa funtores covariantes ( fmap eleva su argumento a fa -> fb ), pero no hay forma de que pueda componer a -> b a -> Int para obtener una función de tipo b -> Int (ver la respuesta de Ramón). Sin embargo, es posible definir una clase de tipo para los funtores contravariantes:
class Contravariant f where
contramap :: (a -> b) -> f b -> f a
y haz de K un ejemplo de ello:
instance Contravariant K where
contramap f (K g) = K (g . f)
Para más información sobre la covarianza / contravarianza en Haskell, consulte here .
Edición: Aquí también hay un buen comentario sobre este tema de Chris Smith en Reddit.