Deja que los funtores de Haskell se hundan.

Izquierda y Derecha no son tipos, y Left x y Right y son del mismo tipo. Son solo constructores de Cualquiera. Usted puede considerar

Left :: c -> Either c d
Right :: d -> Either c d

Puedes tener 2 fmap declaraciones porque sabemos que las de la izquierda y las de la derecha son valores diferentes. Es como

g :: Int -> Int
g 1 = 2
g 2 = 4
g n = n

Aquí no podemos decir que 1 y 2 y n son "tipos" diferentes solo porque la coincidencia de patrones funciona.

La clase Funtor se define de tal manera que

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

Tenga en cuenta que a y b son tipos arbitrarios. Para mayor claridad, cambiemos el nombre de a en su instancia a c, y la función f a func.

instance Functor (Either c) where  
    fmap func (Right x) = Right (x)  
    fmap func (Left x) = Left (func x)

Asume que cualquiera de los dos sigue la definición predeterminada

data Either c d = Left c | Right d

Entonces por su definición,

fmap    func     (Right x) = Right x
-- # (a -> b) ->      f a       f  b
-- # f = Either c

Esto obliga a = b, y

fmap    func     (Left x) = Left (func x)
-- # (a -> b) ->     f a       f b
-- # f = Either c

Fuerzas c = a = b. Ambos no son válidos teniendo en cuenta a, b y c son tipos arbitrarios independientes.

Ok así que aquí hay otro intento muy simple en esto.

Te preguntas por qué esto no compila:

instance Functor (Either a) where
    fmap f (Right x) = Right (x)
    fmap f (Left x) = Left (f x)

Así que vamos a tratar de simplificar el problema tratando de definir la misma función sin ponerlo como parte de una declaración de instancia de clase:

Que nos da

foo f (Right x) = Right (x)
foo f (Left x) = Left (f x)

Que de hecho compila. ghci nos dice la firma de tipo:

*Main> :t foo
foo :: (t1 -> a) -> Either t1 t -> Either a t

Cambiaremos el nombre de algunas de las variables para conseguir algo más uniforme:

foo :: (a -> b) -> Either a c -> Either b c

Eso hace a la perfección sentido. Toma una función y la aplica a la izquierda de una Cualquiera.

Pero ¿cuál es la firma para fmap?

*Main> :t fmap
fmap :: (Functor f) => (a -> b) -> f a -> f b

Así que sustituyamos Either c por f en la firma fmap (Cambié el nombre de Either a a Either c para evitar que nuestras dos as diferentes se mezclen):

fmap :: (a -> b) -> Either c a -> Either c b

¿ves el problema? Su función es perfectamente válida has solo tiene un tipo diferente de lo que fmap para Either a necesariamente debe tener .

, Esto es una especie de cosa hermosa tipo. Dada la firma para fmap, realmente solo hay una implementación significativa para fmap en Cualquiera de los dos.

A veces, cuando tenemos suerte y cuidado, podemos terminar en situaciones similares given dada una firma de tipo, la función casi se escribe a sí misma.

Editar: tratando de responder a las siguientes preguntas.

1) No hay una" composición de dos funciones". Para obtener la firma de tipo para fmap sobre {[8] } simplemente vaya a través de la firma de la función fmap, y cada lugar que veas f, sustitúyelo por Either a. Llamaríamos a eso una" especialización " del tipo firma de fmap. Es decir, esestrictamente menos general que el tipo normal de fmap any cualquier lugar que requiera una función del tipo más especializado, puede pasar algo del tipo general sin problemas.

2) Su función para mapear sobre el lado izquierdo (que nombré "foo" en los ejemplos anteriores) está bien. Funciona bien, hace lo que quieres. Usted simplemente no se puede nombrar fmap y usarlo en una instancia de Funtor. Personalmente, lo nombraría algo así como onLeft o mapLeft.

Todo lo siguiente puede ser ignorado / es para información, pero no una sugerencia para lectura futura en un futuro cercano/uso real:

Si uno quiere ser muy técnico, porque puede mapear tanto el lado izquierdo como el derecho (aunque solo puede declarar Funtor para este último), o bien no es solo un Funtor, sino un Bifuntor. Esto se proporciona en, por ejemplo, ekmett's Categoría-Extras biblioteca (ver http://hackage.haskell.org/packages/archive/category-extras/0.44.4/doc/html/Control-Bifunctor.html).

