Wie bekomme ich einen Typ für eine bestimmte polymorphe Funktion und einen bestimmten Ausdruck?

Question

Hier ist die Prüfung Frage, dass dieser Beitrag aufgefordert:

Exam Frage:

Betrachten Sie die folgende Definition von binären Bäumen in Haskell.

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) 

Nach dieser Erklärung kann sein, Bäume: Empty ein Leaf ein Element der Art enthält, a oder ein Node Element vom Typ a und zwei Tree s enthält.

Zum Beispiel haben die folgenden Ausdrücke Typ Tree Int:

Leaf 0 

Node (Leaf 1) 2 (Leaf 3) 

Die folgende Funktion ein Tree auf eine Liste von Elementen flacht (man erinnere sich, dass die ++ Verkettungsoperator für Listen in Haskell ist).

flatten Empty = [ ] 
flatten (Leaf l) = [l] 
flatten (Node t1 r t2) = (flatten t1) ++ (r : (flatten t2)) 

i. Geben Sie einen polymorphen Typ für die Funktion flatten an. Rechtfertige deine Antwort.

ii. Geben Sie einen Typ für den Ausdruck:

flatten (Node (Leaf 1) 2 (Leaf 3)) 

Begründen Sie Ihre Antwort.

Meine Frage

Ich glaube, ich die Theorie hier zu verstehen, ist es klar, dass flatten, um seine Arbeit zu tun, es Art ist, interpretieren mehrere Typen ([ ], Leaf und Node), aber wie soll ich akzeptiert davon? Wenn ich nicht annehmen soll, dass flatten vom gleichen Typ ist, den es akzeptiert, bin ich mir nicht sicher, wohin ich von hier aus gehen soll.

In Bezug auf den zweiten Teil der Frage, gibt es verschiedene Typen für flatten je nachdem, ob es in Form eines Ausdruck ist? Wenn dem so ist, fühle ich mich in meiner Annahme im letzten Absatz recht, aber ich möchte den Komfort der tatsächlichen Logik auf meiner Seite haben, anstatt einfach zu raten.

Vielen Dank im Voraus.

Answer 1

es ist klar, dass flatten, um seine Arbeit zu tun, mehrere Typen ([ ], Leaf und Node)

ich, warum Sie denken, nicht verstehen, akzeptiert, dass flatten[ ] akzeptiert. Ich bin mir nicht einmal sicher, was du damit meinst; [ ] ist kein Typ, es ist ein Typkonstruktor, der den Typ a als Argument akzeptiert und den Typ [a] "list zurückgibt, dessen Elemente vom Typ a sind".

Die drei Klauseln, die alle flatten definieren machen es eine Funktion, die ein Argument nimmt, so hat es eine Art von Form x -> yx wo der Typ des Arguments ist und y ist der Rückgabetyp. In jedem Fall wird das Argument durch Anwenden eines Konstruktors des Tree-Typkonstruktors gebildet, so dass das Argument einen Typ der Form Tree w hat. Der Rückgabewert in der ersten Klausel lautet [], daher hat der Typ die Form [z]. Bis jetzt wissen wir, dass der allgemeinste Typ von flatten von der Form Tree w -> [z] ist. Die zweite Klausel flatten (Leaf l) = [l] stellt eine zusätzliche Einschränkung w = z bereit, da der Typ l auf beiden Seiten auftritt, so dass der allgemeinste Typ die Form Tree z -> [z] hat.

Dies ist in der Tat ein gültiger Typ für flatten, also Tree z -> [z] ist die allgemeinste Art von flatten. Um dies zu sehen, müssen Sie die gesamte Definition durchgehen und prüfen, ob sie keine zusätzliche Einschränkung auferlegt.

Dies ist ein polymorpher Typ: Er enthält die Typvariable z. Diese Variable kann von jedem Typ instanziiert werden. Beispielsweise verwendet flatten (Leaf (1 :: Int))flatten mit dem Typ Tree Int -> [Int], während flatten (Leaf True)flatten mit dem Typ Tree Bool -> [Bool] verwendet.

Die Tatsache, dass flatten ist polymorph ist nicht aufgrund seiner Funktion. Die Anwendung auf ein Argument ändert nicht den Typ von flatten, aber es darf nicht in seiner vollen Allgemeinheit verwendet werden. Der Typ des resultierenden Ausdrucks kann immer noch polymorph sein. Zum Beispiel ist der Typ \x -> flatten xTree a -> [a] für alle a, wie flatten, nicht überraschend, da \x -> flatten x äquivalent zu flatten ist.

