haskell - ¿Cómo puedo entender "(.).(.) "?

functional-programming pointfree

Question

Creo que entiendo fmap . fmap fmap . fmap para Functors, pero en funciones me duele la cabeza desde hace meses.

He visto que puedes aplicar la definición de (.) (.) . (.) (.) . (.) , pero olvidé cómo hacer eso.
Cuando lo intento, siempre resulta incorrecto:

(.) f g = /x -> f (g x)
(.) (.) (.) = /x -> (.) ((.) x)
/x f -> (.) ((.) x) f
/x f y  -> (((.)(f y)) x)
/x f y g-> (((.)(f y) g) x)
/x f y g-> ((f (g y)) x)
/x f y g-> ((f (g y)) x):: t2 -> (t1 -> t2 -> t) -> t3 -> (t3 -> t1) -> t

Si "solo aplicando la definición" es la única forma de hacerlo, ¿cómo se le ocurrió a alguien (.) . (.) (.) . (.) ?
Debe haber una comprensión o intuición más profunda que me estoy perdiendo.

Answer 1

Entonces, esto es lo que obtengo cuando hago una expansión ligeramente más incremental

(.) f g   = /x -> f (g x)
(.) . g   = /x -> (.) (g x)
          = /x -> /y -> (.) (g x) y
          = /x -> /y -> /z -> (g x) (y z)
          = /x y z -> (g x) (y z)
(.) . (.) = /x y z -> ((.) x) (y z)
          = /x y z -> /k -> x (y z k)
          = /x y z k -> x (y z k)

Que, de acuerdo con ghci tiene el tipo correcto

