numeración funciones multiplicativas (extraño pero entretenido)

Question

En los comentarios de la cuestión Tacit function composition in Haskell, personas mencionaron haciendo una instancia Num para a -> r, así que pensé que volvería a jugar con el uso de la notación de funciones para representar la multiplicación:

{-# LANGUAGE TypeFamilies #-} 
import Control.Applicative 

instance Show (a->r) where -- not needed in recent GHC versions 
    show f = " a function " 

instance Eq (a->r) where  -- not needed in recent GHC versions 
    f == g = error "sorry, Haskell, I lied, I can't really compare functions for equality" 

instance (Num r,a~r) => Num (a -> r) where 
    (+) = liftA2 (+) 
    (-) = liftA2 (-) 
    (*) = liftA2 (*) 
    abs = liftA abs 
    negate = liftA negate 
    signum = liftA signum 
    fromInteger a = (fromInteger a *) 

Tenga en cuenta que la definición fromInteger significa que puedo escribir 3 4, que evalúa a 12, y 7 (2+8) es 70, exactamente como era de esperar.

¡Entonces todo va maravillosamente, entretenidamente raro! Por favor explicar esto wierdness si puedes:

*Main> 1 2 3 
18 
*Main> 1 2 4 
32 
*Main> 1 2 5 
50 
*Main> 2 2 3 
36 
*Main> 2 2 4 
64 
*Main> 2 2 5 
100 
*Main> (2 3) (5 2) 
600 

[Editar:. Aplicativo utilizado en lugar de mónada porque Aplicativo es grande por lo general, pero no hay mucha diferencia en absoluto al código]

Answer 1

En una expresión como 2 3 4 con sus instancias, tanto 2 como 3 son funciones. Entonces 2 es en realidad (2 *) y tiene un tipo Num a => a -> a. 3 es lo mismo. 2 3 es entonces (2 *) (3 *) que es lo mismo que 2 * (3 *). Por su instancia, esto es liftM2 (*) 2 (3 *) que es entonces liftM2 (*) (2 *) (3 *). Ahora esta expresión funciona sin ninguna de tus instancias.

¿Qué significa esto? Bueno, liftM2 para funciones es una especie de composición doble. En particular, liftM2 f g h es lo mismo que \ x -> f (g x) (h x). Entonces, liftM2 (*) (2 *) (3 *) es \ x -> (*) ((2 *) x) ((3 *) x). Simplificando un poco, obtenemos: \ x -> (2 * x) * (3 * x). Entonces ahora sabemos que 2 3 4 es realmente (2 * 4) * (3 * 4).

Ahora bien, ¿por qué funciona liftM2 para las funciones de esta manera? Veamos el ejemplo de mónada (->) r (tenga en cuenta que es (->) r(r ->) pero no podemos escribir secciones de operador a nivel de tipo):

instance Monad ((->) r) where 
    return x = \_ -> x 
    h >>= f = \w -> f (h w) w 

Así return es const. >>= es un poco raro. Creo que es más fácil ver esto en términos de join. Para las funciones, join funciona así:

join f = \ x -> f x x 

Es decir, se necesita una función de dos argumentos y lo convierte en una función de un argumento mediante el uso de ese argumento dos veces. Suficientemente simple. Esta definición también tiene sentido. Para funciones, join tiene que convertir una función de dos argumentos en una función de uno; la única forma razonable de hacerlo es usar ese único argumento dos veces.

>>= es fmap seguido de join. Para funciones, fmap es solo (.).Así que ahora >>= es igual a:

h >>= f = join (f . h) 

que es justo:

h >>= f = \ x -> (f . h) x x 

ahora sólo deshacerse de . para obtener:

h >>= f = \ x -> f (h x) x 

Así que ahora que sabemos cómo >>= obras , podemos mirar liftM2. liftM2 se define de la siguiente manera:

liftM2 f a b = a >>= \ a' -> b >>= \ b' -> return (f a' b') 

Podemos simplemente esto poco a poco. Primero, return (f a' b') se convierte en \ _ -> f a' b'. Combinado con el \ b' ->, obtenemos: \ b' _ -> f a' b'. Entonces se convierte en b >>= \ b' _ -> f a' b':

\ x -> (\ b' _ -> f a' b') (b x) x 

desde la segunda x se ignora, obtenemos: \ x -> (\ b' -> f a' b') (b x) que después se reduce a \ x -> f a' (b x). Así que esto nos deja con:

a >>= \ a' -> \ x -> f a' (b x) 

Una vez más, sustituimos >>=:

\ y -> (\ a' x -> f a' (b x)) (a y) y 

esto se reduce a:

\ y -> f (a y) (b y) 

que es exactamente lo utilizamos como liftM2 antes!

Esperemos que ahora el comportamiento de 2 3 4 tenga sentido por completo.