Hay muchas cosas interesantes que involucran el cálculo con programas, y la "programación de origami" que usa bifunctores con más rigor. Puedes leer sobre ello aquí: http://lambda-the-ultimate.org/node/1360 Pero, probablemente no quieras, al menos hasta que estés mucho más familiarizado con Haskell. Es informática, matemáticas, investigación, y muy guay, pero no es necesario en absoluto para entender la programación idiomática de Haskell.

Si bien eventualmente me aferraré a su formato, voy a comenzar con algo en un formato ligeramente diferente, ya que creo que hará que mi explicación sea más clara.

Consideremos un tipo de datos diferente

data Choice a = Default Integer | Chosen a

-- This corresponds to your top, working, instance.
instance Functor Choice where
  fmap f (Default i) = Default i
  fmap f (Chosen  a) = Chosen  (f a)

Debería quedar claro por qué funciona esta instancia. Sin embargo, ¿qué pasa con lo siguiente:

-- Broken!
instance Functor Choice where
  fmap f (Default i) = Default (f i)
  fmap f (Chosen  a) = Chosen  a

Deberías ser capaz de ver por qué esto no funciona. El tipo de fmap es Functor f => (a -> b) -> f a -> f b; en este contexto, es (a -> b) -> Choice a -> Choice b. Por lo tanto, el argumento f tiene el tipo a -> b. Sin embargo, en la segunda declaración de instancia (fallida), escribe f i. Sabemos, debido a la declaración de tipo de datos, que i debe ser un Integer, por lo que no podemos aplicarle f. Del mismo modo, dado que a tiene tipo a, Chosen a tendrá type Chosen a, no type Chosen b. Por lo tanto, la instancia Functor en la parte inferior no puede funcionar.

Bueno, tu instancia superior para Either funciona porque, como en el ejemplo Choice, obedece a los tipos. Echémosle un vistazo, con algunos renamings:

instance Functor (Either c) where  
  fmap f (Left  c) = Left  c
  fmap f (Right a) = Right (f a)

Esta declaración de instancia no declara una instancia de Functor para Either-no puede. Algo que es una instancia de Functor debe tomar un parámetro de tipo. Por lo tanto, Int no puede ser un funtor, ya que Int no toma parámetros de tipo, pero [] y Maybe pueden ser, ya que [a] y Maybe a son tipos completos. Either, sin embargo, toma dos parámetros de tipo: Either a b. Por lo tanto, lo que esta instancia hace {[75] } es declarar que Either c es un funtor para cualquier posible c. Que c es fijo para la duración de la declaración de instancia. Así que vamos a ir a través y añadir tipos (esto no es sintaxis legal!):

instance Functor (Either c) where
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  c
  fmap f (Right (a :: a)) = Right (f a :: b)

Dado que f tiene el tipo a -> b, pero el tipo de c está fijo en c, no podemos escribir Left (f c); e incluso si pudiéramos, queremos que el c se deje solo, para que podamos devolver un (Either c) b. Del mismo modo, debemos aplicar f a a para obtener algo del tipo b.

Esta es también la razón por la que su la instancia inferior no funciona: tiene una función que necesita funcionar para cualquier tipo que se aplique solo al tipo fijo c, y deja el tipo que necesita para transformar solo. Echémosle un vistazo, de nuevo con las firmas de tipo añadidas:

instance Functor (Either c) where  
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  (f c)
  fmap f (Right (a :: a)) = Right a

Aquí, la primera parte de la definición de la función intenta aplicar una función f :: a -> b a algo del tipo fijo c, que no puede funcionar, por lo que esto ya falla. Pero veamos qué tipo genera esto. En este caso, esperar que (de alguna manera) f c tendría el tipo b, y a tendría el tipo a. En ese caso, estamos devolviendo un valor de tipo Either b a, que todavía no está permitido.

Básicamente, el problema se deriva de esto. Primero, tenga en cuenta que f es lo mismo entre las dos cláusulas de definición de función, por lo que no puede cambiar entre líneas. En segundo lugar, tenga en cuenta que estamos fijando c, y declarando una instancia para que c. Esto es cierto para cualquier c, pero nosotros sólo mira uno a la vez. Finalmente, debido a esto, el argumento de Left es no parametrizado por el tipo que f espera; se garantiza que tendrá algún tipo fijo c. Esto significa que (a) no se puede aplicar f a él, y (b) debe aplicarlo al argumento Right, ya que de lo contrario no cambiará el tipo que se espera que cambie.

(Editar para tratar de responder mejor a la pregunta)

La definición de Cualquiera de los dos es:

data Either a b = Left a | Right b

