Что такое катаморфизм и можно ли его реализовать в C# 3.0?
Я пытаюсь узнать о катаморфизмах, и я прочитал статью в Википедии и первые пару постов из серии тем для F# в блоге Inside F#.
Я понимаю, что это обобщение сгибов (т. Е. Отображение структуры из многих значений в одно значение, включая список значений в другой список). И я понимаю, что список сгиба и дерево сгиба - это канонический пример.
Можно ли показать, что это сделано в C# с использованием LINQ? Aggregate оператор или какой-то другой метод высшего порядка?
5 ответов
Агрегат () LINQ предназначен только для IEnumerables. Катаморфизмы в целом относятся к схеме свертывания для произвольного типа данных. Таким образом, Aggregate() для IEnumerables означает, что FoldTree (ниже) для деревьев (ниже); оба являются катаморфизмами для их соответствующих типов данных.
Я перевел часть кода в части 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))));
}
}
Я занимаюсь чтением, в том числе исследовательской работой Micorosft по функциональному программированию с катаморфизмом ("бананами"), и кажется, что катаморфизм просто относится к любой функции, которая берет список и обычно разбивает его на одно значение (IEnumerable<A> => B), как Max (), Min () и в общем случае Aggregate (), будут катаморфизмами для списков.
Ранее у меня сложилось впечатление, что он ссылается на способ создания функции, которая может обобщать различные сгибы, чтобы можно было сгибать дерево и список. Возможно, что-то еще может быть, какой-то функтор или стрелка, но сейчас это за пределами моего уровня понимания.
Ответ Брайана в первом абзаце правильный. Но его пример кода на самом деле не отражает, как можно было бы решить подобные проблемы в стиле 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)
);
}
Для катаморфизмов мы должны указать состояния данных, узлы могут быть нулевыми или иметь детей. Общие параметры определяют, что мы делаем в любом случае. Обратите внимание, что стратегия итерации (в данном случае рекурсия) скрыта внутри функции сгиба.
Теперь вместо того, чтобы писать:
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#, которые действуют как неявные структуры данных для запуска оптимизации хвостового вызова. Пример в ответе Брайана также учитывает оптимизацию в F# для уклонения от реконструкции дерева. Я не уверен, что C# поддерживает оптимизацию хвостового вызова, и, возможно, In_Order_fold можно было бы написать лучше, но ни один из этих пунктов не имеет отношения к обсуждению того, насколько выразителен C# при работе с этими катаморфизмами.
При переводе кода между языками вам необходимо понять основную идею техники, а затем реализовать ее в терминах языковых примитивов.
Возможно, теперь вы сможете убедить своих коллег по C# более серьезно относиться к складкам.
У Брайана была отличная серия постов в его блоге. Также у Channel9 было хорошее видео. Для.Aggregate() нет синтаксического сахара LINQ, поэтому имеет ли значение определение метода LINQ Aggregate или нет? Идея, конечно, та же. Складывание поверх деревьев... Сначала нам нужен узел... может быть, можно использовать Tuple, но это более понятно:
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) { }
}
Теперь я процитирую часть кода Брайана с небольшими изменениями в стиле 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# больше.
Я понимаю, что это обобщение сгибов (т. Е. Отображение структуры из многих значений в одно значение, включая список значений в другой список).
Я бы не сказал одно значение. Это отображает его в другую структуру.
Может быть, пример прояснит, скажем, суммирование по списку.
Foldr (\x -> \y -> x + y) 0 [1,2,3,4,5]
Теперь это уменьшилось бы до 15. Но на самом деле, его можно рассматривать как отображение на чисто синтаксическую структуру 1 + 2 + 3 + 4 + 5 + 0. Просто язык программирования (в приведенном выше случае haskell) знает, как уменьшить вышеупомянутую синтаксическую структуру до 15.
По сути, катаморфизм заменяет один конструктор данных другим. В случае списка выше,
[1,2,3,4,5] = 1: 2: 3: 4: 5: [] (: оператор cons,[] - нулевой элемент). Приведенный выше катаморфизм заменен на + и [] на 0,
Он может быть обобщен для любых рекурсивных типов данных.