Lambda/comprensione concettuale della funzione anonima

Question

Sto cercando di capire e comprendere il design di Haskell. Sono attualmente in funzione Lambda/Anonimo e mi stavo chiedendo.

Perché le istanze dei tipi di funzione della classe Eq non sono?

Prelude> (\z -> z+5) == (+5) 

In questa domanda, mi chiedevo se è perché z può essere qualsiasi cosa e può essere ancora essere una variabile libera, in tutte le funzioni lambda, quindi sarebbe un difetto di progettazione per rendere le funzioni lambda di tipo Eq .

Perché le istanze dei tipi di funzione della classe di tipo Mostra?

Prelude> (\q -> q-2) 

Apprezzo qualsiasi chiarimento.

Molte grazie in anticipo!

Answer 1

Sono queste funzioni lo stesso o sono differenti:

dbl1 :: Int -> Int 
dbl1 x = x + x 

dbl2 :: Int -> Int 
dlb2 x = 2 * x 

?

Per alcune funzioni è "facile" per il compilatore vedere che contengono la stessa logica. Ma la maggior parte delle funzioni sarebbe estremamente difficile da confrontare. Poi ci sono funzioni che sono logicamente diverse, ma si comportano allo stesso modo - come dbl1 e dbl2 sopra. Quindi, dovresti fare una scelta per testarli contro ogni possibile valore, o decidere che non sono uguali. Il primo è completamente poco pratico nella maggior parte dei casi. Quest'ultimo non è sicuramente desiderabile o intuitivo. Ora, considera che il problema è già troppo difficile da risolvere, quindi getta IO ...

Answer 2

Gödel's incompleteness theorems implica che qualsiasi istanza Eq per le funzioni deve fornire risultati inaccurati o talvolta restituire ⊥. Questo non è quello che ci aspettiamo dalle istanze Eq (almeno per i dati limitati).

show deve fornire il codice sorgente Haskell che valuta il suo input. Questo è scomodo quando si compila un programma Haskell, perché ora è necessario conservare una copia del codice sorgente per ogni funzione, gonfiando l'eseguibile, anche se l'istanza Show per le funzioni non viene mai utilizzata.

È possibile fornire un'istanza Show per le funzioni che infrange questa regola, ad es. restituendo sempre "{-function-}" o (per alcuni tipi) restituendo il tipo di funzione. Le prime versioni di Haskell lo fecero. Ma si è ritenuto che rompere questa regola non fosse una buona idea.

Answer 3

Un concetto critico che ritengo né Dave né Peter abbiano sottolineato abbastanza: due funzioni sono uguali se e solo se (a) hanno lo stesso tipo, e (b) per ogni possibile argomento che puoi dare loro, entrambi producono lo stesso risultato.

Ora, con questo chiaro, la risposta per Eq è proprio quello che hanno detto. Peter sottolinea che un'istanza Eq per le funzioni dovrebbe essere in grado di analizzare due funzioni arbitrarie e determinare correttamente se producono lo stesso risultato per due input. E come sottolinea Dave, questo è in realtà matematicamente impossibile; qualsiasi correttore che ha provato a confrontare funzioni arbitrarie fallirà per alcune funzioni, il che significa che si bloccherà o produrrà una risposta errata per alcuni casi.

vedrete programmatori Haskell parlare di parità di funzioni per tutto il tempo, però, ma la maggior parte del tempo il loro significato è che gli esseri umani hanno dimostrato che alcune due funzioni sono uguali. Ad esempio, l'operatore composizione funzione è definita in questo modo:

(.) :: (b -> c) -> (a -> b) -> (a -> c) 
f . g = \x -> f (g x) 

Possiamo ora dimostrare che per ogni possibile h :: c -> d, g :: b -> c e h :: a -> b, f . (g . h) == (f . g) . h. E 'abbastanza facile in questo caso, abbiamo semplicemente ampliare l'espressioni secondo la definizione di (.), e noi ottenere la stessa cosa per entrambi:

f . (g . h) = f . (\y -> g (h y))   -- expand `g . h` by definition 
      = \x -> f ((\y -> g (h y)) x) -- expand `f . (\y -> g (h y))` 
      = \x -> f (g (h x))   -- apply the inner lambda 

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

Ma questo può essere fatto solo per le funzioni scelti con cura, e computer in genere può Fallo bene o in modo affidabile. Per ogni programma che scrivi per provare e testare l'uguaglianza delle funzioni arbitrarie, ci saranno alcune funzioni per le quali produrranno la risposta sbagliata o il ciclo per sempre.

Answer 4

Mi piacciono le risposte di tutti ... sembrano avere un senso. Non immaginerei, in questa fase, di rispondere perché le funzioni non sono impostate di default come istanze di Eq e Show. Questa è solo una sperimentazione che potrebbe darti delle idee per provarlo tu stesso:

Prelude> :set -XFlexibleInstances 
Prelude> instance Eq (Int -> Int) where x == y = map x [0..10] == map y [0..10] 
Prelude> ((\z -> z+5) :: Int -> Int) == ((+5) :: Int -> Int) 
True 
Prelude> instance Show (Int -> Int) where show x = show (zip [0..10] (map x [0..10])) 
Prelude> (\q -> q-2) :: (Int -> Int) 
[(0,-2),(1,-1),(2,0),(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7),(10,8)]