Capire `ap` in una funzione priva di punti in Haskell

Question

sono in grado di capire le basi di funzioni senza punto in Haskell:

addOne x = 1 + x 

Come si vede x su entrambi i lati dell'equazione, semplifichiamo iT:

addOne = (+ 1) 

---

Incredibilmente si scopre che funzioni in cui lo stesso argomento viene utilizzato due volte in diverse parti possono essere scritti senza punto!

Colgo come un esempio di base della funzione average scritto come:

average xs = realToFrac (sum xs)/genericLength xs 

può sembrare impossibile per semplificare xs, ma http://pointfree.io/ se ne esce con:

average = ap ((/) . realToFrac . sum) genericLength 

che funziona.

Per quanto ho capito questo afferma che average è lo stesso di chiamare ap su due funzioni, la composizione del (/) . realToFrac . sum e genericLength

Purtroppo la funzione ap ha alcun senso per me, la documentazione http://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:ap Stato:

ap :: Monad m => m (a -> b) -> m a -> m b 

In many situations, the liftM operations can be replaced by uses of ap, 
which promotes function application. 

     return f `ap` x1 `ap` ... `ap` xn 

is equivalent to 

     liftMn f x1 x2 ... xn 

Ma la scrittura:

let average = liftM2 ((/) . realToFrac . sum) genericLength 

non funziona, (dà un messaggio di errore di tipo molto lungo, chiedi e lo includerò), quindi non capisco cosa stanno cercando di dire i documenti.

---

Come funziona l'espressione ap ((/) . realToFrac . sum) genericLength? Potresti spiegare ap in termini più semplici dei documenti?

Answer 1

Quando la monade m è (->) a, come nel tuo caso, è possibile definire ap come segue:

ap f g = \x -> f x (g x) 

Possiamo vedere che questo davvero "funziona" nel tuo esempio pointfree.

average = ap ((/) . realToFrac . sum) genericLength 
average = \x -> ((/) . realToFrac . sum) x (genericLength x) 
average = \x -> (/) (realToFrac (sum x)) (genericLength x) 
average = \x -> realToFrac (sum x)/genericLength x 

Possiamo anche derivare ap dalla legge generale

ap f g = do ff <- f ; gg <- g ; return (ff gg) 

che è, Dezuccheraggio il do -notation

ap f g = f >>= \ff -> g >>= \gg -> return (ff gg) 

Se sostituiamo le definizioni dei metodi monade

m >>= f = \x -> f (m x) x 
return x = \_ -> x 

si ottiene la precedente definizione di ap indietro (per la nostra monade specifica (->) a).Infatti:

app f g 
= f >>= \ff -> g >>= \gg -> return (ff gg) 
= f >>= \ff -> g >>= \gg -> \_ -> ff gg 
= f >>= \ff -> g >>= \gg _ -> ff gg 
= f >>= \ff -> \x -> (\gg _ -> ff gg) (g x) x 
= f >>= \ff -> \x -> (\_ -> ff (g x)) x 
= f >>= \ff -> \x -> ff (g x) 
= f >>= \ff x -> ff (g x) 
= \y -> (\ff x -> ff (g x)) (f y) y 
= \y -> (\x -> f y (g x)) y 
= \y -> f y (g y) 

Answer 2

Qualunque termine lambda può essere riscritta a un termine equivalente che utilizza solo un insieme di adatto combinators e non astrazioni lambda. Questo processo è chiamato abstraciton elimination. Durante il processo si desidera rimuovere le astrazioni lambda dall'interno. Quindi in una fase hai λx.M dove M è già privo di astrazioni lambda e vuoi liberarti di x.

• Se M è x, si sostituisce λx.x con id (id è di solito indicato con I in logica combinatoria).
• Se M non contiene x, si sostituisce il termine con const M (const è di solito indicato con K in logica combinatoria).

• Se M è PQ, che è il termine è λx.PQ, si vuole "spingere" x all'interno di entrambi parti dell'applicazione funzione in modo da poter elaborare in modo ricorsivo entrambe le parti. Ciò si ottiene utilizzando il combinatore S definito come λfgx.(fx)(gx), ovvero, prende due funzioni e passa a x a entrambi e applica i risultati insieme. È possibile verificare facilmente che lo λx.PQ è equivalente a S(λx.P)(λx.Q) e che è possibile elaborare in modo ricorsivo entrambi i sottotemi.

  Come descritto nelle altre risposte, il combinatore S è disponibile in Haskell come ap (o <*>) specializzato per il lettore monade.

L'aspetto della monade lettore non è casuale: Quando si risolve il compito di sostituire λx.M con una funzione equivalente è fondamentalmente sollevamento M :: a al lettore Monade r -> a (in realtà la parte lettore applicativo è sufficiente), dove r è il tipo di x. Se rivediamo il processo di cui sopra:

• L'unico caso che è effettivamente collegato con la monade lettore è quando M è x. Quindi "solleviamo" x a id, per eliminare la variabile. Gli altri casi indicati sono applicazioni solo meccanici di sollevamento un'espressione ad un funtore applicativo:
• L'altro caso in cui λx.MM non contiene x, è solo sollevamento M al applicativa lettore, che è pure M. Infatti, per (->) r, pure equivale a const.
• Nell'ultimo caso, <*> :: f (a -> b) -> f a -> f b è l'applicazione di funzione sollevata su una monade/applicativa. E questo è esattamente quello che facciamo: solleviamo entrambe le parti P e Q al lettore applicativo e quindi utilizziamo <*> per unirle insieme.

Il processo può essere ulteriormente migliorato aggiungendo più combinatori, il che consente di ridurre il termine risultante. Più spesso, combinators B and C are used, che in Haskell corrisponde alle funzioni (.) e flip.E ancora, (.) è solo fmap/<$> per il lettore applicativo. (Io non sono a conoscenza di una tale funzione built-in per esprimere flip, ma sarebbe visto come una specializzazione del f (a -> b) -> a -> f b per l'applicativo lettore.)

_{Qualche tempo fa ho scritto un breve articolo su questo: The Monad Reader Issue 17, The Reader Monad e Abstraction Elimination.}