Что такое катаморфизм и может ли он быть реализован в C # 3.0?
https://stackoverflow.com/questions/196294
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь узнать о катаморфизмах и я прочитал статья в Википедии и первые пару постов в серия тем для F# на Внутри F# Блог.
Я понимаю, что это обобщение складок (т. е. сопоставление структуры из многих значений одному значению, включая список значений другому списку).И я так понимаю, что fold-list и fold-tree являются каноническими примерами.
Можно ли показать, что это сделано на C #, используя LINQ Aggregate оператор или какой-то другой метод более высокого порядка?
Решение
LINQ's Aggregate() только для IEnumerables. Катаморфизмы в целом относятся к схеме свертывания для произвольного типа данных. Так что FoldTree означает Trees (ниже) <<> (ниже); оба являются катаморфизмами для их соответствующих типов данных.
Я перевел часть кода из части 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 # поддерживает оптимизацию хвостового вызова, и, возможно, <=> можно было бы написать лучше, но ни один из этих пунктов не имеет отношения к обсуждению того, насколько выразительным является C # при работе с этими катаморфизмами.
При переводе кода между языками вам необходимо понять основную идею метода, а затем реализовать его в терминах языковых примитивов.
Возможно, теперь вы сможете убедить своих коллег по C # более серьезно относиться к складкам.
Я понимаю, что это обобщение сгибов (то есть отображение структура многих значений в одном значение, включая список значений для другой список).
Я бы не сказал одно значение. Он отображает его в другую структуру.
Может быть, пример прояснит, скажем, суммирование по списку.
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.
Его можно обобщить для любых рекурсивных типов данных.
У Брайана была отличная серия постов в его блоге.Кроме того, у Channel9 был хорошее видео.Для LINQ нет синтаксического сахара .Aggregate() так имеет ли значение, имеет ли он определение метода 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 называется агрегатом
- Методы LINQ - это методы расширения, которые имеют item в качестве первого параметра с ключевым словом "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 #.
