我正在尝试学习有关Catamorphism的知识，我已经阅读了维基百科文章和Inside F#博客上该主题系列的前几篇文章。
我了解它是折叠的一般化（即将许多值的结构映射到一个值，包括将值列表映射为另一个列表）。 我发现fold-list和fold-tree是一个典型的例子。
是否能够在C＃中使用LINQ的Aggregate操作或其他高阶方法来实现它？
什么是Catamorphism？它能在C# 3.0中实现吗？
27
- marxidad
2
如果这里的答案能够整合到维基百科文章中，那将是非常棒的。 - Edward Z. Yang
6小心创建循环引用。 - Joel Coehoorn
5个回答
32
LINQ的Aggregate()仅针对IEnumerables。通常，Catamorphisms是指任意数据类型的折叠模式。因此，Aggregate()用于IEnumerables，而FoldTree（下面）用于Trees（下面）; 两者都是各自数据类型的Catamorphisms。
我将系列的第4部分中的一些代码翻译成了C#。 代码如下。请注意，等效的F#使用三个小于字符（用于泛型类型参数注释），而此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<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);
}
}
可以折叠树，例如，可以测量两个树是否具有不同的节点：
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);
}
}
在这个第二个示例中，另一棵树以不同的方式重构：
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);
}
}
在这第三个例子中，折叠一棵树被用于绘画：
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))));
}
}
- Brian
4
2我的天啊！但说真的，我曾经试着用这样的例子来与我的同事们比较一下 F#，他们的反应是为什么我要首先写这个。 - gradbot
19没错。当你所知道的只有C#时，想到计算树的高度、变换树的形状以及在WPF画布上绘制树这些看似不相关的任务，实际上有一个共同的核心，这种感觉很疯狂。而且“Tree”代码本身就更加证明了这一点，因为它非常难懂。但是当你用F#编写它们时，每个单独的实现都有DRY（不要重复自己）的气息，并且这种共性显而易见，语言让你抓住了这种共性的精髓。这就像成瘾一样，让你想知道自己一直以来缺少了哪些抽象概念。 - Brian
5我将收藏这个答案，但即使过了30年，我仍然不会明白那些代码到底在做什么…… - surfasb
11
我最近阅读了更多的内容，包括微软研究论文中有关使用“bananas”进行函数式编程的文章。看起来catamorphism只是指任何接收列表并通常将其分解为单个值（IEnumerable<A> => B）的函数，例如Max()，Min()和一般情况下的Aggregate()都可以用于列表的catamorphisms。
我之前认为这是一种创建函数的方法，可以概括不同的折叠操作（folds），使其可以对树和列表进行折叠。可能还存在这样一种东西，类似于functor或arrow，但现在这已经超出了我的理解范围。
- marxidad
2
正如你所说，对于列表折叠来说，一般情况是类型为 IEnumerable<A> → B。因此，Aggregate 并不像列表折叠那样通用，因为它的类型是
T Aggregate<T>(this IEnumerable<T> src, Func<T, T, T> f)。然而，在 C#/.NET 中，默认情况下并没有更通用的 B Fold<A>(this IEnumerable<A>, B init, Func<A, B, B> f)。 - sshine@SimonShine 差不多了 ;) - Mark Cidade
5
在第一段中，Brian的回答是正确的。但是他的代码示例并不能真正反映出人们如何以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;
}
}
使用这个方法，我们可以在主函数中创建一棵树：
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<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)
);
}
对于离散数学中的 catamorphisms，我们需要指定数据状态。节点可以为空，也可以有子节点。通用参数决定了我们在每种情况下所采取的操作。需要注意的是，迭代策略（在本例中是递归）被隐藏在折叠函数内部。
现在，我们不再需要编写以下代码：
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));。
添加新功能也很容易：
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#在简洁性方面赢得了
In_Order_fold类别，但这是可以预料的，因为该语言提供了专用操作符以构建和使用列表。C#和F#之间的明显差异似乎源于F#使用闭包作为隐式数据结构来触发尾递归优化。Brian回答中的示例还考虑了F#中的优化，以避免重构树形结构。我不确定C#是否支持尾递归优化，也许可以更好地编写
In_Order_fold，但是当讨论C#处理这些Catamorphisms时的表现时，这两点都不相关。在将代码从一种语言翻译成另一种语言时，您需要理解技术的核心思想，然后根据该语言的基本元素实现该思想。
也许现在你能说服你的C#同事更认真地对待folds。
- Polymer
3
我理解这是对fold的一种概括，即将多个值的结构（包括列表）映射到一个值（或另一个列表）中。
我不会说只映射到一个值，而是将其映射为另一个结构。
也许举个例子会更清晰。假设对列表进行求和。
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用+替换了:，用0替换了[]。
它可以推广到任何递归数据类型。
我不会说只映射到一个值，而是将其映射为另一个结构。
也许举个例子会更清晰。假设对列表进行求和。
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用+替换了:，用0替换了[]。
它可以推广到任何递归数据类型。
- Thiagarajan
2
布莱恩在他的博客中有一系列很棒的文章。此外，Channel9有一个好视频。对于.Aggregate()，LINQ没有语法糖，所以它是否具有LINQ Aggregate方法的定义并不重要？当然，思路是相同的。折叠树......首先我们需要一个节点......也许可以使用元组，但这更清晰：
然后，在C#中，我们可以创建一个递归类型，尽管这很不寻常：
现在，我将引用一些Brian的代码，并进行轻微的LINQ风格修改：
现在，使用方式非常类似于C#风格：
我仍然更喜欢 F#。
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; }
}
然后，在C#中，我们可以创建一个递归类型，尽管这很不寻常：
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) { }
}
现在，我将引用一些Brian的代码，并进行轻微的LINQ风格修改：
- C#中的Fold被称为Aggregate
- LINQ方法是扩展方法，第一个参数是项，并带有“this”关键字。
- 循环可以是私有的
...
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);
}
}
现在，使用方式非常类似于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();
}
我仍然更喜欢 F#。
- Tuomas Hietanen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接