Haskell falten Betrieb am Baum

Question

Beachten Sie, dass wir keine leeren Bäume zulassen, und dass ein Blatt ist ein Baum mit einer leeren Liste von Unterbäumen.

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

die oben genannten Informationen gegeben, die ich nicht verstehe, wie der Baum Falzfunktion ein Ergebnis zurückgibt, indem rekursiv die Falte Operation auf die Unterstrukturen Anwendung, dann an der Wurzel die Funktion zum Anbringen eines Etiketts und die Ergebnisse kehrte von den Unterbäumen zurück.

Ich bekomme auch nicht, wie die Tree Fold-Funktion nur ein Argument anstelle von 2, wenn es als Argument an die Kartenfunktion übergeben wird und es noch kompiliert und ordnungsgemäß ausgeführt wird. Beispiel: Die Baumgrößenfunktion unten zählt die Knoten des Baums. So

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

laufen TreeSize Baum wo tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]] die Größe des Baumes gibt als 4.

in der Baumgröße Funktion oben, der Baum Falzfunktion auch ein Argument übergeben wird statt zwei. Außerdem wird das x, das an die Tree-Fold-Funktion übergeben wird, nirgends verwendet, also warum brauchen Sie es dort? Wenn Sie das Programm entfernen, wird das Programm nicht kompiliert und die folgende Fehlermeldung wird angezeigt.

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

Jede Hilfe würde sehr geschätzt werden.

Answer 1

Die erste Frage ist ein bisschen knifflig, denn das ist die Sache mit Rekursion ... Wie Lehrer sagen: "Um Rekursion zu verstehen, muss man lernen, wie Rekursion funktioniert." :-P Ein kleiner Tipp: Versuchen Sie, die Anwendung von treeFold mit einem einzigen Baum oder einem Baum mit einem Baum im Inneren zu durchlaufen und bewerten Sie es (auf einem Papier oder so). Ich denke, dann könntest du ein Gefühl dafür bekommen, was vor sich geht ... (benutze natürlich eine einfache Funktion als Argument für treeFold; so wie es deine treeSize verwendet).

treeFold bekommt nur ein Argument in der Karte Körper, weil map eine Funktion aus a->b erfordert, und treeFold hat den Typ (a -> [b] -> b) -> Tree a -> b., also wenn Sie es 2 Argumente übergeben würde, würden Sie nur einen Wert map passieren, was ein verursacht Fehler. (Ein verständliches Beispiel: (+) erfordert zwei Argumente. Wenn Sie map (+1) [1,2,3] schreiben, erhalten Sie [2,3,4] , weil (+1) auf jedes Element in der Liste angewendet wird (und (+1) benötigt eindeutig ein weiteres Argument, wie Ihre treeFold f oben)

Ihr Beispiel TreeSize. es ist nicht richtig, wenn Sie sagen, dass es ein Argument nur bekommt man könnte über

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

statt Ihrer Definition schreiben Die x ist nicht. verwendet, weil zum Zählen ist es nutzlos.Aber, treeFoldn eeds um eine Funktion zu haben, die zwei Argumente braucht, also geben Sie ihr das x. Das ist der einzige Grund. Sie könnten einen anderen Wert übergeben.

Answer 2

Nicht verwendete Argumente

Zunächst wird die Art und Weise Sie explizit eine Variable markieren als nicht benutzt zu sein, ist die Variable mit _ zu ersetzen. Also wollten Sie wirklich:

treeFold (\_ ys -> 1 + sum ys) 

Sie haben einen Compiler-Fehler, weil Sie schrieb:

treeFold (\ys -> 1 + sum ys) 

... was nicht dasselbe ist.

Folds

Zweitens, ich treeSize auf einem Beispiel Baum bewerten Hand werden so können Sie sehen, dass es keine Magie auf dem Gehen ist:

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

Allerdings gibt es eine einfache Möglichkeit, sich daran zu erinnern, wie treeFold funktioniert. Alles, was es tut, ersetzt jeden Tree Konstruktor mit der Funktion, die Sie ihm liefern.

Also, wenn Sie haben:

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

... und Sie gelten treeFold f kommt, dass es bewerten zu:

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum nur der Sonderfall ist, wo f = (\_ ys -> 1 + sum ys):

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

Curry

Der letzte Punkt ist, wie Currying in Haskell funktioniert. Wenn Sie eine Funktion wie definieren:

foo x y = x + y 

... der Compiler desugars eigentlich, dass zu zwei verschachtelte Funktionen:

foo = \x -> (\y -> x + y) 

diesem Grund sollten Sie teilweise Funktionen anwenden können, um nur ein Argument in Haskell. Wenn Sie foo 1 schreiben, übersetzt sie in:

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

Mit anderen Worten, es eine neue Funktion ein Argument zurückgibt.

In Haskell nehmen alle Funktionen genau ein Argument, und wir simulieren Funktionen von mehreren Argumenten durch die Rückgabe neuer Funktionen. Diese Technik ist als "Curry" bekannt.

Wenn Sie das Multi-Argument Ansatz der traditionellen Mainstream-Sprachen bevorzugen, können Sie es simulieren, indem die Funktion eines Tupels Argument Kauf nehmen zu müssen:

f (x, y) = x + y 

aber das ist nicht wirklich idiomatische Haskell, und es gewann‘ t gibt Ihnen irgendeine Art von Leistungsverbesserung.