Numeri come funzioni moltiplicative (strano ma divertente)

Question

Nei commenti della questione Tacit function composition in Haskell, le persone menzionate fare un esempio Num per a -> r, così ho pensato di giocare con la notazione utilizzando la funzione di rappresentare la moltiplicazione:

{-# 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 *) 

Si noti che la definizione fromInteger significa che è possibile scrivere 3 4 che restituisce 12, e 7 (2+8) è 70, proprio come si spera.

Quindi tutto va meravigliosamente, divertente stranamente! Si prega di spiegare questo wierdness se potete:

*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 

[Edit:. Utilizzato applicativo invece di Monade perché applicativo è grande generale, ma non fa molta differenza a tutti per il codice]

Answer 1

In un espressione come 2 3 4 con le tue istanze, sia 2 sia 3 sono funzioni. Quindi 2 è in realtà (2 *) e ha un tipo Num a => a -> a. 3 è lo stesso. 2 3 è quindi (2 *) (3 *) che corrisponde a 2 * (3 *). Con la tua istanza, questo è liftM2 (*) 2 (3 *) che è quindi liftM2 (*) (2 *) (3 *). Ora questa espressione funziona senza nessuna delle tue istanze.

Che cosa significa? Bene, liftM2 per le funzioni è una sorta di doppia composizione. In particolare, liftM2 f g h corrisponde a \ x -> f (g x) (h x). Quindi liftM2 (*) (2 *) (3 *) è quindi \ x -> (*) ((2 *) x) ((3 *) x). Semplificando un po ', otteniamo: \ x -> (2 * x) * (3 * x). Quindi ora sappiamo che 2 3 4 è in realtà (2 * 4) * (3 * 4).

Ora, perché le funzioni di liftM2 funzionano in questo modo? Diamo un'occhiata ad istanza Monade per (->) r (tenere a mente che è (->) r(r ->) ma non possiamo scrivere sezioni operatore tipo-livello):

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

Così return è const. >>= è un po 'strano. Penso che sia più facile vederlo in termini di join. Per le funzioni, join funziona così:

join f = \ x -> f x x 

Cioè, si prende una funzione di due argomenti e la trasforma in una funzione di un argomento utilizzando tale argomento due volte. Abbastanza semplice Anche questa definizione ha senso. Per le funzioni, join deve trasformare una funzione di due argomenti in una funzione di uno; l'unico modo ragionevole per farlo è usare quell'argomento due volte.

>>= è fmap seguito da join. Per le funzioni, fmap è solo (.).Così ora >>= è pari a:

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

che è solo:

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

ora dobbiamo solo liberiamo di . per ottenere:

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

Quindi, ora che sappiamo come >>= opere , possiamo guardare a liftM2. liftM2 è definito come segue:

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

possiamo semplicemente questo a poco a poco. Innanzitutto, return (f a' b') diventa \ _ -> f a' b'. In combinazione con lo \ b' ->, otteniamo: \ b' _ -> f a' b'. Poi b >>= \ b' _ -> f a' b' si trasforma in:

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

a partire dalla seconda x viene ignorato, otteniamo: \ x -> (\ b' -> f a' b') (b x) che viene poi ridotto a \ x -> f a' (b x). Quindi questo ci lascia con:

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

Ancora una volta, sostituiamo >>=:

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

questo si riduce a:

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

che è esattamente quello che abbiamo usato come liftM2 prima!

Speriamo ora che il comportamento di 2 3 4 abbia senso.