Что такое катаморфизм и может ли он быть реализован в C# 3.0?

Question

Я пытаюсь узнать о катаморфизмах, и я прочитал the Wikipedia article и первые сообщения в the series of the topic for F# на Внутри F # блог.

Я понимаю, что это обобщение складок (т. Е. Отображение структуры многих значений в одно значение, включая список значений в другой список). И я понимаю, что складчатый список и складчатое дерево - канонический пример.

Можно ли это сделать, чтобы сделать это на C#, используя оператор LINQ Aggregate или какой-либо другой метод более высокого порядка?

Answer 1

LINQ's Aggregate() предназначен только для IEnumerables. Катаморфизм в общем случае относится к шаблону складывания для произвольного типа данных. Итак, Aggregate() относится к IEnumerables, что FoldTree (ниже) относится к деревьям (ниже); оба являются катаморфизмами для соответствующих типов данных.

Я перевел часть кода в part 4 of the series на 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)))); 
    } 
}  

Answer 2

Я делал больше чтения, в том числе бумаги Micorosft Research по functional programming with catamorphisms ("bananas"), и кажется, что катаморфизм просто относится к любой функции, которая принимает список и обычно разбивает его на одно значение (IEnumerable<A> => B) , как Max(), Min(), и в общем случае Aggregate(), все это будет катаморфизм для списков.

Раньше у меня создалось впечатление, что оно относится к способу создания функции, которая может обобщать различные складки, чтобы она могла складывать дерево и список. На самом деле все еще может быть такая вещь, какой-то функтор или стрелка может быть, но прямо сейчас, что выше моего уровня понимания.

Answer 3

Я понимаю, что это обобщение складок (то есть отображение - структура множества значений до одного значения , включая список значений до другой список).

Я бы не сказал ни одного значения. Он отображает его в другую структуру.

Может быть, пример может рассказать суммирование по списку.

foldr (\ х -> \ у -> х + у) 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 , [] - это nil e lement) вышеперечисленный катаморфизм: с + и [] с 0.

Он может быть обобщен на любые рекурсивные типы данных.

Answer 4

У Брайана была большая серия сообщений в его блоге. Также Channel9 имел nice video. Синтаксический сахар LINQ для .Aggregate() не имеет значения, имеет ли он определение метода LINQ Aggregate или нет? Идея, конечно же, та же. Складные над деревьями ... Сначала нужно узел ... возможно Кортеж можно было бы использовать, но это более ясно:

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:

1. в C# вислоухих называются Совокупным
2. Методы LINQ - это методы расширения, которые имеют элемент как первый параметр с «этим» ключом.
3. Loop может быть частным

...

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 # больше.

Answer 5

Ответ Брайана в первом абзаце верен. Но его пример кода на самом деле не отражает, как можно было бы решить аналогичные проблемы в стиле 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 «s:

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# при работе с этими Catamorphisms.

При переводе кода между языками вам необходимо понять основную идею техники, а затем реализовать идею с точки зрения примитивов языка.

Возможно, теперь вы сможете убедить своих сотрудников C# более серьезно относиться к складкам.