¿Qué es un catamorfismo y puede implementarse en C # 3.0?
https://stackoverflow.com/questions/196294
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy tratando de aprender sobre catamorfismos y he leído el artículo de Wikipedia y las primeras dos publicaciones en la serie del tema para 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 deduzco que la lista de plegado y el árbol de plegado son un ejemplo canónico.
¿Se puede demostrar que esto se hace en C #, utilizando el operador Aggregate de LINQ o algún otro método de orden superior?
Solución
LINQ's Aggregate() es solo para IEnumerables. Los catamorfismos en general se refieren al patrón de plegado para un tipo de datos arbitrario. Entonces FoldTree es Trees lo que <=> (abajo) es <=> (abajo); ambos son catamorfismos para sus respectivos tipos de datos.
Traduje parte del código en parte 4 de la serie en C #. El código está abajo. Tenga en cuenta que el F # equivalente usa tres caracteres menores que (para anotaciones de parámetros de tipo genérico), mientras que este código de C # usa más de 60. Esto es 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 tan denso en C # que 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 p. mida 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))));
}
}
Otros consejos
He estado leyendo más, incluido un artículo de Micorosft Research sobre programación funcional con catamorfismos (" bananas ") , y parece que catamorphism solo se refiere a cualquier función que toma una lista y típicamente lo divide en un solo valor (IEnumerable<A> => B), como Max(), Min(), y en el caso general, Aggregate(), todo sería un catamorfismo para las listas.
Anteriormente tenía la impresión de que se refería a una forma de crear una función que pueda generalizar diferentes pliegues, de modo que pueda plegar un árbol y una lista. Puede que todavía exista tal cosa, algún tipo de functor o arrow , pero en este momento eso está más allá de mi nivel de comprensión.
La respuesta de Brian en el primer párrafo es correcta. Pero su ejemplo de código realmente no refleja cómo se resolverían problemas similares en un estilo C #. Considere una clase 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;
}
}
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érica en el espacio de nombres 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)
);
}
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, la recursión) 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 marcado, mantenible, etc. Fácil de usar Console.WriteLine(Node.Sum_Tree(Tree));.
Es fácil agregar nueva funcionalidad:
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 por parte de F #, para actuar como estructuras de datos implícitas, para activar la optimización de la llamada de cola. El ejemplo en la respuesta de Brian también incluye las optimizaciones de cuenta en F #, para esquivar la reconstrucción del árbol. No estoy seguro de que C # sea compatible con la optimización de llamadas de cola, y tal vez <=> podría escribirse mejor, pero ninguno de estos puntos es relevante cuando se discute cuán expresivo es C # cuando se trata con estos catamorfismos.
Al traducir código entre idiomas, debe comprender la idea central de la técnica y luego implementar la idea en términos de las primitivas del lenguaje.
Tal vez ahora pueda convencer a sus compañeros de trabajo de C # para que tomen los pliegues más en serio.
Entiendo que es un generalización de pliegues (es decir, mapeo una estructura de muchos valores a uno valor, incluida una lista de valores para otra lista).
No diría un valor, lo asigna a otra estructura.
Quizás un ejemplo aclararía. Digamos la sumatoria sobre 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 el mapeo 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 contras, [] es el elemento nulo) el catamorfismo anterior reemplazado: con + y [] con 0.
Se puede generalizar a cualquier tipo de datos recursivo.
Brian tuvo una gran serie de publicaciones en su blog. También Channel9 tenía un bonito video . No hay azúcar sintáctico LINQ para .Aggregate (), entonces ¿importa si tiene la definición del método LINQ Aggregate o no? La idea es, por supuesto, la misma. Plegándose sobre los árboles ... Primero necesitamos un Nodo ... tal vez podría usarse Tuple, pero esto está 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é algunos de los códigos de Brian, con ligeras modificaciones al estilo LINQ:
- En C # Fold se llama Agregado
- Los métodos LINQ son métodos de Extensión que tienen el elemento como primer parámetro con " this " -keyword.
- El bucle 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 estilo 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();
}
Todavía me gusta F # más.
