simple Haskell funziona in stile point-free

Question

Sto cercando di capire come convertire le funzioni in notazione point-free in Haskell. Ho visto this example, ma è più complicato di quello che sto cercando. Mi sembra di capire la logica dietro, ma quando sto cercando di eseguire alcuni semplici esempi nel codice, sto ricevendo errori di compilazione. Voglio provare e scrivere questa funzione in stile libero-point:

f x = 5 + 8/x che ho riordinato come f x = (+) 5 $ (/) 8 x

Così, ho pensato che potrebbe essere qualcosa di simile:

f = (+) 5 $ (/) 8 

ma quando corro questo in ghci ricevo questo messaggio:

No instance for (Num (a0 -> a0)) 
    arising from the literal `5' at Test.hs:3:9 
Possible fix: add an instance declaration for (Num (a0 -> a0)) 
In the first argument of `(+)', namely `5' 
In the first argument of `($)', namely `(+) 5' 
In the expression: (+) 5 $ (/) 8 
Failed, modules loaded: none. 

Non capisco il messaggio "Nessuna istanza per ...". Cosa devo fare per scrivere questa funzione in stile point-free?

Answer 1

$ ha una precedenza molto bassa. Quindi, f x = (+) 5 $ (/) 8 x significa in realtà f x = (+) 5 $ ((/) 8 x). Invece, riscrivere che come

f x = (+) 5 ((/) 8 x) 
f x = ((+) 5) (((/) 8) x) 
f x = ((+) 5) . (((/) 8)) x 
f = ((+) 5) . ((/) 8) 
f = (5+) . (8/) 

L'ultima espressione senso: f è la composizione di due operazioni, prima dividere 8 da quello che si ha, e quindi aggiungere 5 al risultato. Ricorda, g.h significa "applica h, quindi applica g il risultato di quello".

Answer 2

Il programma "pointfree" può essere installato con cabal install pointfree, e si mostra come scrivere un'espressione in stile pointfree. Per esempio:

$ pointfree "f x = 5 + 8/x" 
f = (5 +) . (8 /) 

Spiegazione di questa conversione:

1. è possibile utilizzare "sezioni" per le funzioni di infisso/operatore. (a +) == \b -> a + b e (+ a) == \b -> b + a
2. La funzione . prende il risultato del secondo parametro, che è una funzione a un argomento, e lo applica al primo argomento.

Answer 3

Si erano davvero vicino. Mi permetta di aggiungere un altro $ illustrare:

f x = (+) 5 $ (/) 8 $ x 

Dovrebbe essere chiaro che l'espressione (+) 5 è una funzione che accetta un ingresso numerico e produce un output numerico. Lo stesso vale per l'espressione (/) 8. Così si prende qualunque sia il numero è in ingresso, x, e prima applicare la "funzione" (/) 8, e quindi applicare la "funzione" (+) 5.

Ogni volta che si dispone di una catena di funzioni separate da $, è possibile sostituire tutti tranne il più a destra con . Significato, se avete a $ b $ c $ d, questo equivale a a . b . c $ d.

f x = (+) 5 . (/) 8 $ x 

A questo punto, facciamo in realtà rimuovere il $ e parenthesize invece.

f x = ((+) 5 . (/) 8) x 

Ora dovrebbe essere chiaro che è possibile rimuovere il trailing x da entrambi i lati:

f = (+) 5 . (/) 8 

Questo è l'idea principale. Se hai f x = expr x, puoi "eta ridurlo" a f = expr. Per produrre codice pointfree, è sufficiente riconoscere come la funzione più grande è composta da funzioni più piccole. Talvolta l'applicazione parziale è necessaria per il codice senza punti (come in questo caso, (+) 5 e (/) 8 sono parzialmente applicati). Il programma "pointfree" è abbastanza utile per quando non vuoi pensarci; Lambdabot sul canale #haskell irc usa questo programma come un plugin, quindi non devi nemmeno installarlo da solo; basta chiedere:

<DanBurton> @pl let f x = 5 + 8/x in f 
<lambdabot> (5 +) . (8 /) 

Answer 4

conversione da lambda-calcolo (che Haskell è una variante) termini a piste termini (totalmente funzioni pointfree, utilizzando solo const (K), id (I) e <*> (S)) può essere effettuata con le seguenti semplici regole:

1. \x -> x traduce in id;
2. \x -> y senza x che si verifica in tradotto in const y;
3. \x -> f g traduce f' <*> g' dove
   • f' è una definizione di \x -> f e
   • g' è una definizione di \x -> g.

Ora ci si chiede da dove viene il . sono disponibili in C'è un caso particolare dell'ultimo traduzioni:. Se f non ha occorrenze libere di x, poi \x -> f g traduce const f <*> (\x -> g), che è uguale a f . (\x -> g).

Usando queste regole possiamo convertire la vostra funzione:

f = \x -> ((+) 5) (((/) 8) x) = -- by the special-case (.) rule 
((+) 5) . (\x -> (((/) 8) x)) = -- by eta-reduction ((\x -> f x) = f) 
((+) 5) . ((/) 8) 

Eta-riduzione non è necessario per completare la traduzione, ma senza di essa saremmo arrivati ​​qualcosa di Messier. Ad esempio, l'ultimo passaggio produrrebbe invece ((+) 5) . ((/) 8) . id.