concatKarte Erklärung

Question

Hallo Leute von StackOverflow!

Ich habe angefangen, mit Haskell zu arbeiten, und bin auf die concatMap Funktion gestolpert. Da ich in dieser Sprache ganz neu bin, habe ich einige Probleme den folgenden Code zu verstehen (source):

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = accum (f x) where 
     accum [] = cmap xs 
     accum (y : ys) = y : accum ys 

Soweit ich die Funktion concatMap nimmt in einem Argument f verstehen, die eine Funktion ist.

Aber wie können wir eine Funktion gleich einer anderen setzen? Setzen wir das Ergebnis von f gleich cmap, oder verwenden wir cmap als Parameter für f?

Jede Hilfe wäre sehr willkommen,

Vielen Dank im Voraus!

Answer 1

Der Code, den Sie gepostet haben, ist nicht einfach für einen Anfänger. Glücklicherweise können wir sie Stück für Stück neu schreiben:

accum [] = cmap xs 
accum (y : ys) = y : accum ys 

Die Funktion oben, wenn die Eingangsliste leer ist, kehrt cmap xs, sonst auf y:ys aussendet y als das erste Element Ausgang und geht dann zum Ausgang accum xs rekursiv.

Daher wird accum zs einfach alle Elemente in zs ausgeben und danach mit cmap xs fortfahren. Wir können umschreiben, dass als:

accum zs = zs ++ cmap xs 

wo ++ Liste Verkettung ist.

Wir können dann den gesamten Code wie folgt umschreiben, entsprechend:

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = f x ++ cmap xs 

Wir schreiben weiter ist als

concatMap f [] = [] 
concatMap f (x : xs) = f x ++ concatMap f xs 

, die für einen Anfänger mehr zugänglich sein sollte. Mehr informell erfüllt die obige Definition der Gleichung:

concatMap f [x1,x2,...,xn] = 
    f x1 ++ f x2 ++ ... ++ f xn ++ [] 

So können wir sehen, was concatMap tut. Sie wendet f auf jedes Listenelement an und für jedes Listenelement muss f eine Liste zurückgeben. Dann werden alle diese Listen verkettet.

Zum Beispiel:

concatMap (\x -> [1..x]) [3,1,2] = 
    [1,2,3] ++ [1] ++ [1,2] = 
    [1,2,3,1,1,2] 

Answer 2

chi Antwort beschreibt, wie concatMap Werke, also werde ich speziell auf einem Ihres Zweifel konzentrieren:

Aber wie können wir eine Funktion gleich zu einem anderen gesetzt?

Eine Funktion in Haskell ist ein Wert, genau wie jeder andere auch.

GHCi> foo = "foo" 

Dies ist eine Definition von foo, die eine Zeichenfolge sein geschieht:

GHCi> :t foo 
foo :: [Char] 
GHCi> putStrLn foo 
foo 

In der gleichen Art und Weise ...

GHCi> add = (+) 

... Dies ist eine Definition des Begriffs add, die zufällig eine Funktion ist:

GHCi> :t add 
add :: Num a => a -> a -> a 
GHCi> add 2 3 
5 

In der obigen Definition, um zu betonen, dass ich gerade einen Wert definiert habe, habe ich keinen der Parameter von add explizit geschrieben. Es ist völlig in Ordnung, das zu tun, aber:

GHCi> add x y = (+) x y 

(. Beachten Sie, dass x + y, das ist, wie wir in der Regel mit der rechten Seite der Definition schreiben würden oben ist einfach bequeme Alternative Syntax für (+) x y)

Eine andere Möglichkeit, die Definition des Schreibens nutzt Teil Anwendung nur der erste Parameter zu erwähnen:

GHCi> add x = (+) x 

Wir können auch nur für die um von ihm (und vielleicht zu klären, was los ist), die (+) x in eine separate Definition in einer where-Klausel bewegen ...

GHCi> :{ 
GHCi| add x = plusX 
GHCi|  where 
GHCi|  plusX = (+) x 
GHCi| :} 

... und den zweiten Parameter schreiben nochmals ausdrücklich:

GHCi> :{ 
GHCi| add x = plusX 
GHCi|  where 
GHCi|  plusX y = (+) x y 
GHCi| :} 

plusX ist eine Funktion, die ein Argument nimmt und es zu x hinzufügt. add ist eine Funktion, die ein Argument x übernimmt und die plusX-Funktion zurückgibt, die der x entspricht. Es ist diese zweite Funktion, die das zweite Argument zu add nimmt, wenn wir add 2 3 machen (was übrigens äquivalent zu (add 2) 3 ist).

Nun vergleichen Sie bitte oben mit concatMap Definition:

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = accum (f x) where 
     accum [] = cmap xs 
     accum (y : ys) = y : accum ys 

Die Definitionen werden in analoger Weise angelegt. cmap ist eine Funktion, die eine Liste nimmt und f, das Argument concatMap verwendet, um ein Ergebnis daraus zu erzeugen, ähnlich wie plusX das x Argument von add.

Also, um es zusammenzufassen:

Sind wir das Ergebnis von f gleich cmap Einstellung oder verwenden wir cmap als Parameter für die f?

Weder. Wir verwenden f, um cmap zu definieren, das dann verwendet wird, um concatMap als Ganzes zu definieren.