Catamorphisme et d'arbres à Haskell traversant

Question

Je suis impatient, impatient de catamorphisme compréhension liés à cette question SO :)

je n'ai pratiqué le début du tutoriel Real World Haskell. Alors, peut-être que je vais demander beaucoup trop en ce moment, si ce fut le cas, dites-moi juste les concepts que je dois apprendre.

Ci-dessous, je cite wikipedia exemple de code catamorphisme.

Je voudrais connaître votre opinion sur foldTree ci-dessous, une façon de traverser un arbre, par rapport à cette autre question SO et réponse, traitant également de traverser un arbre n-aire arbre traversal. (Indépendamment d'être binaire ou non, je pense que le catamorphisme ci-dessous peut être écrit de manière à gérer l'arbre n-aire)

Je mets en commentaire ce que je comprends, et soyez heureux si vous pouviez me corriger, et de clarifier certaines choses.

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r -> r }

{- foldTree is a morphism that takes: a TreeAlgebra for Tree a with result r, a Tree a
and returns an r -} 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree a@(TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree a@(TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

à ce stade, j'ai beaucoup de difficultés, il me semble deviner que la feuille de morphisme sera appliqué à une feuille Mais pour utiliser ce code pour de vrai, foldTree doit être nourris avec un TreeAlgebra défini, un TreeAlgebra qui a une feuille de morphisme défini de manière à faire quelque chose?
mais dans ce cas dans le code foldTree je me attends {f = feuille} et non le contraire

Toute clarification de votre part serait vraiment la bienvenue.

Answer 1

Pas exactement ce que vous demandez. Mais oui, vous nourrissez un TreeAlgebra à foldTree correspondant au calcul que vous souhaitez effectuer sur l'arbre. Par exemple, pour résumer tous les éléments dans un arbre de Ints vous utiliseriez cette algèbre:

sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
                         , branch = (+) }

Ce qui signifie que, pour obtenir la somme d'une feuille, appliquer id (ne rien faire) à la valeur dans la feuille. Pour obtenir la somme d'une branche, additionnez les sommes de chacun des enfants.

Le fait que nous pouvons dire pour (+) branche au lieu de, disons, \x y -> sumTree x + sumTree y est la propriété essentielle du catamorphisme. Il dit que pour calculer une f fonction sur une structure de données récursive il suffit d'avoir les valeurs de f pour ses enfants immédiats.

Haskell est un langage assez unique en ce sens que nous pouvons formaliser l'idée de catamorphisme abstraitement. Faisons un type de données pour un seul nœud dans votre arbre, paramétrés sur ses enfants:

data TreeNode a child
    = Leaf a
    | Branch child child

Voyez ce que nous avons fait là-bas? Nous venons remplaçons les enfants récursives avec un type de notre choix. Il en est ainsi que nous pouvons mettre les sommes de sous-arbres là quand nous plier.

Maintenant, pour ce qui est vraiment magique. Je vais écrire ceci dans pseudohaskell - écrire en temps réel Haskell est possible, mais nous devons ajouter quelques annotations pour aider le typechecker qui peut être une sorte de confusion. Nous prenons le « point fixe » d'un type de données paramétrées - qui est, la construction d'un type de données T telle que T = TreeNode a T. Ils appellent cela Mu opérateur.

type Mu f = f (Mu f)

Regardez bien ici. L'argument de Mu est pas un type, comme Int ou Foo -> Bar. Il est un type constructeur comme Maybe ou TreeNode Int - l'argument se Mu prend un argument. (La possibilité d'abstraire sur les constructeurs de type est l'une des choses qui rend le système de type de Haskell se démarquent vraiment dans sa puissance expressive).

le type Mu f est défini comme la prise f et le remplissage dans son paramètre de type avec Mu f lui-même. Je vais définir un synonyme de réduire une partie du bruit:

type IntNode = TreeNode Int

L'expansion Mu IntNode, nous obtenons:

Mu IntNode = IntNode (Mu IntNode)
           = Leaf Int | Branch (Mu IntNode) (Mu IntNode)

Voyez-vous comment Mu IntNode est équivalent à votre Tree Int? Nous venons de la structure récursive déchiré dehors puis utilisé Mu pour le remettre à nouveau ensemble. Cela nous donne l'avantage que nous pouvons parler de tous les types de Mu à la fois. Cela nous donne ce que nous devons définir un catamorphisme.

Soit définir de:

type IntTree = Mu IntNode

J'ai dit la propriété essentielle du catamorphisme est que pour calculer une f fonction, il suffit d'avoir les valeurs de f pour ses enfants immédiats. Appelons le type de chose que nous essayons de r Compute, et la structure de données node (IntNode serait une instanciation possible de cela). Donc, pour r Compute sur un nœud particulier, nous avons besoin du nœud avec ses enfants remplacés par leurs rs. Ce calcul est de type node r -> r. Ainsi, un catamorphisme dit que si nous avons un de ces calculs, nous pouvons calculer r pour l'ensemble récursive la structure (souvenez-vous récursion est désignée explicitement ici avec Mu):

cata :: (node r -> r) -> Mu node -> r

Faire ce béton pour notre exemple, cela ressemble à:

cata :: (IntNode r -> r) -> IntTree -> r

Reformuler, si nous pouvons prendre un nœud avec rs pour ses enfants et calculer une r, alors nous pouvons calculer une r pour un arbre entier.

Afin de calculer effectivement, nous avons besoin d'être un node Functor - qui est que nous devons être en mesure de cartographier une fonction arbitraire sur les enfants d'un noeud

.

fmap :: (a -> b) -> node a -> node b

Cela peut être fait pour IntNode carrément.

fmap f (Leaf x) = Leaf x                  -- has no children, so stays the same
fmap f (Branch l r) = Branch (f l) (f r)  -- apply function to each child

enfin , nous pouvons donner une définition pour cata (la contrainte Functor node dit juste que node a un fmap approprié):

cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)

J'ai utilisé le nom du paramètre t pour la valeur mnémonique de « arbre ». Ceci est une définition abstraite dense, mais il est vraiment très simple. Il dit: récursive effectuer cata f - le calcul que nous faisons sur l'arbre - sur chacun des enfants de t (qui sont eux-mêmes Mu nodes) pour obtenir un node r, puis passer ce résultat à f calculer le résultat pour t lui-même

Lier ce retour au début, l'algèbre vous définissez est essentiellement une façon de définir cette fonction de node r -> r. En effet, étant donné un TreeAlgebra, on peut facilement obtenir la fonction double:

foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r)
foldFunction alg (Leaf a) = leaf alg a
foldFunction alg (Branch l r) = branch alg l r

Ainsi, le catamorphisme arbre peut être défini en termes de notre générique comme suit:

type Tree a = Mu (TreeNode a)

treeCata :: TreeAlgebra a r -> (Tree a -> r)
treeCata alg = cata (foldFunction alg)

Je suis hors du temps. Je sais que ça a vraiment abstraite très vite, mais je l'espère au moins vous ai donné un nouveau point de vue pour aider votre apprentissage. Bonne chance!

Answer 2

Je pense que vous posiez une question sur les {} 's. Il y a une question plus tôt avec une bonne discussion sur {} 's. Ceux-ci sont appelés enregistrement syntaxe Haskell. L'autre question est pourquoi construire l'algèbre. Ceci est un paradigme de fonction typique où vous généralisez données fonctions.

L'exemple le plus célèbre est la construction de l'église des Naturals , où f = + 1 et z = 0 , 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z)), etc ...

Ce que vous voyez est essentiellement la même idée appliquée à un arbre. Travailler l'exemple de l'église et l'arbre cliquera.