haskell - example - Composing function composition: ¿Cómo funciona(.).(.)?
curry haskell example (7)
(.) toma dos funciones que toman un valor y devuelven un valor:
(.) :: (b -> c) -> (a -> b) -> a -> c
Como (.) Toma dos argumentos, siento que (.).(.) Debería ser inválido, pero está perfectamente bien:
(.).(.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
¿Que esta pasando aqui? Me doy cuenta de que esta pregunta está mal redactada ... todas las funciones realmente solo toman un argumento gracias al currying. Quizás una mejor manera de decirlo es que los tipos no coinciden.
Aquí hay un ejemplo más simple del mismo fenómeno:
id :: a -> a
id x = x
El tipo de identificación dice que la identificación debe tomar un argumento. Y de hecho, podemos llamarlo con un argumento:
> id "hello"
"hello"
Pero resulta que también podemos llamarlo con dos argumentos:
> id not True
False
O incluso:
> id id "hello"
"hello"
Que esta pasando? La clave para entender el id not True es id not True es primero ver el id not . Claramente, eso está permitido, porque aplica id a un argumento. El tipo de not es Bool -> Bool , entonces sabemos que el a del tipo de id debe ser Bool -> Bool , entonces sabemos que esta ocurrencia de id tiene el tipo:
id :: (Bool -> Bool) -> (Bool -> Bool)
O, con menos paréntesis:
id :: (Bool -> Bool) -> Bool -> Bool
Entonces esta ocurrencia de identificación en realidad toma dos argumentos .
El mismo razonamiento también funciona para id id "hello" y (.) . (.) (.) . (.) .
Este es uno de esos casos claros en los que creo que es más fácil captar primero el caso más general y luego pensar en el caso específico. Así que pensemos en funtores. Sabemos que los funtores proporcionan una forma de mapear funciones sobre una estructura:
class Functor f where
fmap :: (a -> b) -> f a -> f b
Pero, ¿y si tenemos dos capas del functor? Por ejemplo, una lista de listas? En ese caso, podemos usar dos capas de fmap
>>> let xs = [[1,2,3], [4,5,6]]
>>> fmap (fmap (+10)) xs
[[11,12,13],[14,15,16]]
Pero el patrón f (gx) es exactamente el mismo que (f . g) x para que podamos escribir
>>> (fmap . fmap) (+10) xs
[[11,12,13],[14,15,16]]
¿Cuál es el tipo de fmap . fmap fmap . fmap ?
>>> :t fmap.fmap
:: (Functor g, Functor f) => (a -> b) -> f (g a) -> f (g b)
Vemos que se asigna más de dos capas de functor, como queríamos. Pero ahora recuerde que (->) r es un funtor (el tipo de funciones de r , que usted podría preferir leer como (r ->) ) y su instancia del funtor es
instance Functor ((->) r) where
fmap f g = f . g
Para una función, ¡ fmap es solo composición de funciones! Cuando fmap dos fmap dos niveles del functor de función. Inicialmente tenemos algo de tipo (->) s ((->) ra) , que es equivalente a s -> r -> a , y terminamos con algo de tipo s -> r -> b , por lo que el tipo de (.).(.) debe ser
(.).(.) :: (a -> b) -> (s -> r -> a) -> (s -> r -> b)
que toma su primera función y la usa para transformar la salida de la segunda función (dos argumentos). Entonces, por ejemplo, la función ((.).(.)) show (+) es una función de dos argumentos, que primero agrega sus argumentos y luego transforma el resultado en una String usando show :
>>> ((.).(.)) show (+) 11 22
"33"
Entonces hay una generalización natural para pensar en cadenas más largas de fmap , por ejemplo
fmap.fmap.fmap ::
(Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))
que mapea tres capas de functor, lo que equivale a componer con una función de tres argumentos:
(.).(.).(.) :: (a -> b) -> (r -> s -> t -> a) -> (r -> s -> t -> b)
por ejemplo
>>> import Data.Map
>>> ((.).(.).(.)) show insert 1 True empty
"fromList [(1,True)]"
que inserta el valor True en un mapa vacío con la clave 1 , y luego convierte la salida en una cadena con show .
Estas funciones pueden ser útiles en general, por lo que a veces las ve definidas como
(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(.:) = (.).(.)
para que puedas escribir
>>> let f = show .: (+)
>>> f 10 20
"30"
Por supuesto, se puede dar una definición más simple y significativa de (.:)
(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(f .: g) x y = f (g x y)
que puede ayudar a desmitificar (.).(.) alguna manera.
Primero juguemos typechecker para la prueba mecánica. Describiré una forma intuitiva de pensarlo después.
Quiero aplicar (.) (.) Y luego aplicaré (.) resultado. La primera aplicación nos ayuda a definir algunas equivalencias de variables.
((.) :: (b -> c) -> (a -> b) -> a -> c)
((.) :: (b'' -> c'') -> (a'' -> b'') -> a'' -> c'')
((.) :: (b'''' -> c'''') -> (a'''' -> b'''') -> a'''' -> c'''')
let b = (b'' -> c'')
c = (a'' -> b'') -> a'' -> c''
((.) (.) :: (a -> b) -> a -> c)
((.) :: (b'''' -> c'''') -> (a'''' -> b'''') -> a'''' -> c'''')
Entonces comenzamos el segundo, pero nos atascamos rápidamente ...
let a = (b'''' -> c'''')
Esta es la clave: queremos let b = (a'''' -> b'''') -> a'''' -> c'''' , pero ya definimos b , por lo que debemos intentar unificar --- para hacer coincidir nuestras dos definiciones lo mejor que podamos Afortunadamente, hacen juego
UNIFY b = (b'' -> c'') =:= (a'''' -> b'''') -> a'''' -> c''''
which implies
b'' = a'''' -> b''''
c'' = a'''' -> c''''
y con esas definiciones / unificaciones podemos continuar la aplicación
((.) (.) (.) :: (b'''' -> c'''') -> (a'' -> b'') -> (a'' -> c''))
luego expandir
((.) (.) (.) :: (b'''' -> c'''') -> (a'' -> a'''' -> b'''') -> (a'' -> a'''' -> c''''))
y limpiarlo
substitute b'''' -> b
c'''' -> c
a'' -> a
a'''' -> a1
(.).(.) :: (b -> c) -> (a -> a1 -> b) -> (a -> a1 -> c)
lo cual, para ser honesto, es un resultado poco intuitivo.
Aquí está la intuición. Primero eche un vistazo a fmap
fmap :: (a -> b) -> (f a -> f b)
"levanta" una función en un Functor . Podemos aplicarlo repetidamente
fmap.fmap.fmap :: (Functor f, Functor g, Functor h)
=> (a -> b) -> (f (g (h a)) -> f (g (h b)))
permitiéndonos elevar una función a capas cada vez más profundas de Functors .
Resulta que el tipo de datos (r ->) es un Functor .
instance Functor ((->) r) where
fmap = (.)
que debería verse bastante familiar. Esto significa que fmap.fmap traduce a (.).(.) . Por lo tanto, (.).(.) Solo nos permite transformar el tipo paramétrico de capas más y más profundas del Funcionador (r ->) . El (r ->) Functor es realmente el Reader Monad , por lo que Reader s en capas es como tener múltiples tipos independientes de estado global e inmutable.
O como tener múltiples argumentos de entrada que no estén siendo afectados por el fmap . Más o menos como componer una nueva función de continuación en "solo el resultado" de una función (> 1) arity.
Finalmente, vale la pena señalar que si crees que esto es interesante, forma la intuición central detrás de la obtención de lentes en control.Lens .
Sí, esto se debe al currying. (.) ya que todas las funciones en Haskell solo toman un argumento. Lo que estás componiendo es la primera llamada parcial a cada compuesto respectivo (.) Que toma su primer argumento (la primera función de la composición).
Tienes razón, (.) Solo toma dos argumentos. Parece confundirse con la sintaxis de Haskell. En la expresión (.).(.) , De hecho es el punto en el medio que toma los otros dos puntos como argumento, al igual que en la expresión 100 + 200 , que se puede escribir como (+) 100 200 .
(.).(.) === (number the dots)
(1.)2.(3.) === (rewrite using just syntax rules)
(2.)(1.)(3.) === (unnumber and put spaces)
(.) (.) (.) ===
Y debería ser aún más claro desde (.) (.) (.) Que el primero (.) Toma el segundo (.) Y el tercero (.) Como sus argumentos.
Vamos a ignorar los tipos por un momento y solo usaremos el cálculo lambda.
Notación de infijo Desugar:
(.) (.) (.)Eta-expand:
(/ ab -> (.) ab) (/ cd -> (.) cd) (/ ef -> (.) ef)Inline la definición de
(.):
(/ abx -> a (bx)) (/ cdy -> c (dy)) (/ efz -> e (fz))Sustituir
a:
(/ bx -> (/ cdy -> c (dy)) (bx)) (/ efz -> e (fz))Sustituto
b:
(/ x -> (/ cdy -> c (dy)) ((/ efz -> e (fz)) x))Sustituto
e:
(/ x -> (/ cdy -> c (dy)) (/ fz -> x (fz)))csuplente:
(/ x -> (/ dy -> (/ fz -> x (fz)) (dy)))Substitute
f:
(/ x -> (/ dy -> (/ z -> x (dyz))))Nota de Resgna lambda:
/ xdyz -> x (dyz)
Y si le preguntas a GHCi, encontrarás que tiene el tipo esperado. ¿Por qué? Debido a que la flecha de la función es asociativa a la derecha para soportar currying: el tipo (b -> c) -> (a -> b) -> a -> c realmente significa (b -> c) -> ((a -> b) -> (a -> c)) . Al mismo tiempo, la variable de tipo b puede representar cualquier tipo, incluido un tipo de función . Ver la conexión?
(Primero lee mi respuesta sobre la composición de la función, $ operador y estilo sin puntos).
Imagine que tiene una función simple: suma 2 números y luego niega el resultado. Lo llamaremos foo :
foo a b = negate (a + b)
Ahora vamos a dejarlo sin puntos paso a paso y ver con qué terminamos:
foo a b = negate $ a + b
foo a b = negate $ (+) a b
foo a b = negate $ (+) a $ b
foo a b = negate . (+) a $ b
foo a = negate . (+) a -- f x = g x is equivalent to f = g
foo a = (.) negate ((+) a) -- any infix operator is just a function
foo a = (negate.) ((+) a) -- (2+) is the same as ((+) 2)
foo a = (negate.) $ (+) a
foo a = (negate.) . (+) $ a
foo = (negate.) . (+)
foo = ((.) negate) . (+)
foo = (.) ((.) negate) (+) -- move dot in the middle in prefix position
foo = ((.) ((.) negate)) (+) -- add extra parentheses
Ahora analicemos la expresión (.) ((.) negate) más de cerca. Es una aplicación parcial de la función (.) , Cuyo primer argumento es ((.) negate) . ¿Podemos transformarlo aún más? Si podemos:
(.) ((.) negate)
(.) . (.) $ negate -- because f (f x) is the same as (f . f) x
(.)(.)(.) $ negate
((.)(.)(.)) negate
(.).(.) es equivalente a (.)(.)(.) , porque en la primera expresión, el punto en el medio se puede mover en posición de prefijo y rodeado de paréntesis, lo que da lugar a la segunda expresión.
Ahora podemos reescribir nuestra función foo :
foo = ((.).(.)) negate (+)
foo = ((.)(.)(.)) negate (+) -- same as previous one
foo = negate .: (+)
where (.:) = (.).(.)
Ahora sabes que (.).(.) Es equivalente a (/fgxy -> f (gxy)) :
(/f g x y -> f (g x y)) negate (+) 2 3 -- returns -5
((.).(.)) negate (+) 2 3 -- returns -5