Anfänger Implementierung von Catamorphism für nicht binäre Bäume gegenüber dem Composite Design Pattern

Question

Im Moment geht der Traum noch auf, an jedem Haskell Konzept Ich lerne ich bin mehr gelockt. Doch ich habe vollständig erfüllen Die Arbeit an diesem kostbaren @ luqui Antwort auf meine vorherige Frage über catamorphism , und ich bin es, bis es ok würde zurückkommen. Es war zu diesem Beispielcode auf Wikipedia, die sich mit catamorphism auf Binärbäumen .

Dennoch habe ich versucht, die Umsetzung catamorphism für NICHT BINARY Bäume, aber ich Gesicht einige Probleme:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- das letzte Zeile auf bitte ghc tut "Karte g [y]"

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

- und das lattest sumTree falsch ist auch für ghc

Ich sehe> und +, genau wie die C ++ Operatoren> und +. So verstehe ich nicht ghc bei mir, um es ohne meine geben objets Umsetzung opertor> / + oder nicht.

Zweitens muß ich zugeben, ich bin völlig verschwommen über den Sinn => (abweichend von -> ???). Und @, die für Mustererkennung wie ein Führer zu sein scheint,

Wie würden Sie diesen Code korrekt?

Und eine letzte Frage, Ich bin auch tun dies VERSUCHT, weil das Composite-Muster passiert ist das wichtigste für mich in C ++ sein. Und natürlich sehe ich es kann fast nur in Haskell eine / zwei Zeilen beschrieben werden (das ist für mich wirklich erstaunlich ist).

Aber wie würden Sie Haskell Menschen ausdrücken, dass Blatt und Composite-Konstruktor Zusammensetzung eine Art von derselben Schnittstelle haben? (Ich weiß, es ist nicht das gute Wort, da die Daten nicht wandelbar sind, aber ich hoffe, Sie können meine Sorge / Ziel erraten versteh)

Dies ist der Gesamtübersetzungsfehler;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

Bearbeiten Das ist also die endgültige Version für nicht binäre catamorphism

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

Und nach der gültigen Antwort unten:., Was ich bat um Haskell Äquivalent von C ++ Schnittstellen Verträge scheint typeclasses Einschränkungen zu sein

So die Design-Muster Verbund durch Anwendung typeclass Einschränkungen würde erreicht werden, wenn die Zusammensetzung einer Konstruktion. Vielleicht sollten ein neues speziellen Daten definieren werden. Aber ich sollte typeclasses lernen, bevor Sie, dass: -)

Answer 1

Es gibt ein paar verschiedene Fehler hier, so bin ich nicht sicher der beste Weg, mit ihm auf SO beschäftigen, aber was zum Teufel.

In der Zukunft versuchen, mehr des Fehlers enthalten, dass GHC bereitstellt.

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

Die Funktion foldCompose hat zwei Fehler, dass ich sehen kann, von denen nur einer durch die Art Kontrolleur gefangen werden.

1. Sie sind Pattern-Matching auf (Composite [y]), die nur für Listen eines Elements übereinstimmen. Sie wollen wahrscheinlich (Composite ys), das bindet an die gesamte Liste ys.

2. map g [y] den Typ-Checker nicht passieren, weil Sie bereits g als Einnahme eine Liste von r definiert haben, aber Sie geben ihm eine Liste von a.

   a

Um eine r zu einem CompositionAlgebra zu konvertieren Sie benötigen g (map (foldComposition a) ys), um es anzuwenden

Also ich würde schreiben, um diese zum Beispiel:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

Für Ihren nächsten Fehler:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

In Haskell, eine Variable vom Typ (wie a hier) alle durch seine einsame in dem von dem Anrufer überhaupt mit jeder Art gefüllt werden kann, bei der Wahl des Anrufers.

Dieses Mittel in Ihrer Art Unterschrift Sie behaupten, dass die Funktion maxPair für funktioniert alle input type. GHC beschwert sich (in seiner eigenen Art und Weise), dass der Betreiber > nicht funktioniert für alle Typ, und dafür verweigert das Programm zu kompilieren.

Sie werden verwenden müssen typeclasses , um dieses Problem zu lösen. In Haskell, ließ typeclasses die Anrufer die Typen zu verwenden wählen, aber mit einigen Einschränkungen. Ich empfehle die Lektüre ein Haskell Tutorial auf typeclasses .

Die richtige Art Unterschrift wäre:

maxOfPair :: Ord a => a →  a →  a

, die die Ord Einschränkung auf die Art a gilt.

Außerdem sollten Sie mit der Standardfunktion seines max .

Answer 2

Zweitens muss ich zugeben, ich bin völlig dunstig über den Sinn => (verschiedene von -> ???) und @, die zu sein scheint wie ein Leitfaden für den Mustervergleich.

Consinder die Elem Funktion, die, wenn eine Liste prüft einen bestimmten Wert enthält. Man könnte definieren es als

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

Welche Signatur hat diese Funktion? Sieht aus wie elem :: a -> [a] -> Bool. Aber der Compiler wird sich beschweren, weil Sie x == y schrieb, und nicht für jede a die == Funktion definiert ist, nur für diejenigen a, die in der Eq Typklasse . Sie müssen also so etwas wie „Für alle ein, die in Gl ...“ angeben. Und genau dafür brauchen Sie =>. So ist die richtige Signatur für elem ist elem :: Eq a => a -> [a] -> Bool.

Die @ gibt Ihnen die Möglichkeit, einen Namen eine ganze Struktur zu geben und Mustererkennung auf sie zugleich. Z.B. wenn Sie das Muster a@(x:xs) haben und rufen Sie diese Funktion mit [1,2,3,4], dann a ist [1,2,3,4], xis 1 und xs ist [2,3,4].