sobre - Operador de composición de funciones Haskell de tipo(c → d) →(a → b → c) →(a → b → d)

multiplicar haskell

Question

La composición de la función ordinaria es del tipo

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

Me imagino que esto debería generalizarse a tipos como:

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

Un ejemplo concreto: calcular la diferencia al cuadrado. Podríamos escribir diffsq ab = (a - b) ^ 2 , pero parece que debería ser capaz de componer el (-) y (^2) para escribir algo como diffsq = (^2) . (-) diffsq = (^2) . (-) .

No puedo, por supuesto. Una cosa que puedo hacer es usar una tupla en lugar de dos argumentos para (-) , transformándola con uncurry , pero esto no es lo mismo.

¿Es posible hacer lo que quiero? Si no, ¿qué estoy malinterpretando que me hace pensar que debería ser posible?

Nota: Esto ya se ha preguntado here , pero la respuesta (que sospecho que debe existir) no se dio.

Answer 1

Como Max señaló en un comment :

diffsq = ((^ 2) .) . (-)

Puedes pensar en f . g f . g como aplicar un argumento a g , y luego pasar el resultado a f . (f .) . g (f .) . g aplica dos argumentos a g , luego pasa el resultado a f . ((f .) .) . g ((f .) .) . g aplica tres argumentos a g , y así sucesivamente.

/f g -> (f .) . g :: (c -> d) -> (a -> b -> c) -> a -> b -> d

Si dejamos la sección del operador de composición con alguna función f :: c -> d (aplicación parcial con f a la izquierda), obtenemos:

(f .) :: (b -> c) -> b -> d

Entonces tenemos esta nueva función que espera una función de b -> c , pero nuestra g es a -> b -> c , o equivalentemente, a -> (b -> c) . Necesitamos aplicar una a antes de que podamos obtener lo que necesitamos. Bueno, iteremos una vez más:

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

Answer 2

El malentendido es que piensas en una función de tipo a -> b -> c como una función de dos argumentos con el tipo de retorno c , mientras que de hecho es una función de un argumento con el tipo de retorno b -> c porque el tipo de función se asocia a la derecha (es decir, es lo mismo que a -> (b -> c) . Esto hace que sea imposible usar el operador de composición de funciones estándar.

Para ver por qué, intente aplicar el operador (.) Que es del operador de tipo (y -> z) -> (x -> y) -> (x -> z) a dos funciones, g :: c -> d f :: a -> (b -> c) . Esto significa que debemos unificar y con c y también con b -> c . Esto no tiene mucho sentido. ¿Cómo puede ser y ser c y una función que devuelve c ? Eso debería ser un tipo infinito. Entonces esto no funciona.

El hecho de que no podamos usar el operador de composición estándar no nos impide definir el nuestro.

 compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
 compose2 g f x y = g (f x y)

 diffsq = (^2) `compose2` (-)

Por lo general, es mejor evitar el uso de estilo sin puntos en este caso y simplemente seguir con

 diffsq a b = (a-b)^2

Answer 3

Esto es lo que creo que es una forma elegante de lograr lo que quieres. La clase de tipo Functor proporciona una forma de ''empujar'' una función hacia abajo en un contenedor para que pueda aplicarla a cada elemento usando fmap . Puede pensar en una función a -> b como un contenedor de b s con cada elemento indexado por un elemento de a . Entonces, es natural hacer esta instancia:

instance Functor ((->) a) where
  fmap f g = f . g

(Creo que puede obtenerlo import una biblioteca adecuada pero no recuerdo cuál).

Ahora la composición habitual de f con g es trivialmente un fmap :

o1 :: (c -> d) -> (b -> c) -> (b -> d)
f `o1` g = fmap f g

Una función de tipo a -> b -> c es un contenedor de contenedores de elementos de tipo c . Entonces, necesitamos presionar nuestra función f hacia abajo dos veces. Aqui tienes:

o2 :: (c -> d) -> (a -> (b -> c)) -> a -> (b -> d)
f `o2` g = fmap (fmap f) g

En la práctica, es posible que no necesite o1 o o2 , solo fmap . Y si puede encontrar la biblioteca cuya ubicación he olvidado, puede encontrar que puede usar fmap sin fmap ningún código adicional.

Answer 4

Iba a escribir esto en un comentario, pero es un poco largo, y se basa en mightybyte y hammar.

Sugiero que estandaricemos operadores como .* Para compose2 y .** para compose3 . Usando la definición de mightybyte:

(.*) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
(.*) = (.) . (.)

(.**) :: (d -> e) -> (a -> b -> c -> d) -> (a -> b -> c -> e)
(.**) = (.) . (.*)

diffsq :: (Num a) => a -> a -> a
diffsq = (^2) .* (-)

modminus :: (Integral a) => a -> a -> a -> a
modminus n = (`mod` n) .* (-)

diffsqmod :: (Integral a) => a -> a -> a -> a
diffsqmod = (^2) .** modminus

Sí, modminus y diffsqmod son diffsqmod muy aleatorias e inútiles, pero fueron rápidas y muestran el punto. Observe cuán inquietantemente fácil es definir el siguiente nivel componiendo en otra función de fmap (similar a los fmap encadenamiento mencionados por Edward).

(.***) = (.) . (.**)

En una nota práctica, desde compose12 hacia arriba es más corto escribir el nombre de la función en lugar del operador

f .*********** g
f `compose12` g

Aunque contar asteriscos es agotador, es posible que deseemos detener la convención en 4 o 5.

[edit] Otra idea aleatoria, podríamos usar .: para compose2, .:. para compose3,. .:: para compose4,. .::. para compose5,. .::: para compose6, dejando que el número de puntos (después del inicial) marque visualmente la cantidad de argumentos para desglosar. Aunque creo que me gustan más las estrellas.

Answer 5

Mi implementación preferida para esto es

fmap . fmap :: (Functor f, Functor f1) => (a -> b) -> f (f1 a) -> f (f1 b)

Si solo porque es bastante fácil de recordar.

Al crear instancias de f y f1 a (->) c y (->) d respectivamente, obtienes el tipo

(a -> b) -> (c -> d -> a) -> c -> d -> b

cual es el tipo de

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

pero es un poco más fácil recitar el fmap . fmap fmap . fmap versión fmap . fmap y se generaliza a otros funtores.

Algunas veces esto se escribe fmap fmap fmap , pero escrito como fmap . fmap fmap . fmap puede expandirse más fácilmente para permitir más argumentos.

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

fmap . fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h, Functor i) => (a -> b) -> f (g (h (i a))) -> f (g (h (i b))

etc.

¡En general, fmap compuesto consigo mismo n veces puede usarse para fmap n niveles profundos!

Y dado que las funciones forman un Functor , esto proporciona plomería para n argumentos.

Para obtener más información, consulte los Combinators del editor semántico de Conal Elliott.

Answer 6

No sé de una función de biblioteca estándar que hace esto, pero el patrón sin puntos que lo logra es componer la función de composición:

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