applicazione Haskell funzione e strigliare

Question

Sono sempre interessato a imparare nuove lingue, un fatto che mi tiene sulle dita dei piedi e me (credo) un programmatore migliore fa. I miei tentativi di conquistare Haskell vanno e vengono, due volte finora, e ho deciso che era ora di provare di nuovo. Il 3 ° tempo è il fascino, giusto?

No. Rileggo i miei vecchi appunti ... e rimango deluso :-(

Il problema che mi ha fatto perdere la fiducia l'ultima volta, è stato facile: permutazioni di numeri interi cioè da un elenco di numeri interi, a un elenco delle liste - un elenco dei loro permutazioni:

[int] -> [[int]] 

Questo è infatti un problema generico, in modo che sostituiscono 'int' di cui sopra con 'a', si applicherebbe comunque

dai miei appunti:

.

Lo codice prima da solo, ci riesco. Evviva!

Invio la mia soluzione a un mio buon amico - Haskell guru, di solito aiuta a imparare dai guru - e mi invia questo, che mi è stato detto, "esprime il vero potere della lingua, l'uso del generico strutture per codificare le tue esigenze ". Tutto per esso, di recente ho bevuto il Kool-Aid, andiamo:

permute :: [a] -> [[a]] 
permute = foldr (concatMap.ins) [[]] 
    where ins x []  = [[x]] 
     ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys] 

Hmm. Rompiamo questo in giù:

bash$ cat b.hs 
ins x []  = [[x]] 
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys] 

bash$ ghci 
Prelude> :load b.hs 
[1 of 1] Compiling Main    (b.hs, interpreted) 
Ok, modules loaded: Main. 

*Main> ins 1 [2,3] 
[[1,2,3],[2,1,3],[2,3,1]] 

OK, così qui, tutto bene. Mi ci volle un minuto per capire la seconda linea di "ins", ma OK: Essa pone la prima arg in tutte le possibili posizioni nella lista. Freddo.

Ora, per capire il foldr e concatMap. nel "mondo reale Haskell", il DOT è stato spiegato ...

(f . g) x 

... come un altro sintassi per ...

f (g x) 

E nel codice il guru ha inviato, DOT è stato utilizzato da un foldr, con la funzione "ins", come la piega "collasso":

