definir - Deje que los funtores de Haskell se hundan.

definir datos haskell (10)

Learn You a Haskell tiene un ejemplo sobre los funtores. Puedo leer LYAH, y enviar mensajes de texto, y descubrir qué se supone que sucederá, pero no sé lo suficiente como para escribir algo como esto. Estoy encontrando este problema a menudo en Haskell.

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

Sin embargo, estoy confundido .. ¿Por qué esto no comple

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

Si f no se está utilizando en la definición superior, ¿qué otra cosa restringe x para que no pueda satisfacer?

(Editar para intentar responder mejor a la pregunta)

La definición de O bien es:

data Either a b = Left a | Right b

Así que "cualquiera de los dos" toma dos argumentos de tipo. Por cierto, técnicamente "O" no es en realidad un tipo sino un constructor de tipos; toma tipos de argumentos para crear un tipo.

La definición de Functor 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 Functor debe tomar un argumento de tipo. Esto no está declarado; se infiere de "fp" y "fq"; como a "f" se le asigna un parámetro de tipo, debe ser un tipo que tome 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 "O ab" cuando llegue a eso más adelante)

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

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

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

foo x y = ...

y luego diga "foo 2" para obtener una nueva función que espere el segundo argumento, así que puedo decir "O bien" para obtener un nuevo tipo que espera el segundo argumento de tipo.

Ahora mira la instancia original:

instance Functor (Either a) where ....

Entonces aquí "O bien a" es un constructor de tipos que espera un argumento más, al igual que Functor espera de sus instancias. Así que el tipo de "fmap" para "Cualquiera de las dos" será

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

Así que ahora en la cláusula "dónde" tiene que dar una definición de "fmap" que tenga este tipo. El primero que cites tiene este tipo porque el segundo parámetro de tipo se usa para el constructor "Derecho", y ese es al 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.

Aquí está la clase de functor:

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

Tenga en cuenta que "f" en sí mismo es un constructor de tipo porque se aplica a una variable de tipo en la línea fmap. Aquí hay algunos ejemplos para aclarar esto:

Tipo de constructores:

IO Maybe Either String

Tipos:

IO Char Maybe a Either String String

"Maybe a" es un tipo con un constructor de tipo (el "Maybe") y una variable de tipo (la "a"). Aún no es algo concreto, pero se puede usar en firmas de tipo para funciones polimórficas.

"Cualquiera de los dos" es un constructor de tipo que toma dos argumentos de tipo, por lo que incluso después de aplicar uno (por ejemplo, Either String sigue siendo un constructor de tipo porque puede tomar otro argumento de tipo).

El punto de esto es: cuando define una instancia de Functor , el tipo constructor f no puede cambiar. Esto se debe a que está representado por la misma variable, f , como el argumento y el resultado de fmap . El único tipo que puede cambiar es el que se aplica al constructor f .

Cuando escribe la instance Functor (Either c) , Either c se llena para f en todas partes en la declaración de fmap . Esto le da a fmap el siguiente tipo para esta instancia:

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

Con la definición de Either , la única forma útil de obtener este tipo es aplicando el valor Right a la función. Recuerde que "Cualquiera de los dos" tiene dos valores posibles con tipos posiblemente diferentes. Aquí, el valor de la Left tiene el tipo ''c'', por lo que no puede aplicarlo a la función (que espera una ''a'') [1], y el resultado tampoco sería correcto porque se quedaría con Either ba , que no coincide con la definición de la clase.

Después de reemplazar "f" con "O uno c" para obtener la firma de tipo anterior para fmap con la instancia "O uno c", a continuación se escribe la implementación. Hay dos casos a considerar, la izquierda y la derecha. La firma de tipo nos dice que el tipo del lado izquierdo, "c", no puede cambiar. Tampoco tenemos manera de cambiar el valor porque no sabemos qué tipo es en realidad. Todo lo que podemos hacer es dejarlo solo.

