Qu'est-ce qu'un catamorphisme et peut-il être implémenté en C # 3.0?

Question

J'essaie d'en savoir plus sur les catamorphismes et j'ai lu l'article de Wikipedia et les premiers messages dans la série du sujet en fa # sur le blog Inside F # .

Je comprends qu’il s’agit d’une généralisation des plis (c’est-à-dire mapper une structure de plusieurs valeurs sur une valeur, y compris une liste de valeurs sur une autre liste). Et je suppose que la liste et l’arborescence sont un exemple canonique.

Peut-on montrer que cela se fait en C #, en utilisant l'opérateur Aggregate de LINQ ou une autre méthode d'ordre supérieur?

Answer 1

LINQ Aggregate() est juste pour IEnumerables. Les catamorphismes font généralement référence au modèle de pliage pour un type de données arbitraire. Donc FoldTree est de Trees ce que <=> (ci-dessous) est <=> (ci-dessous); les deux sont des catamorphismes pour leurs types de données respectifs.

J'ai traduit une partie du code dans la partie 4 de la série en C #. Le code est ci-dessous. Notez que l'équivalent F # utilise trois caractères inférieurs à (pour les annotations de paramètre de type générique), alors que ce code C # en utilise plus de 60. C'est la raison pour laquelle personne n'écrit un tel code en C # - il y a trop d'annotations de type. Je présente le code au cas où il aiderait les personnes qui connaissent C # mais pas F # à jouer avec cela. Mais le code est si dense en C # qu'il est très difficile de comprendre.

Étant donné la définition suivante d'un arbre binaire:

using System;
using System.Collections.Generic;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Shapes;

class Tree<T>   // use null for Leaf
{
    public T Data { get; private set; }
    public Tree<T> Left { get; private set; }
    public Tree<T> Right { get; private set; }
    public Tree(T data, Tree<T> left, Tree<T> rright)
    {
        this.Data = data;
        this.Left = left;
        this.Right = right;
    }

    public static Tree<T> Node<T>(T data, Tree<T> left, Tree<T> right)
    {
        return new Tree<T>(data, left, right);
    }
}

On peut plier des arbres et par exemple mesurer si deux arbres ont des nœuds différents:

class Tree
{
    public static Tree<int> Tree7 =
        Node(4, Node(2, Node(1, null, null), Node(3, null, null)),
                Node(6, Node(5, null, null), Node(7, null, null)));

    public static R XFoldTree<A, R>(Func<A, R, R, Tree<A>, R> nodeF, Func<Tree<A>, R> leafV, Tree<A> tree)
    {
        return Loop(nodeF, leafV, tree, x => x);
    }

    public static R Loop<A, R>(Func<A, R, R, Tree<A>, R> nodeF, Func<Tree<A>, R> leafV, Tree<A> t, Func<R, R> cont)
    {
        if (t == null)
            return cont(leafV(t));
        else
            return Loop(nodeF, leafV, t.Left, lacc =>
                   Loop(nodeF, leafV, t.Right, racc =>
                   cont(nodeF(t.Data, lacc, racc, t))));
    }

    public static R FoldTree<A, R>(Func<A, R, R, R> nodeF, R leafV, Tree<A> tree)
    {
        return XFoldTree((x, l, r, _) => nodeF(x, l, r), _ => leafV, tree);
    }

    public static Func<Tree<A>, Tree<A>> XNode<A>(A x, Tree<A> l, Tree<A> r)
    {
        return (Tree<A> t) => x.Equals(t.Data) && l == t.Left && r == t.Right ? t : Node(x, l, r);
    }

    // DiffTree: Tree<'a> * Tree<'a> -> Tree<'a * bool> 
    // return second tree with extra bool 
    // the bool signifies whether the Node "ReferenceEquals" the first tree 
    public static Tree<KeyValuePair<A, bool>> DiffTree<A>(Tree<A> tree, Tree<A> tree2)
    {
        return XFoldTree((A x, Func<Tree<A>, Tree<KeyValuePair<A, bool>>> l, Func<Tree<A>, Tree<KeyValuePair<A, bool>>> r, Tree<A> t) => (Tree<A> t2) =>
            Node(new KeyValuePair<A, bool>(t2.Data, object.ReferenceEquals(t, t2)),
                 l(t2.Left), r(t2.Right)),
            x => y => null, tree)(tree2);
    }
}