Prelude> :t (.) . (.)
(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
Prelude> :t /x y z k -> x (y z k)
/x y z k -> x (y z k)
  :: (t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t
Prelude> 

Si bien no conozco los orígenes de este combinador, es probable que haya sido desarrollado para su uso en lógica combinatoria, donde usted trabaja estrictamente con combinadores, por lo que no puede definir cosas utilizando expresiones lambda más convenientes. Puede haber alguna intuición que se relacione con resolver estas cosas, pero no lo he encontrado. Lo más probable es que desarrolles algún nivel de intuición si tienes que hacerlo lo suficiente.

Answer 2

Es más fácil escribir ecuaciones , combinators-style , en lugar de lambda-expressions: abc = (/x -> ... body ...) es equivalente a abcx = ... body ... , y viceversa, siempre que x no aparece entre {a,b,c} . Asi que,

-- _B = (.)  

_B f g x = f (g x)
_B _B _B f g x y = _B (_B f) g x y
                 = (_B f) (g x) y
                 = _B f (g x) y
                 = f ((g x) y)
                 = f (g x y)

Descubres esto si, dado f (gxy) , quieres convertirlo en una forma combinatoria (elimina todos los paréntesis y las repeticiones variables). Luego, aplica los patrones correspondientes a las definiciones de los combinadores, con la esperanza de rastrear esta derivación hacia atrás. Sin embargo, esto es mucho menos mecánico / automático.

Answer 3

Próximamente (.) . (.) (.) . (.) es bastante sencillo, es la intuición detrás de lo que hace que es bastante difícil de entender.

(.) te lleva muy lejos cuando reescribes la expresión en los cálculos de estilo "tubería" (piense | en shell). Sin embargo, resulta incómodo utilizarlo una vez que intentas componer una función que toma múltiples argumentos con una función que solo toma uno. Como ejemplo, tengamos una definición de concatMap :

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat (map f xs)

Deshacerse de xs es solo una operación estándar:

concatMap f = concat . map f

Sin embargo, no hay una forma "agradable" de deshacerse de f . Esto es causado por el hecho de que ese map toma dos argumentos y nos gustaría aplicar concat en su resultado final.

Por supuesto, puede aplicar algunos trucos sin puntos y salirse con la suya (.) :

concatMap f = (.) concat (map f)
concatMap f = (.) concat . map $ f
concatMap = (.) concat . map
concatMap = (concat .) . map

Pero, por desgracia, la legibilidad de este código ha desaparecido en su mayoría. En cambio, presentamos un nuevo combinador, que hace exactamente lo que necesitamos: aplicar la segunda función al resultado final de la primera.

-- .: is fairly standard name for this combinator
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(f .: g) x y = f (g x y)

concatMap = concat .: map

Bien, eso es todo por motivación. Vayamos al negocio sin preocupaciones.

(.:) = /f g x y -> f (g x y)
     = /f g x y -> f ((g x) y)
     = /f g x y -> f . g x $ y
     = /f g x   -> f . g x

Ahora, aquí viene la parte interesante. Este es otro de los trucos sin puntos que usualmente ayudan cuando te quedas atascado: reescribimos . en su forma de prefijo y tratar de continuar desde allí.

     = /f g x   -> (.) f (g x)
     = /f g x   -> (.) f . g $ x
     = /f g     -> (.) f . g
     = /f g     -> (.) ((.) f) g
     = /f       -> (.) ((.) f)
     = /f       -> (.) . (.) $ f
     =             (.) . (.)

En cuanto a la intuición, hay un artículo muy bueno que deberías leer. Parafrasearé la parte sobre (.) :

Pensemos nuevamente en lo que debería hacer nuestro combinador: debería aplicarse f al resultado del resultado de g (he estado usando el resultado final en la parte anterior a propósito, es lo que obtienes cuando aplicas por completo - variables de tipo unificadoras de módulo) con otro tipo de función: la función g , el resultado aquí es solo la aplicación gx para algunos x ).

¿Qué significa para nosotros aplicar f al resultado de g ? Bueno, una vez que apliquemos g a algún valor, tomaremos el resultado y aplicaremos f a él. Suena familiar: eso es lo que (.) Hace.

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

Ahora bien, resulta que la composición (nuestra de palabra) de esos combinadores es simplemente una composición de funciones, es decir:

(.:) = result . result -- the result of result

Answer 4

También puede usar su comprensión de fmap . fmap fmap . fmap

Si tiene dos Functor y bar Functor , entonces

fmap . fmap :: (a -> b) -> foo (bar a) -> foo (bar b)

fmap . fmap fmap . fmap toma una función y produce una función inducida para la composición de los dos Functor .

Ahora, para cualquier tipo t , (->) t es un Functor , y el fmap para ese Functor es (.) .

Entonces (.) . (.) (.) . (.) es fmap . fmap fmap . fmap para el caso donde los dos Functor son (->) s (->) t , y por lo tanto

(.) . (.) :: (a -> b) -> ((->) s) ((->) t a) -> ((->) s) ((->) t b)
          =  (a -> b) -> (s -> (t -> a))     -> (s -> (t -> b))
          =  (a -> b) -> (s -> t -> a)       -> (s -> t -> b)

"compone" una función f :: a -> b con una función de dos argumentos, g :: s -> t -> a ,

((.) . (.)) f g = /x y -> f (g x y)

Esa visión también deja en claro que, y cómo, el patrón se extiende a las funciones que toman más argumentos,

(.) . (.) . (.) :: (a -> b) -> (s -> t -> u -> a) -> (s -> t -> u -> b)

etc.

Answer 5

Tu solución diverge cuando introduces y . Debería ser

/x f y -> ((.) ((.) x) f) y     :: (c -> d) -> (a -> b -> c) -> a -> b -> d
/x f y z -> ((.) ((.) x) f) y z :: (c -> d) -> (a -> b -> c) -> a -> b -> d
/x f y z -> ((.) x (f y)) z     :: (c -> d) -> (a -> b -> c) -> a -> b -> d
-- Or alternately:
/x f y z -> (x . f y) z         :: (c -> d) -> (a -> b -> c) -> a -> b -> d
/x f y z -> (x (f y z))         :: (c -> d) -> (a -> b -> c) -> a -> b -> d

Que coincide con la firma de tipo original: (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

(Es más fácil hacer la expansión en ghci, donde puedes verificar cada paso con :t expression )

Editar:

La intuición más profunda es esta:

(.) simplemente se define como

/f g -> /x -> f (g x)

Que podemos simplificar a

/f g x -> f (g x)

Entonces, cuando le proporcionas dos argumentos, está al curry y todavía necesita otro argumento para resolver. Cada vez que usa (.) Con 2 argumentos, crea una "necesidad" para un argumento más.

(.) . (.) (.) . (.) por supuesto es (.) (.) (.) , así que vamos a expandirlo:

(/f0 g0 x0 -> f0 (g0 x0)) (/f1 g1 x1 -> f1 (g1 x1)) (/f2 g2 x2 -> f2 (g2 x2))

Podemos beta-reducir en f0 y g0 (¡pero no tenemos x0 !):

/x0 -> (/f1 g1 x1 -> f1 (g1 x1)) ((/f2 g2 x2 -> f2 (g2 x2)) x0) 

Sustituye la 2da expresión para f1 ...

/x0 -> /g1 x1 -> ((/f2 g2 x2 -> f2 (g2 x2)) x0) (g1 x1) 

¡Ahora "voltea"! (beta-reducción en f2 ):
Este es el paso interesante - x0 sustituye a f2 - Esto significa que x , que podría haber sido datos, es en cambio una función.
Esto es lo que (.) . (.) (.) . (.) proporciona - la "necesidad" para el argumento adicional.

/x0 -> /g1 x1 -> (/g2 x2 -> x0 (g2 x2)) (g1 x1) 

Esto comienza a verse normal ... Vamos a beta-reducir una última vez (en g2 ):

/x0 -> /g1 x1 -> (/x2 -> x0 ((g1 x1) x2))

Así que nos quedamos simplemente

/x0 g1 x1 x2 -> x0 ((g1 x1) x2)

, donde los argumentos están todavía en orden.