fmap f (Left rval) = Left rval

Para el lado derecho, la firma de tipo dice que tenemos que cambiar de un valor con el tipo "a" a un valor con el tipo "b". El primer argumento es una función para hacer exactamente eso, por lo que usamos la función con el valor de entrada para obtener la nueva salida. Poner los dos juntos da la definición completa

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

Hay un principio más general en funcionamiento aquí, por eso es imposible escribir una instancia de Functor que ajuste el lado izquierdo, al menos con las definiciones de Prelude. Copiando algo de código desde arriba:

class Functor f where fmap :: (a -> b) -> f a -> f b instance Functor (Either c) where ...

Aunque tenemos una variable de tipo ''c'' en la definición de instancia, no podemos usarla en ninguno de los métodos de clase porque no se menciona en la definición de clase. Así que no puedes escribir

leftMap :: (c -> d) -> Either c a -> Either d a leftMap mapfunc (Left x) = Left (mapfunc x) leftMap mapfunc (Right x) = Right x instance Functor (Either c) where --fmap :: (c -> d) -> Either c a -> Either d a fmap = leftMap

El resultado de leftMap, y por lo tanto fmap, ahora es (Either d) a . La (Either c) ha cambiado a una (Either d) , pero esto no está permitido porque no hay manera de expresarlo en la clase Functor. Para expresar esto, necesitarías una clase con dos variables de tipo, por ejemplo,

class BiFunctor f where lMap :: (a -> b) -> f a c -> f b c rMap :: (c -> d) -> f a c -> f a d biMap :: (a -> b) -> (c -> d) -> f a c -> f b d

En esta clase, dado que las variables de tipo izquierda y derecha están dentro del alcance, es posible escribir métodos que operen en cualquiera de los lados (o en ambos).

instance BiFunctor Either where lMap = leftMap rMap = rightMap --the same as the standard fmap definition biMap fl fr e = rMap fr (lMap fl e)

Aunque en la práctica la gente normalmente escribe "biMap" para la clase BiFunctor y usa "id" para la otra función si es necesario un mapeo hacia la izquierda o hacia la derecha.

[1] Más precisamente, el valor Izquierdo tiene el tipo ''c'', la función espera una ''a'', pero el verificador de tipos no puede unificar esos tipos porque el tipo ''c'' no está dentro del alcance de la definición de clase.

Arriba funciona porque fmap::(b -> c) -> Either ab -> Either ac y tu -bottom- no funciona porque eso requeriría fmap::(a -> c) -> Either ab -> Either ac . Pero, funcionaría si cambias cualquiera de

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)

Aunque eventualmente me adheriré a su formato, 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)

Debe quedar claro por qué esta instancia funciona. 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 poder ver por qué esto no funciona. El tipo de fmap es Functor f => (a -> b) -> fa -> fb ; 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 fi . Sabemos, debido a la declaración del tipo de datos, que debo ser un Integer , por lo que no podemos aplicarle f . De manera similar, dado que a tiene el tipo a , el Chosen a tendrá el tipo Chosen a , no el tipo Chosen b . Por lo tanto, la instancia de Functor en la parte inferior no puede funcionar.

Bueno, su instancia superior para Either de los Either funciona porque, como en el ejemplo de Choice , obedece a los tipos. Mirémoslo, con algunos renombrados:

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 Functor de los 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 functor, 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 ab . Por lo tanto, lo que hace esta instancia es declarar que Either c es un functor para cualquier c posible. Esa c es fija por la duración de la declaración de instancia. Así que veamos y agreguemos tipos (¡esto no es una 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)

Como f tiene el tipo a -> b , pero el tipo de c se fija en c , no es posible escribir Left (fc) ; e incluso si pudiéramos, queremos que la c quede sola, para que podamos devolver una (Either c) b . Del mismo modo, debemos aplicar f a a para obtener algo de tipo b .