Así que "Cualquiera" toma dos argumentos de tipo. Por cierto, técnicamente "Either" no es realmente un tipo, sino un constructor de tipo; toma argumentos de tipo para crear un tipo.

La definición de Funtor es:

class Functor f where
   fmap :: (p -> q) -> f p -> f q

Así que en esta definición de clase cualquier tipo "f" que sea una instancia de Funtor debe tomar un argumento de tipo. Esto no se declara; se infiere de la "f p" y "f q"; puesto que "f" se le da un parámetro de tipo aquí debe ser un tipo que toma uno.

(Nota: la definición original usaba "a" y "b" en lugar de "p" y "q". Estoy usando letras diferentes para mantener las cosas distintas de "Ya sea a b" cuando llego a eso más tarde)

En la mayoría de los casos "f" es un tipo de contenedor como una lista o un árbol. Así que por ejemplo tienes

data Tree a = ...

instance Functor Tree where
   fmap func_a2b tree_of_a = ... --  tree of b.

Sin embargo, "Cualquiera" toma dos parámetros de tipo, así que ¿cómo podemos encajarlo en este esquema? La respuesta es que los tipos pueden tener parcial aplicación al igual que las funciones. De la misma manera que Puedo declarar una función

foo x y = ...

Y luego decir "foo 2" para obtener una nueva función que espera el segundo argumento, por lo que puedo decir "O bien a" para obtener un nuevo tipo que espera el segundo argumento de tipo.

Ahora mira la instancia original:

instance Functor (Either a) where ....

Así que aquí "Either a" es un constructor de tipo que espera un argumento más, al igual que Functor espera de sus instancias. Así que el tipo de" fmap "para" Cualquiera de los dos " será be

fmap :: (p -> q) -> Either a p -> Either a q

Así que ahora en la cláusula "where" tienes que dar una definición de "fmap" que tiene este tipo. El primero que cite tiene este tipo porque el segundo parámetro type se usa para el constructor "Correcto", y ese es el que se aplica la función. El segundo no funcionará, porque tendría el tipo

fmap :: (p -> q) -> Either p a -> Either q a

Y eso no es lo que la clase Functor dice que va a ser.

Lo creas o no, esto no es magia. Todo tiene que ver con que el tipo Either a b no sea el mismo tipo que Either b a. Aquí está la definición de Cualquiera de Preludio

data  Either a b  =  Left a | Right b

... Observe cómo la variable de tipo a viene primero, luego b, y también observe que solo incluimos a en la declaración de Cualquiera de los Funtores:

instance Functor (Either a) where  
    fmap f (Right x) = Right (f x)  
    fmap f (Left x) = Left x

Ahora veamos la definición del Funtor Maybe

instance Functor Maybe where
    fmap = map

Aquí no hay ninguna variable de tipo, Aunque Maybe toma un parámetro de tipo (como Maybe Int). Lo que estoy tratando de llegar a es que los tipos no son funtores, los constructores de tipos son funtores (los funtores tienen clase *->*).

Así que vamos a f :: b -> c, en la versión de la Functor que funciona, el x de (Left x) es de tipo a, lo cual está bien ya que es (Either a) que es un functor, el x en (Right x) es de Tipo b tan (Right x) es de tipo ((Either a) b), y (Right (f x)) es de tipo ((Either a) c), por lo tanto, fmap es de tipo (b->c) -> ((Either a) b) -> ((Either a) c), como se requiere.

En su versión que falló, tenemos que x en (Right (x)) no es de tipo a, pero de tipo b, Entonces (Right (x)) es no de tipo ((Either a) c) que no encaja con el tipo de fmap.

Así que para resumirlo: el fmap que funciona sale: {[27]]}, pero el que no funciona sale: (b -> c) -> (Either b) a -> (Either c) a y ese no es el tipo correcto para fmap.

Con suerte, esto ayudará...

Primero, sin embargo, algunos antecedentes:

1) Funtor necesita un "constructor de tipo", a (bueno, no un tipo per se,...) tipo que "necesita" otro tipo regular para formar un "tipo completo", al igual que un genérico en Java/C++. Así, por ejemplo, List es un Funtor (lo es, por cierto), o Array, porque (entre otras cosas) el tipo completo no es solo List, sino List<A>. Tan, : Un Funtor toma un "constructor de tipo", un tipo.