Die Art der flatten (Leaf 3) Ergebnisse aus drei Einschränkungen: flatten mit einem Argument Art von Form Tree a hat den Rückgabetyp [a], Leafa jede Art akzeptiert und liefert einen Tree a und 3 hat den Typ Num a => a, dh 3 hat jede Art a vorausgesetzt, dass dieser Typ eine Instanz der Num Klasse ist. So hat flatten (Leaf 3) den Typ [a] unter der Bedingung, dass a eine Instanz von Num ist, d. H. flatten (Leaf 3) hat die allgemeinste Art Num a => [a].

Answer 2

Um die Frage richtig zu verstehen, sollten Sie über type inference und difference between type and data constructor wissen. Haskell verwendet einen Typ-Inferenz-Algorithmus, jedoch wird die Prüfungsfrage so formuliert, dass sie nicht notwendig ist und die Intuition ausreichend ist. Es ist auch nützlich zu wissen, dass wenn Sie :t <expression> in GHCI eingeben, wird es Ihnen den Typ geben.

In diesem speziellen Beispiel Ihrer Definition erstellt vier Konstrukteuren - einstelliger Typkonstruktor Tree, nullary Daten Empty, einstellige Daten Leaf und Ternärdaten Node.

Nun schauen wir uns die Funktion an. Die Funktion hat drei Definitionen, basierend auf dem, was das Muster abgleicht, aber wir wissen, dass jede Definition denselben Typ haben muss (oder mit anderen Typen vereinheitlichbar sein kann).Von der ersten Zeile

flatten Empty = [ ] 

wir, dass Flatten sehen einige Empty nimmt (was wir wissen, ein Tree ‚s Daten Konstruktor ist), und gibt eine [], was ist eine Liste. Tree ist jedoch ein parametrisierter Typ. Empty macht jedoch keinen Gebrauch von der Parametrisierung, und deshalb kann es zu jedem Tree - polymorfous Typ Tree a gehören. Die [] ist eine Liste. Listen sind in der Regel vom Typ [a], a der Typ der Liste Mitglieder. Es gibt keine Mitglieder in einer leeren Liste und daher ist der Typ der Liste polymorph - bleibt [a]. Wir haben jedoch gesagt, a kommt aus dem Tree Parameter, und es gibt nichts in dieser Zeile der Definition, die die Mitglieder der Liste sagt, kommt aus dem Baum, so können wir es anderen Namen geben, lassen Sie uns mit b gehen. Aus der ersten Zeile haben wir daher abgeleitet, dass der Typ Tree a -> [b] ist, oder etwas, das vereinheitlicht werden kann.

Von der zweiten Zeile

flatten (Leaf l) = [l]

Wir sehen, dass flatten einige Leaf nimmt, parametrisiert mit l. Wir wissen, dass Leaf l ein Datenkonstruktor einer Tree a ist, und wir wissen, dass l eine Art a ist. Also nimmt die Funktion wieder einige . Es gibt eine Liste mit einem einzelnen Element zurück, dem l. Wir wissen, dass l vom Typ a ist, daher muss die Liste vom Typ [a] sein. Der ganze Typ ist Tree a -> [a].

Wir können diesen Typ nehmen und vereinheitlichen mit dem, was wir von der ersten Zeile bekommen haben. Wenn das Tree a -> [b] das gleiche wie Tree a -> [a] sein sollte, sehen wir, dass a gleich b sein muss. Also vereinigen wir uns. Wir sollten uns die dritte Zeile ansehen, aber in diesem Fall wird der Typ nicht weiter vereinheitlicht.

Eine weitere Sache. Wenn wir Definition wie folgt hatten:

flatten Empty = ['e'] 
flatten (Leaf l) = [l] 
flatten (Node t1 r t2) = (flatten t1) ++ (r : (flatten t2)) 

würden wir von der ersten Zeile sehen, dass der resultierende Typ ein Array von Zeichen ist [Char] (oder String, dann ist es eine Alias). Der Funktionstyp wäre Tree a -> [Char]. Nachdem wir die zweite Zeile betrachtet haben und sehen, dass das Array enthält, was das Blatt enthält, müssen wir nach der Vereinheitlichung annehmen, dass der Baum nur Zeichen enthält, und der Typ der Funktion wäre Tree Char -> [Char].