Dans ce deuxième exemple, un autre arbre est reconstruit différemment:

class Example
{
    // original version recreates entire tree, yuck 
    public static Tree<int> Change5to0(Tree<int> tree)
    {
        return Tree.FoldTree((int x, Tree<int> l, Tree<int> r) => Tree.Node(x == 5 ? 0 : x, l, r), null, tree);
    }

    // here it is with XFold - same as original, only with Xs 
    public static Tree<int> XChange5to0(Tree<int> tree)
    {
        return Tree.XFoldTree((int x, Tree<int> l, Tree<int> r, Tree<int> orig) =>
            Tree.XNode(x == 5 ? 0 : x, l, r)(orig), _ => null, tree);
    }
}

Et dans ce troisième exemple, le pliage d'un arbre est utilisé pour dessiner:

class MyWPFWindow : Window 
{
    void Draw(Canvas canvas, Tree<KeyValuePair<int, bool>> tree)
    {
        // assumes canvas is normalized to 1.0 x 1.0 
        Tree.FoldTree((KeyValuePair<int, bool> kvp, Func<Transform, Transform> l, Func<Transform, Transform> r) => trans =>
        {
            // current node in top half, centered left-to-right 
            var tb = new TextBox();
            tb.Width = 100.0; 
            tb.Height = 100.0;
            tb.FontSize = 70.0;
                // the tree is a "diff tree" where the bool represents 
                // "ReferenceEquals" differences, so color diffs Red 
            tb.Foreground = (kvp.Value ? Brushes.Black : Brushes.Red);
            tb.HorizontalContentAlignment = HorizontalAlignment.Center;
            tb.VerticalContentAlignment = VerticalAlignment.Center;
            tb.RenderTransform = AddT(trans, TranslateT(0.25, 0.0, ScaleT(0.005, 0.005, new TransformGroup())));
            tb.Text = kvp.Key.ToString();
            canvas.Children.Add(tb);
            // left child in bottom-left quadrant 
            l(AddT(trans, TranslateT(0.0, 0.5, ScaleT(0.5, 0.5, new TransformGroup()))));
            // right child in bottom-right quadrant 
            r(AddT(trans, TranslateT(0.5, 0.5, ScaleT(0.5, 0.5, new TransformGroup()))));
            return null;
        }, _ => null, tree)(new TransformGroup());
    }

    public MyWPFWindow(Tree<KeyValuePair<int, bool>> tree)
    {
        var canvas = new Canvas();
        canvas.Width=1.0;
        canvas.Height=1.0;
        canvas.Background = Brushes.Blue;
        canvas.LayoutTransform=new ScaleTransform(200.0, 200.0);
        Draw(canvas, tree);
        this.Content = canvas;
        this.Title = "MyWPFWindow";
        this.SizeToContent = SizeToContent.WidthAndHeight;
    }
    TransformGroup AddT(Transform t, TransformGroup tg) { tg.Children.Add(t); return tg; }
    TransformGroup ScaleT(double x, double y, TransformGroup tg) { tg.Children.Add(new ScaleTransform(x,y)); return tg; }
    TransformGroup TranslateT(double x, double y, TransformGroup tg) { tg.Children.Add(new TranslateTransform(x,y)); return tg; }

    [STAThread]
    static void Main(string[] args)
    {
        var app = new Application();
        //app.Run(new MyWPFWindow(Tree.DiffTree(Tree.Tree7,Example.Change5to0(Tree.Tree7))));
        app.Run(new MyWPFWindow(Tree.DiffTree(Tree.Tree7, Example.XChange5to0(Tree.Tree7))));
    }
}    

Answer 2

Je lis plus souvent, y compris un article de Micorosft Research sur la programmation fonctionnelle. avec des catamorphismes (& "; bananes &";) , et il semble que le catamorphisme se réfère uniquement à une fonction prenant une liste et généralement le décompose en une seule valeur (IEnumerable<A> => B), comme Max(), Min() et, dans le cas général, Aggregate(), ce serait un catamorphisme pour les listes.