2) Either es un tipo de constructor que la gente de Haskell (léase: Edward Kmett, y otros all-stars bien dotados de matemáticas) llaman bifunctor. Necesita dos tipos dados a él para ser completo. Por ejemplo, un uso completo de Cualquiera de los Dos es: Either Integer String que significa (yeah, yeah, " duh!") es un entero (Left), o una cadena (Right). Entonces, esto significa que Either Integer es un tipo incompleto que es un Left Integer o un Right...b cuando decide qué se supone que es esa "b".

Ahora, por diversión part!

La parte superior funciona porque, fmap usa algún constructor de tipo, y lo usa con una función a -> b para hacer una función similar de f a a f b - el ejemplo favorito para esto en Haskell es el de listas, TAMBIÉN conocido como map :: (a -> b) -> ([a] -> [b]), donde el Funtor es la parte [ ]. Ahora, usando algo como Either a (sigamos adelante y usemos Either Integer de antes), la firma de tipo de fmap se ve así:

fmap :: (a -> b) -> (Either Integer a -> Either Integer b)

Y los dos ejemplos (de la parte superior) muestran lo que hace fmap con valores representativos de ese tipo Either Integer a, para obtener un valor de tipo Either Integer b.

Ahora, el tuyo-inferior - no funciona, porque: {[36]]}

1. Tienes una función, f, que toma a s a b s.
2. Su Left tipo tiene que ser tipo Entero, y permanecer un entero (o tipo de flotador, y permanecer un flotador, lo que cada tipo es el izquierda uno de los dos tipos del tipo Either usted está usando).
3. Su Right tipo tiene que ser de cualquiera que sea el tipo que el función toma ("a"), y vaya al tipo que la función hace ("b").

Tiene que hacer esto (pero tus cosas no lo hacen - por eso no funciona), porque ese es el tipo que fmap necesita tener. Específicamente, usted tiene estas ecuaciones:

fmap f (Right x) = Right (x)  
fmap f (Left x) = Left (f x)

Sus ecuaciones dan fmap los tipos:

fmap :: (a -> b) -> Either c d -> Either c d
fmap :: (a -> b) -> Either a d -> Either b d

Que no solo no se ajusta a lo que fmap quiere, sino que ni siquiera es consistente entre sí!

Siento haber escrito medio libro para vadear, pero Espero que eso te dé alguna idea.

Top funciona porque fmap::(b -> c) -> Either a b -> Either a c y el tuyo-bottom - no funciona porque eso requeriría fmap::(a -> c) -> Either a b -> Either a c. Pero, funcionaría si cambiaras a

data Either' a b = Left' b | Right' a deriving (Eq, Show)

instance Functor (Either' a) where  
    fmap f (Right' x) = Right' (x)  
    fmap f (Left' x) = Left' (f x)

La instancia que estás intentando escribir, llamémosla fmap2 por ahora, tiene el siguiente tipo:

fmap2 :: (a -> b) -> Either a c -> Either b c

Si establece el LANGUAGE pragma TypeOperators, GHC también acepta el tipo

fmap2 :: (a -> b) -> (a `Either` c) -> (b `Either` c)

En un mundo ideal esto también funcionaría:

fmap2 :: (a -> b) -> (`Either` c) a -> (`Either` c) b

Lo que daría una instancia de Funtor para (`Either` c) pero la similitud entre los operadores normales (y sus secciones) y los operadores de tipo se descompone en este punto (a menos que haya una opción GHC que me falta!)

En breve: su comprensión de functors está bien, pero te muerde la falta de lambdas de tipo.

Ehm... ¿Qué tal unas palabras sobre "clases"?..
Eso puede simplificar la comprensión, supongo.
Recuerda lo que está ganando. Es decir, en ghci:

Prelude> let f x y z = x + y * z
f :: (Num a) => a -> a -> a -> a
Prelude> :t f 1
f 1 :: (Num t) => t -> t -> t
Prelude> :t f 1 2
f 1 2 :: (Num t) => t -> t
Prelude> :t f 1 2 3
f 1 2 3 :: (Num t) => t

Las mismas cosas que tienes con los tipos. Cuando dices Either tipo de ese tipo es * -> * -> * (es decir, toma dos tipos y produce tipo) y cuando dices Either a tipo es * -> * y para Either a b es * (btw Monad a y Functor a requiere a para ser de tipo * -> *, como recuerdo). Así que cuando dices tipo Either a eso significa tipo que es todavía incompleto (requiere algún" argumento " para ser enlazado), por lo que fmap :: (a -> b) -> f a -> f b se convierte en fmap :: (a -> b) -> (Either c) a -> (Either c) b cuando f se sustituye por Either c.