Haskell Funktion Anwendung und currying

Question

Ich bin immer daran interessiert, neue Sprachen zu lernen, eine Tatsache, die mich auf Trab hält und macht mich (glaube ich) ein besserer Programmierer. Meine Versuche, Haskell zu erobern, kamen und gingen - zweimal so weit - und ich beschloss, dass es an der Zeit war, es noch einmal zu versuchen. 3. Mal ist der Charme, oder?

Nein. Ich lese meine alten Notizen noch einmal ... und werde enttäuscht :-(

Das Problem, das mich letztes Mal das Vertrauen verloren hat, war einfach: Permutationen von ganzen Zahlen. dh von einer Liste von ganzen Zahlen, zu einer Liste von Listen - eine Liste ihrer Permutationen:

[int] -> [[int]] 

Dies ist in der Tat ein allgemeines Problem, würde gelten, so 'int' oben mit 'a', ersetzt noch

aus meinen Notizen:

.

Ich code es zuerst auf eigene Faust, es gelingt mir. Hurray!

Ich sende meine Lösung an einen guten Freund von mir - Haskell Guru, es hilft normalerweise, von Gurus zu lernen - und er sendet mir das, was mir gesagt wird, "drückt die wahre Kraft der Sprache, den Gebrauch von Generika aus Einrichtungen, um Ihre Bedürfnisse zu kodieren ". Alles für es, ich trank vor kurzem die Kool-Aid, lass uns gehen:

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. Lassen Sie uns dies aufgliedern:

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, so weit, so gut. Nahm mich eine Minute, um die zweite Zeile von "ins" zu verstehen, aber OK: Es platziert den ersten arg in allen möglichen Positionen in der Liste. Cool.

Nun, um die foldr und concatMap zu verstehen. in der "realen Welt Haskell" wurde die DOT erklärt ...

(f . g) x 

... als nur eine andere Syntax für ...

f (g x) 

Und im Code der Guru geschickt wurde DOT verwendet von einem foldr, mit der „In“ Funktion als fold „Kollaps“:

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

OK, da ich verstehen will, wie die DOT vom Guru verwendet wird, versuche ich, den äquivalenten Ausdruck gemäß der DOT-Definition , (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]]) 

Was!?! Warum? OK, ich überprüfe die concatMap-Signatur und stelle fest, dass sie ein Lambda und eine Liste benötigt, aber das ist nur ein menschliches Denken; Wie bewältigt GHC? Nach der Definition von DOT oben ...

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

... was ich war gültig war, ersetzen weise:

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

Kopf verkratzt ...

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

So ...Die DOT-Erklärung war anscheinend zu simpel ... DOT muss irgendwie klug genug sein, um zu verstehen, dass wir tatsächlich "ins" wollten, um curri-ed weg zu bekommen und das erste Argument "essen" und so eine Funktion werden, die nur will operieren auf [t] (und "durchsetzen" sie mit "1" in allen möglichen Positionen).

Aber wo wurde das angegeben? Wie kam wußte GHC, dies zu tun, wenn wir aufgerufen:

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

Hat das „In“ Signatur irgendwie diese vermittelt ... „essen mein erstes Argument“ Politik?

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

Ich sehe nicht nichts besonder - „In“ ist eine Funktion, die eine ‚t‘ nimmt, eine Liste von ‚t‘ und geht eine Liste mit allen „interspersals“ zu erstellen. Nichts über "essen Sie Ihr erstes Argument und curry es weg".

Also da ... Ich bin verwirrt. Ich verstehe (nach einer Stunde, in der ich den Code anschaue!), Was vor sich geht, aber ... Gott allmächtig ... Vielleicht versucht GHC zu sehen, wie viele Argumente es "ablösen" kann?

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) 

Again - Huch ...

Und da ich immer die Sprachen bin im Vergleich mit denen ich lerne, was ich schon weiß, wie würde „In“ in Python aussehen?

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]] 

Sei ehrlich, jetzt ... was ist einfacher?