J’avais l’impression qu’il s’agissait auparavant de créer une fonction permettant de généraliser différents plis, de manière à pouvoir plier un arbre et une liste. Il se peut qu’il existe toujours une telle chose, une sorte de foncteur ou flèche peut-être, mais pour le moment cela dépasse mon niveau de compréhension.

Answer 3

La réponse de Brian au premier paragraphe est correcte. Mais son exemple de code ne montre pas vraiment comment résoudre des problèmes similaires dans un style C #. Considérons une classe simple node:

class Node {
  public Node Left;
  public Node Right;
  public int value;
  public Node(int v = 0, Node left = null, Node right = null) {
    value = v;
    Left = left;
    Right = right;
  }
}

Avec cela, nous pouvons créer un arbre dans main:

var Tree = 
    new Node(4,
      new Node(2, 
        new Node(1),
        new Node(3)
      ),
      new Node(6,
        new Node(5),
        new Node(7)
      )
    );

Nous définissons une fonction de repli générique dans l'espace de noms de Node:

public static R fold<R>(
  Func<int, R, R, R> combine,
  R leaf_value,
  Node tree) {

  if (tree == null) return leaf_value;

  return 
    combine(
      tree.value, 
      fold(combine, leaf_value, tree.Left),
      fold(combine, leaf_value, tree.Right)
    );
}

Pour les catamorphismes, nous devons spécifier les états des données, les nœuds peuvent être nuls ou avoir des enfants. Les paramètres génériques déterminent ce que nous faisons dans les deux cas. Notez que la stratégie d’itération (dans ce cas la récursion) est cachée dans la fonction fold.

Maintenant, au lieu d'écrire:

public static int Sum_Tree(Node tree){
  if (tree == null) return 0;
  var accumulated = tree.value;
  accumulated += Sum_Tree(tree.Left);
  accumulated += Sum_Tree(tree.Right);
  return accumulated; 
}

Nous pouvons écrire

public static int sum_tree_fold(Node tree) {
  return Node.fold(
    (x, l, r) => x + l + r,
    0,
    tree
  );
}

Élégant, simple, type vérifié, maintenable, etc. Facile à utiliser Console.WriteLine(Node.Sum_Tree(Tree));.

Il est facile d’ajouter de nouvelles fonctionnalités:

public static List<int> In_Order_fold(Node tree) {
  return Node.fold(
    (x, l, r) => {
      var tree_list = new List<int>();
      tree_list.Add(x);
      tree_list.InsertRange(0, l);
      tree_list.AddRange(r);
      return tree_list;
    },
    new List<int>(),
    tree
  );
}
public static int Height_fold(Node tree) {
  return Node.fold(
    (x, l, r) => 1 + Math.Max(l, r),
    0,
    tree
  );
}

F # l'emporte dans la catégorie de concision pour In_Order_fold, mais il faut s'y attendre lorsque le langage fournit des opérateurs dédiés à la construction et à l'utilisation de listes.

La différence dramatique entre C # et F # semble être due à l'utilisation de fermetures par F #, agissant comme des structures de données implicites, pour déclencher l'optimisation de l'appel final. L'exemple de la réponse de Brian prend également en compte les optimisations de compte en F #, pour éviter la reconstruction de l'arbre. Je ne suis pas sûr que C # prenne en charge l'optimisation de l'appel final, et peut-être que <=> pourrait être mieux écrit, mais aucun de ces points n'est pertinent lorsqu'il est question d'exprimer comment C # est expressif lorsqu'il traite de ces catamorphismes.

Lors de la traduction de code entre les langues, vous devez comprendre l'idée de base de la technique, puis l'implémenter en termes de primitives de langue.

Peut-être pourrez-vous maintenant convaincre vos collègues C # de prendre les plis plus au sérieux.

Answer 4

  

Je comprends que c'est un   généralisation des plis (c.-à-d. cartographie   une structure de plusieurs valeurs à un   valeur, y compris une liste de valeurs à   une autre liste).

Je ne dirais pas une valeur. Elle la mappe dans une autre structure.

Peut-être qu'un exemple éclaircirait. On dit du résumé sur une liste.

foldr (\ x - > \ y - > x + y) 0 [1,2,3,4,5]

