¿Qué es un catamorfismo y se puede implementar en C#3.0?

f# functional-programming

Question

Estoy tratando de aprender sobre catamorfilos y he leído el artículo de Wikipedia y las primeras publicaciones de la serie del tema de F # en el blog Inside F # .

Entiendo que es una generalización de pliegues (es decir, mapear una estructura de muchos valores a un valor, incluida una lista de valores a otra lista). Y me doy cuenta de que la lista doble y el árbol plegable es un ejemplo canónico.

¿Se puede demostrar que se hace en C #, usando el operador Aggregate de LINQ o algún otro método de orden superior?

Answer 1

He estado leyendo más, incluido un artículo de investigación de Micorosft sobre programación funcional con catamorfilos ("plátanos") , y parece que el catamorfismo solo se refiere a cualquier función que toma una lista y generalmente la divide en un solo valor ( IEnumerable<A> => B ), como Max () , Min () , y en el caso general, Aggregate () , todos serían cataforismos para las listas.

Antes tenía la impresión de que se refería a una forma de crear una función que puede generalizar diferentes pliegues, de modo que pueda doblar un árbol y una lista. Puede que todavía exista tal cosa, algún tipo de funtor o flecha, pero ahora está más allá de mi nivel de comprensión.

Answer 2

Entiendo que es una generalización de pliegues (es decir, mapear una estructura de muchos valores a un valor, incluida una lista de valores a otra lista).

No diría un valor. Lo mapea en otra estructura.

Tal vez un ejemplo aclare. Pongamos una suma en una lista.

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

Ahora esto se reduciría a 15. Pero en realidad, se puede ver mapear a una estructura puramente sintáctica 1 + 2 + 3 + 4 + 5 + 0. Es solo que el lenguaje de programación (en el caso anterior, haskell) sabe cómo reducir la estructura sintáctica anterior a 15.

Básicamente, un catamorfismo reemplaza un constructor de datos con otro. En el caso de la lista anterior,

[1,2,3,4,5] = 1: 2: 3: 4: 5: [] (: es el operador cons, [] es el elemento nulo) el catamorfismo anterior reemplazado: con + y [] con 0 .

Se puede generalizar a cualquier tipo de datos recursivos.

Answer 3

Brian tenía una gran serie de publicaciones en su blog. También Channel9 tuvo un buen video . No hay azúcar sintáctico LINQ para .Agregar (), ¿qué importancia tiene si tiene la definición de método LINQ Agregado o no? La idea es, por supuesto, lo mismo. Doblando árboles ... Primero necesitamos un Nodo ... tal vez se pueda usar Tuple, pero esto es más claro:

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; }
}

Entonces, en C # podemos hacer un tipo recursivo, incluso esto es inusual:

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) { }
}

Ahora, citaré parte del código de Brian, con ligeras modificaciones al estilo LINQ:

1. En C # Fold se llama Agregado
2. Los métodos LINQ son métodos de extensión que tienen el elemento como primer parámetro con "this" -keyword.
3. Loop puede ser privado

...

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);
    }
}

Ahora, el uso es bastante C # -style:

[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();
}

Todavía me gusta F # más.

Answer 4

La respuesta de Brian en el primer párrafo es correcta. Pero su ejemplo de código no refleja realmente cómo se resolverían problemas similares en un estilo C #. Considere un node clase simple:

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;
  }
}

Con esto podemos crear un árbol en main:

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

Definimos una función de plegado genérico en el espacio de nombres del 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)
    );
}

Para los catamorfismos, debemos especificar los estados de los datos, los Nodos pueden ser nulos o tener hijos. Los parámetros genéricos determinan lo que hacemos en cualquier caso. Observe que la estrategia de iteración (en este caso, recursividad) está oculta dentro de la función de plegado.

Ahora en lugar de escribir:

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; 
}

Podemos escribir

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

Elegante, simple, tipo revisado, mantenible, etc. Fácil de usar Console.WriteLine(Node.Sum_Tree(Tree)); .

Es fácil agregar nuevas funcionalidades:

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 # gana en la categoría de concisión para In_Order_fold pero eso es de esperar cuando el lenguaje proporciona operadores dedicados para construir y usar listas.

La diferencia dramática entre C # y F # parece deberse al uso de cierres de F #, para actuar como estructuras de datos implícitas, para activar la optimización de la cola de llamadas. El ejemplo en la respuesta de Brian también toma en cuenta las optimizaciones en F #, para evitar la reconstrucción del árbol. No estoy seguro de que C # sea compatible con la optimización de la cola de llamadas, y tal vez In_Order_fold podría escribirse mejor, pero ninguno de estos dos puntos es relevante cuando se analiza cuán expresivo es C # cuando se trata de estos catamorfilos.

Al traducir el código entre idiomas, necesita comprender la idea central de la técnica y luego implementar la idea en términos de las primitivas del lenguaje.

Quizás ahora puedas convencer a tus compañeros de trabajo de C # para que se doblen más seriamente.

Answer 5

El Agregado de LINQ () es solo para IEnumerables. Los catamorfismos en general se refieren al patrón de plegado para un tipo de datos arbitrario. Así que Aggregate () es para IEnumerables lo que FoldTree (a continuación) es para Trees (abajo); ambos son cataforismos para sus respectivos tipos de datos.

Traduje algo del código en la parte 4 de la serie a C #. El código está abajo. Tenga en cuenta que el F # equivalente usó tres caracteres menores que (para anotaciones de parámetros de tipo genérico), mientras que este código C # usa más de 60. Esta es la evidencia de por qué nadie escribe dicho código en C #; hay demasiadas anotaciones de tipo. Presento el código en caso de que ayude a las personas que conocen C # pero no F # a jugar con esto. Pero el código es muy denso en C #, es muy difícil de entender.

Dada la siguiente definición para un árbol binario:

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);
    }
}

Uno puede doblar árboles y, por ejemplo, medir si dos árboles tienen nodos diferentes:

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);
    }
}

En este segundo ejemplo, otro árbol se reconstruye de manera diferente:

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);
    }
}

Y en este tercer ejemplo, doblar un árbol se usa para dibujar:

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))));
    }
}