Ich meine, ich weiß, ich bin ein Neuling in Haskell, aber ich fühle mich wie ein Idiot ... Betrachtet 4 Zeilen Code für eine Stunde und am Ende vorausgesetzt, dass der Compiler ... verschiedene Interpretationen bis es versucht findet etwas, das "klickt"?

von tödlicher Waffe zu zitieren: „Ich bin zu alt für dieses“ ...

Answer 1

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

Dies gilt. Sie daraus geschlossen, dass

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

muss auch wahr sein, aber das ist nicht der Fall. In der Tat ist das Folgende wahr:

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

was nicht das Gleiche ist.

Warum ist das wahr? Nun (f . g) x y ist das gleiche wie ((f . g) x) y und da wir wissen, (f . g) x = f (g x) können wir das auf (f (g x)) y reduzieren, das ist wieder das gleiche wie f (g x) y.

Also (concatMap . ins) 1 [[2,3]] entspricht concatMap (ins 1) [[2,3]]. Hier gibt es keine Magie.

Ein anderer Weg, um diesen Ansatz ist über die Typen:

. hat den Typ (b -> c) -> (a -> b) -> a -> c, concatMap den Typ hat (x -> [y]) -> [x] -> [y], ins hat den Typ t -> [t] -> [[t]].Wenn wir also concatMap als b -> c Argument und ins als a -> b Argument verwenden, dann at wird, b wird [t] -> [[t]] und c wird [[t]] -> [[t]] (mit x = [t] und y = [t]).

Also der Typ von concatMap . ins ist t -> [[t]] -> [[t]], was bedeutet, dass eine Funktion eine was auch immer und eine Liste von Listen (von whatevers) und eine Liste von Listen (des gleichen Typs) zurückgibt.

Answer 2

Ich möchte meine zwei Cent hinzufügen. Die Frage und Antwort klingt wie . ist ein magischer Operator, der seltsame Dinge mit Neuanordnung von Funktionsaufrufen macht. Das ist nicht der Fall. . ist nur Funktionszusammensetzung. Hier ist eine Implementierung in Python:

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

Es schafft nur eine neue Funktion, die g auf ein Argument gilt, gilt f auf das Ergebnis, und gibt das Ergebnis der f Anwendung.

Also (concatMap . ins) 1 [[2, 3]] sagt: Erstellen Sie eine Funktion, concatMap . ins, und wenden Sie es auf die Argumente 1 und [[2, 3]]. Wenn Sie concatMap (ins 1 [[2,3]]) tun, sagen Sie stattdessen, wenden Sie die Funktion concatMap auf das Ergebnis der Anwendung ins auf 1 und [[2, 3]] - völlig anders, wie Sie Haskell's schreckliche Fehlermeldung herausgefunden.

UPDATE: Um dies noch weiter zu betonen. Sie haben gesagt, dass (f . g) x eine andere Syntax für f (g x) ist. Dies ist falsch! . ist nur eine Funktion, da Funktionen nicht-alphanumerische Namen haben können (>><, .. usw. könnten auch Funktionsnamen sein).

Answer 3

Sie überdenken dieses Problem. Sie können alles mit einfachen Gleichargumentationen ausarbeiten.Lassen Sie uns versuchen, es von Grund auf neu:

kann

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

concatMap wie folgt definiert werden:

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

Dies kann trivialer Weise umgewandelt werden

concatMap f lst = concat (map f lst) 

Die Art und Weise foldr Arbeiten auf einer Liste ist, dass (zum Beispiel):

-- 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)) 

So etwas wie

permute [1, 2, 3] 

wird:

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

die durch den ersten Ausdruck arbeiten lassen:

(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 

Jetzt ins 3 [] == [3], so

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

So ist unser ursprünglicher Ausdruck wird:

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

Lassen Sie sich Arbeit durch

(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]] 

So ist unser ursprünglicher Ausdruck wird:

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]] 

nichts Magisches hier. Ich denke, Sie könnten verwirrt gewesen sein, weil es leicht ist, dassanzunehmen, aber das ist nicht der Fall. Ähnlich kann es wie concatMap f = concat . (map f) scheinen, aber das ist auch nicht wahr. Gleichwertiges Denken wird Ihnen zeigen, warum.