Maintenant, cela réduirait à 15. Mais en réalité, il peut être visualisé en correspondance avec une structure purement syntaxique 1 + 2 + 3 + 4 + 5 + 0. C'est juste que le langage de programmation (dans le cas ci-dessus, haskell) sait comment réduire la structure syntaxique ci-dessus à 15.

En gros, un catamorphisme remplace un constructeur de données par un autre.En cas de liste ci-dessus,

[1,2,3,4,5] = 1: 2: 3: 4: 5: [] (: est l'opérateur contre, [] est l'élément nul) le catamorphisme ci-dessus remplacé: par + et [] par 0.

Il peut être généralisé à tout type de données récursif.

Answer 5

Brian avait une excellente série de billets sur son blog. De plus, Channel9 avait une belle vidéo Il n'y a pas de sucre syntaxique LINQ pour .Aggregate (), donc est-ce important de savoir s'il a ou non la définition de la méthode LINQ Aggregate? L'idée est bien sûr la même. Plier sur les arbres ... Nous avons d’abord besoin d’un nœud ... peut-être que vous utiliseriez Tuple, mais ceci est plus clair:

public class Node<TData, TLeft, TRight>
{
    public TLeft Left { get; private set; }
    public TRight Right { get; private set; }
    public TData Data { get; private set; }
    public Node(TData x, TLeft l, TRight r){ Data = x; Left = l; Right = r; }
}

Ensuite, en C #, nous pouvons créer un type récursif, même si cela est inhabituel:

public class Tree<T> : Node</* data: */ T, /* left: */ Tree<T>, /* right: */ Tree<T>>
{
    // Normal node:
    public Tree(T data, Tree<T> left, Tree<T> right): base(data, left, right){}
    // No children:
    public Tree(T data) : base(data, null, null) { }
}

Maintenant, je citerai quelques-uns du code de Brian, avec de légères modifications de style LINQ:

1. En C #, le pli s'appelle Agrégat
Les
2. méthodes LINQ sont des méthodes d'extension dont l'élément est le premier paramètre avec " this "key-key.
3. La boucle peut être privée

...

public static class TreeExtensions
{
    private static R Loop<A, R>(Func<A, R, R, Tree<A>, R> nodeF, Func<Tree<A>, R> leafV, Tree<A> t, Func<R, R> cont)
    {
        if (t == null) return cont(leafV(t));
        return Loop(nodeF, leafV, t.Left, lacc =>
                Loop(nodeF, leafV, t.Right, racc =>
                cont(nodeF(t.Data, lacc, racc, t))));
    }    
    public static R XAggregateTree<A, R>(this Tree<A> tree, Func<A, R, R, Tree<A>, R> nodeF, Func<Tree<A>, R> leafV)
    {
        return Loop(nodeF, leafV, tree, x => x);
    }

    public static R Aggregate<A, R>(this Tree<A> tree, Func<A, R, R, R> nodeF, R leafV)
    {
        return tree.XAggregateTree((x, l, r, _) => nodeF(x, l, r), _ => leafV);
    }
}

Maintenant, l'utilisation est plutôt du style C #:

[TestMethod] // or Console Application:
static void Main(string[] args)
{
    // This is our tree:
    //     4 
    //  2     6 
    // 1 3   5 7 
    var tree7 = new Tree<int>(4, new Tree<int>(2, new Tree<int>(1), new Tree<int>(3)),
                            new Tree<int>(6, new Tree<int>(5), new Tree<int>(7)));

    var sumTree = tree7.Aggregate((x, l, r) => x + l + r, 0);
    Console.WriteLine(sumTree); // 28
    Console.ReadLine();

    var inOrder = tree7.Aggregate((x, l, r) =>
        {
            var tmp = new List<int>(l) {x};
            tmp.AddRange(r);
            return tmp;
        }, new List<int>());
    inOrder.ForEach(Console.WriteLine); // 1 2 3 4 5 6 7
    Console.ReadLine();

    var heightTree = tree7.Aggregate((_, l, r) => 1 + (l>r?l:r), 0);
    Console.WriteLine(heightTree); // 3
    Console.ReadLine();
}

J'aime toujours plus F #.