*Main> let g=concatMap . ins 
*Main> g 1 [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

OK, perché voglio capire come il DOT è utilizzato dal guru, provo l'espressione equivalente secondo la definizione DOT , (f g) x = f (gx) ...

*Main> concatMap (ins 1 [[2,3]]) 

<interactive>:1:11: 
    Couldn't match expected type `a -> [b]' 
      against inferred type `[[[t]]]' 
    In the first argument of `concatMap', namely `(ins 1 [[2, 3]])' 
    In the expression: concatMap (ins 1 [[2, 3]]) 
    In the definition of `it': it = concatMap (ins 1 [[2, 3]]) 

Cosa!?! Perché? OK, verifico la firma di concatMap, e scoprire che ha bisogno di un lambda e una lista, ma questo è solo un pensiero umano; come fa GHC a far fronte? Secondo la definizione di DOT sopra ...

(f.g)x = f(g x), 

... quello che ho fatto era valido, sostituire-saggio:

(concatMap . ins) x y = concatMap (ins x y) 

graffia testa ...

*Main> concatMap (ins 1) [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

Così ...La spiegazione DOT era apparentemente troppo semplicistica ... DOT deve essere abbastanza intelligente per capire che in realtà volevamo "ins" per allontanarci e "mangiare" il primo argomento - diventando così una funzione che vuole solo operare su [t] (e "intersponderli" con "1" in tutte le posizioni possibili).

Ma dove è stato specificato? Come ha fatto GHC sapeva di fare questo, quando abbiamo invocato:

*Main> (concatMap . ins) 1 [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

ha fatto la firma "ins" in qualche modo convogliata questo ... "mangiare il mio primo argomento" politica?

*Main> :info ins 
ins :: t -> [t] -> [[t]]  -- Defined at b.hs:1:0-2 

Non vedo niente di speciale - "ins" è una funzione che prende un 't', un elenco di 't', e procede a creare una lista con tutte le "interspersals". Niente su "mangia la tua prima discussione e mangiala via".

Quindi ... sono sconcertato. Capisco (dopo un'ora di osservazione del codice!) Cosa succede, ma ... Dio onnipotente ... Forse GHC fa dei tentativi per vedere quanti argomenti può "staccare"?

let's try with no argument "curried" into "ins", 
    oh gosh, boom, 
    let's try with one argument "curried" into "ins", 
    yep, works, 
    that must be it, proceed) 

Ancora una volta - yikes ...

E siccome sono sempre confrontando le lingue che sto imparando con quello che so già, come sarebbe "ins" guardare in Python?

a=[2,3] 
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)] 

[[1, 2, 3], [2, 1, 3], [2, 3, 1]] 

Sii onesto, ora ... che è più semplice?

Voglio dire, so di essere un principiante in Haskell, ma mi sento un idiota ... Guardando 4 righe di codice per un'ora, e finendo per assumere che il compilatore ... prova varie interpretazioni fino a quando trova qualcosa che "fa clic"?

citare arma letale: "Sono troppo vecchio per questo" ...

Answer 1

(f . g) x = f (g x) 

Questo è vero. Lei ha concluso che

(f . g) x y = f (g x y) 

deve anche essere vero, ma questo non è il caso. In effetti, è vero il seguente:

(f . g) x y = f (g x) y 

che non è la stessa cosa.

Perché è vero? Bene (f . g) x y è lo stesso di ((f . g) x) y e poiché sappiamo che (f . g) x = f (g x) possiamo ridurlo a (f (g x)) y, che è ancora lo stesso di f (g x) y.

Quindi (concatMap . ins) 1 [[2,3]] è equivalente a concatMap (ins 1) [[2,3]]. Non c'è magia che sta succedendo qui.

Un altro modo per affrontare questo è tramite i tipi:

. ha il tipo (b -> c) -> (a -> b) -> a -> c, concatMap ha il tipo (x -> [y]) -> [x] -> [y], ins ha il tipo t -> [t] -> [[t]].Quindi, se usiamo concatMap come argomento b -> c e ins come argomento a -> b, quindi a diventa t, b diventa [t] -> [[t]] e c diventa [[t]] -> [[t]] (con x = [t] e y = [t]).

Quindi il tipo di concatMap . ins è t -> [[t]] -> [[t]], che significa una funzione che accetta un qualunque e un elenco di elenchi (di whatevers) e restituisce un elenco di elenchi (dello stesso tipo).

Answer 2

Vorrei aggiungere i miei due centesimi. La domanda e la risposta fanno sembrare che . sia un operatore magico che fa cose strane con la ri-organizzazione delle chiamate di funzione. Questo non è il caso. . è solo la composizione delle funzioni. Ecco un'implementazione in Python:

def dot(f, g): 
    def result(arg): 
     return f(g(arg)) 
    return result 

crea solo una nuova funzione che si applica g ad un argomento, vale f al risultato, e restituisce il risultato dell'applicazione di f.

Così (concatMap . ins) 1 [[2, 3]] sta dicendo: creare una funzione, concatMap . ins, e applicarlo agli argomenti 1 e [[2, 3]]. Quando fai concatMap (ins 1 [[2,3]]) stai dicendo, applica la funzione concatMap al risultato dell'applicazione di ins a 1 e [[2, 3]] - completamente diverso, come hai capito dall'orrendo messaggio di errore di Haskell.

AGGIORNAMENTO: per sottolineare ulteriormente questo aspetto. Hai detto che (f . g) x era un'altra sintassi per f (g x). Questo è sbagliato! . è solo una funzione, poiché le funzioni possono avere nomi non alfanumerici (>><, .., ecc., Potrebbero anche essere nomi di funzioni).

Answer 3

Stai pensando troppo a questo problema. Puoi lavorare tutto usando semplici ragionamenti equazionali.Proviamo nuovamente da zero:

permute = foldr (concatMap . ins) [[]] 

Questo può essere convertito banalmente a:

permute lst = foldr (concatMap . ins) [[]] lst 

concatMap può essere definito come:

concatMap f lst = concat (map f lst) 

Il modo foldr opere in un elenco è che (per esempio):

-- let lst = [x, y, z] 
foldr f init lst 
= foldr f init [x, y, z] 
= foldr f init (x : y : z : []) 
= f x (f y (f z init)) 

Quindi qualcosa di simile

permute [1, 2, 3] 

diventa:

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 
     ((concatMap . ins) 3 [[]])) 

Lavoriamo attraverso la prima espressione:

(concatMap . ins) 3 [[]] 
= (\x -> concatMap (ins x)) 3 [[]] -- definition of (.) 
= (concatMap (ins 3)) [[]] 
= concatMap (ins 3) [[]]  -- parens are unnecessary 
= concat (map (ins 3) [[]]) -- definition of concatMap 

Ora ins 3 [] == [3], così

map (ins 3) [[]] == (ins 3 []) : [] -- definition of map 
= [3] : [] 
= [[3]] 

Così la nostra espressione originale diventa: il lavoro

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 
     ((concatMap . ins) 3 [[]])) 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]] 

Let attraverso

(concatMap . ins) 2 [[3]] 
= (\x -> concatMap (ins x)) 2 [[3]] 
= (concatMap (ins 2)) [[3]] 
= concatMap (ins 2) [[3]]  -- parens are unnecessary 
= concat (map (ins 2) [[3]]) -- definition of concatMap 
= concat (ins 2 [3] : []) 
= concat ([[2, 3], [3, 2]] : []) 
= concat [[[2, 3], [3, 2]]] 
= [[2, 3], [3, 2]] 

Così la nostra espressione originale diventa:

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 [[2, 3], [3, 2]] 
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]] 
= concatMap (ins 1) [[2, 3], [3, 2]] 
= concat (map (ins 1) [[2, 3], [3, 2]]) 
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map 
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
      [[1, 3, 2], [3, 1, 2], [3, 2, 1]]] -- defn of ins 
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
    [1, 3, 2], [3, 1, 2], [3, 2, 1]] 

nulla di magico qui. Penso che potresti essere stato confuso perché è facile presumere che sia concatMap = concat . map, ma non è questo il caso. Allo stesso modo, può sembrare come concatMap f = concat . (map f), ma neanche questo è vero. Il ragionamento equo ti mostrerà il perché.