Esta es la razón por la que su 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. Vamos a verlo, de nuevo con las firmas de tipo agregado:

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í, su primera parte de la definición de 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, podemos esperar que (de alguna manera) fc tenga el tipo b , y a tenga el tipo a . En ese caso, estamos devolviendo un valor de tipo Either ba , que aún no está permitido.

Básicamente, el problema proviene de esto. Primero, tenga en cuenta que f es el 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 arreglando c y declarando una instancia para esa c . Esto es cierto para cualquier c , pero solo vemos uno a la vez. Finalmente, debido a esto, el argumento de Left no está parametrizado por el tipo que f espera; Se garantiza tener algún tipo fijo c . Esto significa que (a) no puede aplicarle f , y (b) debe aplicarlo al argumento de Right , ya que de lo contrario no cambiará el tipo que se espera que cambie.

Ehm ... ¿Qué tal unas pocas palabras sobre "tipos"?
Eso puede simplificar la comprensión, supongo.
Recuerda lo que está curry. 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 de ese tipo es * -> * -> * (es decir, toma dos tipos y produce tipo) y cuando dices Either a tipo es * -> * y para Either ab es * (por cierto, Monad a y Functor a requiere a ser de tipo * -> * , como recuerdo). Así que cuando dices "type" Either a significa "type" que todavía está incompleto (requiere que se fmap :: (a -> b) -> fa -> fb algún "argumento"), entonces fmap :: (a -> b) -> fa -> fb convierte en fmap :: (a -> b) -> (Either c) a -> (Either c) b cuando f sustituido por Either c .

Esperemos que esto ayude ...

Primero, sin embargo, algunos antecedentes:

1) Functor necesita un "constructor de tipo", un (bueno, no un tipo en sí, ...) que "necesita" otro tipo regular que se le asigna para formar un "tipo completo", como un genérico en Java / C ++. Entonces, por ejemplo, List es un Functor (es, por cierto), o Array , porque (entre otras cosas) el tipo completo no es solo List , sino List<A> . Entonces,: un Functor toma un "constructor de tipo", un tipo incompleto.

2) Either es un tipo de constructor que la gente de Haskell (léase: Edward Kmett, y otras estrellas estelares bien dotadas de matemáticas) llama bifunctor. Necesita dos tipos dados para ser completo. Por ejemplo, un uso completo de Either es: Either Integer String que significa (sí, sí, "duh!") Es un entero ( Left ) o una cadena ( Right ). Por lo tanto, esto significa que Either Integer es un tipo incompleto que es un Left Integer o un Right...b cuando decides lo que se supone que es "b".

¡Ahora viene la parte divertida!

Las cosas más importantes funcionan porque, fmap usa algún constructor de tipos, y lo usa con una función a a -> b para hacer una función similar de fa a fb - el ejemplo preferido de esto en Haskell es el de listas, también conocido como mapa :: (a -> b) -> ([a] -> [b]) , donde el Functor es la parte [ ] . Ahora, usando algo como Either a (sigamos adelante y usemos Either Integer desde 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 los valores representativos de ese tipo, ya sea de tipo Either Integer a , para obtener un valor de tipo Either Integer b tipo Either Integer b .

Ahora, tu -bottom- no funciona, porque:

Usted tiene una función, f , que toma a s a b s.
Su tipo Left debe ser tipo Integer, y permanecer como Integer (o tipo Float, y permanecer como Float, cualquiera que sea el tipo es el izquierdo de uno de los dos tipos de Either type que está usando).
Su tipo Right debe ser del tipo que tome la función (" a "), y debe ir al tipo que hace la función (" b ").

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

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

Tus ecuaciones dan a fmap los tipos:

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

lo que no solo no se ajusta a lo que fmap quiere, sino que tampoco es coherente entre sí.

Lamento haber escrito medio libro para leerlo, pero espero que eso te ayude a comprenderlo.

Izquierda y Derecha no son tipos, y Left x y Right y son del mismo tipo. Ellos son solo constructores de O bien. Puedes considerar

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

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

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

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

La clase Functor 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 la 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)

