la mise en œuvre de débutant de catamorphisme pour les arbres non binaires par rapport au Design Pattern Composite

Question

Pour le moment, le rêve se poursuit encore, à chaque concept haskell J'apprends que je suis plus attiré. Pourtant, je nai pas complètement rempli à travailler sur la réponse de cette précieuse @ Luqui ma question précédente sur catamorphisme , et je vais revenir à elle jusqu'à ce qu'il soit correct. Il était sur le code exemple sur Wikipedia, traitant catamorphisme sur les arbres BINARY .

Néanmoins, j'ai essayé la mise en œuvre catamorphisme NON BINARY arbres mais je face à certains problèmes:

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] 

- que la dernière ligne ne marche pas sur GHC plaire "carte 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 = (+) } 

- et ce lattest sumTree est faux aussi pour GHC

Je vois> et +, tout comme les opérateurs C ++> et +. Donc, je ne comprends pas GHC est en colère contre moi, sans que je lui donnant la mise en œuvre opertor objets> / + ou non.

En second lieu, je dois admettre que je suis tout à fait flou sur le sens de => (différent de -> ???). Et @ qui semble être comme un guide de correspondance de motif

Comment voulez-vous corriger ce code?

Et une dernière question, Je tente aussi fait cela parce que le modèle composite est arrivé à être le plus important pour moi en C ++. Et évidemment, je le vois peut être décrite dans presque seule ligne un / deux en Haskell (qui est vraiment incroyable pour moi).

Mais comment voulez-vous HASKELL les gens expriment le fait que des feuilles et le constructeur composite de composition peut avoir une sorte de la même interface? (Je sais que ce n'est pas le bon mot, car les données ne sont pas mutable, mais j'espère que vous pouvez deviner comprendre ma préoccupation / but)

est l'erreur totale de compilation;

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'

EDIT C'est donc la version finale pour catamorphisme non binaire

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 } 

Et selon la réponse valide ci-dessous. Ce que je demandais haskell équivalent de contrats Interfaces C ++ semble être contraintes de classes de types

Ainsi, le modèle de conception composite serait obtenue en appliquant les contraintes lors de la construction du classe de types Composition. Peut-être une nouvelle donnée spécialisée devrait être définir. Mais je devrais apprendre avant de faire cela classes de types: -)

Answer 1

Il y a quelques erreurs différentes ici, donc je ne suis pas sûr de la meilleure façon de traiter sur SO, mais ce que le diable.

Dans l'avenir, essayez d'inclure plus des erreurs GHC fournit.

:

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]

La foldCompose fonction a deux erreurs que je peux voir, dont un seul sera pris par le vérificateur de type.

1. Vous êtes en correspondance de motif sur (Composite [y]), qui ne correspondent pour les listes d'un élément. Vous voulez probablement (Composite ys), qui se fixe ys à la liste entière.

2. map g [y] ne passera pas le type vérificateur, parce que vous avez déjà g défini comme prenant une liste de r, mais vous donnez une liste des a.

   Pour convertir un a à un r vous devez appliquer votre CompositionAlgebra à elle: g (map (foldComposition a) ys)

Je voudrais donc écrire ce que:

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)

Pour votre erreur suivante:

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

Dans Haskell, une variable de type (comme a ici) tout par son lonesome peut être rempli avec tout type du tout par l'appelant, au choix de l'appelant.

Cela signifie votre signature de type que vous affirmez que la fonction maxPair fonctionnera pour tous type d'entrée. GHC se plaint (à sa manière) que le > opérateur ne fonctionne pas pour tous type et celui-ci refuse de compiler votre programme.

Vous aurez besoin d'utiliser classes de types pour résoudre ce problème. Dans Haskell, laissez l'appelant classes de types choisir les types à utiliser, mais avec certaines contraintes. Je recommande la lecture d'un tutoriel sur classes de types.

La signature de type correct serait:

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

Ce qui applique la contrainte Ord au a type.

En outre, vous devriez utiliser la fonction standard max .

Answer 2

  

En second lieu, je dois admettre que je suis complètement   brumeux sur le sens de => (différent   de -> ???) et @ qui semble être   comme un guide pour la mise en correspondance de motif.

élém fonction, qui teste si une liste contient une certaine valeur. Vous pouvez le définir comme

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

signature qui a cette fonction? On dirait elem :: a -> [a] -> Bool. Mais le compilateur se plaindra parce que vous avez écrit x == y, et non pour chaque a la fonction == est définie, seulement pour ceux qui sont a dans équation de type classe . Donc, vous devez spécifier quelque chose comme « Pour tout a qui sont dans l'équation ... ». Et exactement ce dont vous avez besoin =>. Ainsi, la signature correcte pour elem est elem :: Eq a => a -> [a] -> Bool.

Le @ vous donne la possibilité de donner une structure entière un nom et de correspondance de motif sur elle en même temps. Par exemple. si vous avez le modèle a@(x:xs) et que vous appelez cette fonction avec [1,2,3,4], puis a est [1,2,3,4], xis 1 et xs est [2,3,4].