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

Aggregate() LINQ предназначен только для IEnumerables. Катаморфизмы в целом относятся к шаблону сворачивания для произвольного типа данных. Итак, 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 Research по функциональному программированию с катаморфизмами ( "бананы"), и кажется, что катаморфизм просто относится к любой функции, которая принимает список и обычно разбивает его на одно значение (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 # относиться к складкам более серьезно.

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

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

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

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, [] - элемент nil) приведенный выше катаморфизм заменен: на + и [] на 0 .

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

У Брайана была отличная серия сообщений в своем блоге. Также на 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:

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

...

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 #.