Supongamos que tu o 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 fuerza 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 considerando que a , b y c son tipos arbitrarios independientes.

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

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

Si establece el tipo de TypeOperators LANGUAGE , 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 Functor 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 exista una opción de GHC).

En resumen: su comprensión de los funtores está bien, pero la falta de lambdas de nivel de tipo le afecta.

Lo creas o no, esto no es magia. Todo tiene que ver con que el tipo Either ab no sea del mismo tipo que Either ba . 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 es primero, luego b, y también observe que solo incluimos a en la declaración del Functor de cualquiera de los dos:

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

Ahora veamos la definición de Maybe Functor

instance Functor Maybe where fmap = map

Aquí no hay una variable de tipo, aunque Maybe toma un parámetro de tipo (como Maybe Int ). A lo que intento llegar es a que los tipos no son funtores, los constructores de tipos son funtores (los funtores tienen kind *->* ).

Entonces, f :: b -> c , en la versión de Either Functor que funciona, la x desde (Left x) es de tipo a , lo cual está bien, ya que (Either a) es un functor, la x en (Right x) es de tipo b por lo tanto (Right x) es de tipo ((Either a) b) , y (Right (fx)) es de tipo ((Either a) c) , por lo tanto, fmap es de tipo (b->c) -> ((Either a) b) -> ((Either a) c) , según sea necesario.

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

para resumir: el fmap que funciona sale: (b -> c) -> (Either a) b -> (Either a) c , pero el que no funciona sale: (b -> c) -> (Either b) a -> (Either c) a y ese no es el tipo correcto para fmap.

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

Preguntas por qué esto no se compila:

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

Así que intentemos simplificar el problema tratando de definir la misma función sin ponerla como parte de una declaración de instancia de clase:

Eso nos da

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

Que sí 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 obtener un aspecto más uniforme:

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

Eso tiene perfecto sentido. Toma una función y la aplica a la izquierda de una de las dos.

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 f para f en la firma fmap ( fmap nombre de Either a a Either c para evitar que nuestros dos a diferentes se fmap ):

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

¿Ves el problema? Su función es perfectamente válida, simplemente tiene un tipo diferente al que fmap for Either a necesariamente debe tener .

Este es un tipo de cosa hermosa sobre tipos. Dada la firma para fmap , en realidad solo hay una implementación significativa para fmap en O bien a.

A veces, cuando somos afortunados y cuidadosos, podemos terminar en situaciones similares, dada la firma de un tipo, la función casi se escribe sola.

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 Either a simplemente pase por la firma de la función fmap , y cada lugar que vea f , reemplácelo con Either a . Llamaríamos a eso una "especialización" de la firma de tipo fmap. Es decir, es estrictamente menos general que el tipo normal de fmap: en 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 quieras. Simplemente no puede nombrarlo fmap y utilizarlo en una instancia de Functor. Personalmente, lo onLeft algo así como " onLeft o " mapLeft .

Todo lo siguiente puede ser ignorado / es para información, pero no una sugerencia para lecturas futuras en el futuro próximo / uso real:

Si uno quiere ser muy técnico, porque puede mapear tanto el lado izquierdo como el derecho (aunque solo puede declarar Functor para el último), O bien no es solo un Functor, sino un Bifunctor. Esto se proporciona, por ejemplo, en la biblioteca de Categoría-Extras de ekmett (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 más rigurosamente. Puede leer sobre esto aquí: http://lambda-the-ultimate.org/node/1360 . Pero, probablemente no quieras hacerlo, al menos hasta que estés mucho más familiarizado con Haskell. Es una computadora, mathy, investigadora y muy buena, pero no necesaria para entender la programación idiomática de Haskell.