什么是catamorphism，可以在C＃3.0中实现吗？
我正在尝试了解catamorphisms，我已经阅读了维基百科文章以及F＃博客上F＃主题系列中的前几篇文章 。
我理解这是折叠的概括（即，将许多值的结构映射到一个值，包括值列表到另一个列表）。 我认为折叠列表和折叠树是一个典型的例子。
可以使用LINQ的Aggregate运算符或其他一些更高阶的方法在C＃中显示它吗？
LINQ的Aggregate（）仅适用于IEnumerables。 一般来说，Catamorphisms指的是任意数据类型的折叠模式。 所以Aggregate（）对于IEnumerables来说是FoldTree（下面）对于树（下面）; 两者都是各自数据类型的catamorphisms。
我将系列的第4部分中的一些代码翻译成了C＃。 代码如下。 请注意，等效的F＃使用了三个小于字符（对于generics类型参数注释），而这个C＃代码使用了超过60个。这就是为什么没有人在C＃中编写这样的代码的证据 – 有太多的类型注释。 我提供代码，以防它知道C＃而不是F＃的人玩这个。 但是C＃中的代码非常密集，很难理解。
给定二叉树的以下定义：
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 // use null for Leaf { public T Data { get; private set; } public Tree Left { get; private set; } public Tree Right { get; private set; } public Tree(T data, Tree left, Tree rright) { this.Data = data; this.Left = left; this.Right = right; } public static Tree Node (T data, Tree left, Tree right) { return new Tree (data, left, right); } }
人们可以折叠树木，例如测量两棵树是否有不同的节点：
class Tree { public static Tree 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(Func, R> nodeF, Func, R> leafV, Tree tree) { return Loop(nodeF, leafV, tree, x => x); } public static R Loop(Func, R> nodeF, Func, R> leafV, Tree t, Func 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(Func nodeF, R leafV, Tree tree) { return XFoldTree((x, l, r, _) => nodeF(x, l, r), _ => leafV, tree); } public static Func, Tree> XNode(A x, Tree l, Tree r) { return (Tree 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> DiffTree (Tree tree, Tree tree2) { return XFoldTree((A x, Func, Tree>> l, Func, Tree>> r, Tree t) => (Tree t2) => Node(new KeyValuePair(t2.Data, object.ReferenceEquals(t, t2)), l(t2.Left), r(t2.Right)), x => y => null, tree)(tree2); } }
在第二个示例中，另一个树的重建方式不同：
class Example { // original version recreates entire tree, yuck public static Tree Change5to0(Tree tree) { return Tree.FoldTree((int x, Tree l, Tree 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 XChange5to0(Tree tree) { return Tree.XFoldTree((int x, Tree l, Tree r, Tree orig) => Tree.XNode(x == 5 ? 0 : x, l, r)(orig), _ => null, tree); } }
在第三个例子中，折叠树用于绘图：
class MyWPFWindow : Window { void Draw(Canvas canvas, Tree> tree) { // assumes canvas is normalized to 1.0 x 1.0 Tree.FoldTree((KeyValuePair kvp, Func l, Func 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> 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)))); } }
我一直在做更多的阅读，包括关于使用catamorphisms（“香蕉”）的函数式编程的Micorosft Research论文，似乎catamorphism只是指任何获取列表并通常将其分解为单个值的函数（ IEnumerable => B ），如Max（） ， Min（） ，在一般情况下， Aggregate（） ，都是列表的catamorphisms。
我之前的印象是它提到了一种创建可以概括不同折叠的函数的方法，以便它可以折叠树和列表。 实际上可能还有这样的东西，某种类型的仿函数或箭头 ，但现在这超出了我的理解水平。
布莱恩在第一段中的答案是正确的。 但他的代码示例并没有真正反映出如何解决C＃风格中的类似问题。 考虑一个简单的类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; } }
有了这个，我们可以在main中创建一个树：
var Tree = new Node(4, new Node(2, new Node(1), new Node(3) ), new Node(6, new Node(5), new Node(7) ) );
我们在Node的命名空间中定义了一个通用的折叠函数：
public static R fold( Func 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) ); }
对于catamorphisms，我们应该指定数据的状态，节点可以为null，或者有子节点。 通用参数决定了我们在任何一种情况下的工作。 请注意，迭代策略（在本例中为递归）隐藏在fold函数中。
现在而不是写：
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; }
我们可以写
public static int sum_tree_fold(Node tree) { return Node.fold( (x, l, r) => x + l + r, 0, tree ); }
优雅，简单，类型检查，可维护等。易于使用Console.WriteLine(Node.Sum_Tree(Tree)); 。
添加新function很容易：
public static List In_Order_fold(Node tree) { return Node.fold( (x, l, r) => { var tree_list = new List (); tree_list.Add(x); tree_list.InsertRange(0, l); tree_list.AddRange(r); return tree_list; }, new List (), tree ); } public static int Height_fold(Node tree) { return Node.fold( (x, l, r) => 1 + Math.Max(l, r), 0, tree ); }
F＃在In_Order_fold的简洁类别中In_Order_fold但是当语言提供用于构造和使用列表的专用运算符时，这是预期的。
C＃和F＃之间的巨大差异似乎是由于F＃使用闭包，充当隐式数据结构，用于触发尾调用优化。 Brian的回答中的例子也考虑了F＃中的优化，以避免重建树。 我不确定C＃是否支持尾调用优化，也许In_Order_fold可以更好地编写，但在讨论C＃在处理这些Catamorphisms时的表达方式时，这些点都不相关。
在语言之间翻译代码时，您需要了解该技术的核心思想，然后根据语言的原语实现该思想。
也许现在你将能够说服你的C＃同事更认真地对待折叠。
我理解这是折叠的概括（即，将许多值的结构映射到一个值，包括值列表到另一个列表）。
我不会说一个值。它将它映射到另一个结构。
也许一个例子可以澄清。对于列表的总结。
foldr（\ x – > \ y – > x + y）0 [1,2,3,4,5]
现在这将减少到15.但实际上，它可以被视为映射到纯粹的语法结构1 + 2 + 3 + 4 + 5 + 0.这只是编程语言（在上面的例子中，haskell）知道如何将上述句法结构减少到15。
基本上，一个catamorphism将一个数据构造函数替换为另一个数据构造函数。如果是上面的列表，
[1,2,3,4,5] = 1：2：3：4：5：[]（：是cons运算符，[]是nil元素）上面的catamorphism取代：with +和[] with 0 。
它可以推广到任何递归数据类型。
Brian在他的博客中发布了很多post。 Channel9还有一个很棒的video 。 .Aggregate（）没有LINQ语法糖，所以它是否具有LINQ聚合方法的定义是否重要？ 这个想法当然是一样的。 折叠树…首先我们需要一个节点…也许可以使用元组，但这更清楚：
public class Node { 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; } }
然后，在C＃中我们可以创建一个递归类型，即使这是不寻常的：
public class Tree : Node, /* right: */ Tree > { // Normal node: public Tree(T data, Tree left, Tree right): base(data, left, right){} // No children: public Tree(T data) : base(data, null, null) { } }
现在，我将引用一些Brian的代码，进行轻微的LINQ风格修改：
- 在C＃中，Fold称为Aggregate
- LINQ方法是扩展方法，它将项目作为带有“this”关键字的第一个参数。
- 循环可以是私有的
…
public static class TreeExtensions { private static R Loop(Func, R> nodeF, Func, R> leafV, Tree t, Func 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(this Tree tree, Func, R> nodeF, Func, R> leafV) { return Loop(nodeF, leafV, tree, x => x); } public static R Aggregate(this Tree tree, Func nodeF, R leafV) { return tree.XAggregateTree((x, l, r, _) => nodeF(x, l, r), _ => leafV); } }
现在，用法非常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(4, new Tree (2, new Tree (1), new Tree (3)), new Tree (6, new Tree (5), new Tree (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 (l) {x}; tmp.AddRange(r); return tmp; }, new List ()); 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(); }
我还是喜欢F＃。