O que é um catamorphism e pode ser implementado em C # 3.0?

Question

Eu estou tentando aprender sobre catamorphisms e eu li artigo de Wikipedia os primeiros posts casal em as séries do tópico para F # no blog Dentro F # .

Eu entendo que é uma generalização de dobras (ou seja, mapear uma estrutura de muitos valores para um valor, incluindo uma lista de valores para outra lista). E entendo que a lista de dobra e dobra-árvore é um exemplo canônico.

Isso pode ser mostrado para ser feito em C #, usando o operador Aggregate de LINQ ou algum outro método de ordem superior?

Answer 1

Aggregate() do LINQ é apenas para IEnumerables. Catamorphisms em geral referem-se ao padrão de dobragem para um tipo de dados arbitrária. Então Aggregate() é IEnumerables que FoldTree (abaixo) é Trees (abaixo); ambos são catamorphisms para seus respectivos tipos de dados.

Eu traduzi parte do código na parte 4 da série em C #. O código está abaixo. Note-se que o equivalente F # usado três a menos do que caracteres (para anotações tipo de parâmetros genéricos), considerando que esta C usa # código mais de 60. Esta é uma evidência por que ninguém escreve tal código em C # - há muitas anotações de tipo. Eu apresento o código no caso de ajuda de pessoas que conhecem C #, mas não F # jogo com isso. Mas o código é tão densa em C #, é muito difícil de fazer sentido.

Dada a seguinte definição para uma árvore binária:

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);
    }
}

Um pode dobrar e árvores, por exemplo, medir se duas árvores têm diferentes nós:

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);
    }
}

Neste segundo exemplo, uma outra árvore é reconstruído de forma diferente:

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);
    }
}

E neste terceiro exemplo, dobrando uma árvore é usada para desenhar:

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

Eu tenho feito mais leitura, incluindo um papel Micorosft Research on programação funcional com catamorphisms ( "bananas") , e parece que catamorphism apenas se refere a qualquer função que recebe uma lista e tipicamente divide-os em um único valor ( IEnumerable<A> => B), como Max(), Min(), e, no caso geral, Aggregate(), tudo seria um catamorphisms para listas.

Eu estava anteriormente sob a impressão de que refefred a uma maneira de criar uma função que pode generalizar dobras diferentes, de modo que pode dobrar uma árvore e uma lista. Não pode realmente ainda haver tal coisa, algum tipo de functor ou seta , mas talvez agora que está além do meu nível de compreensão.

Answer 3

A resposta de Brian no primeiro parágrafo é correta. Mas o seu exemplo de código realmente não refletir como seria de resolver problemas semelhantes em estilo C #. Considere um node classe simples:

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;
  }
}

Com esta podemos criar uma árvore na principal:

var Tree = 
    new Node(4,
      new Node(2, 
        new Node(1),
        new Node(3)
      ),
      new Node(6,
        new Node(5),
        new Node(7)
      )
    );

Nós definimos uma função vezes genéricos no namespace do 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)
    );
}

Para catamorphisms devemos especificar os estados de dados, nós pode ser nulo ou ter filhos. Os parâmetros genéricos determinar o que fazemos em qualquer caso. Observe a estratégia iteração (neste caso recursão) está escondido no interior da função de dobragem.

Agora, em vez de escrever:

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; 
}

Podemos escrever

public static int sum_tree_fold(Node tree) {
  return Node.fold(
    (x, l, r) => x + l + r,
    0,
    tree
  );
}

elegante, simples, tipo marcada, de fácil manutenção, etc. fácil de usar Console.WriteLine(Node.Sum_Tree(Tree));.

É fácil adicionar uma nova funcionalidade:

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 # vitórias na categoria concisão para In_Order_fold mas isso é de se esperar quando a linguagem fornece operadores dedicados para construção e utilização de listas.

A diferença dramática entre C # e F # parece ser devido a F # 's uso de encerramentos, para atuar como estruturas de dados implícitos, para desencadear a otimização de chamada de cauda. O exemplo na resposta de Brian também leva em conta as otimizações em F #, por esquivando-se reconstruir a árvore. Eu não tenho certeza C # suporta a otimização de chamada de cauda, ??e talvez In_Order_fold poderia ser escrito melhor, mas nenhum desses pontos são relevantes quando se discute como expressiva C # é quando se lida com essas Catamorphisms.

Ao traduzir código entre línguas, você precisa entender a idéia central da técnica, e, em seguida, implementar a idéia em termos de primitivas da linguagem.

Talvez agora você vai ser capaz de convencer seus C # colegas de trabalho para tirar dobras mais a sério.

Answer 4

Eu entendo que é um generalização de dobras (isto é, o mapeamento uma estrutura de diversos valores para uma valor, incluindo uma lista de valores para outra lista).

Eu não diria que um value.It mapeia-lo em outra estrutura.

Talvez um exemplo seria clarify.let dizer que soma mais de uma lista.

foldr (\ x -> \ y -> x + y) 0 [1,2,3,4,5]

Agora, isso reduziria a 15. Mas, na verdade, pode ser visto por mapeamento para uma estrutura puramente sintática 1 + 2 + 3 + 4 + 5 + 0. É justo que a linguagem de programação (no caso acima, Haskell) sabe como reduzir a acima estrutura sintática a 15.

Basicamente, um catamorphism substitui um construtor de dados com outro caso one.In da lista acima,

[1,2,3,4,5] = 1: 2: 3: 4: 5: [] (: é o operador contras, [] é o elemento nil) o catamorphism acima substituído:. com + e [] com 0

Ele pode ser generalizada para qualquer tipo de dados recursiva.

Answer 5

Brian tinha grande série de posts em seu blog. Também Channel9 tinha um bom vídeo . Não há açúcar sintático LINQ para .Aggregate (), de modo que isso importa se tem a definição de método LINQ agregado ou não? A idéia é, naturalmente, o mesmo. Folding sobre árvores ... Primeiro precisamos de um Nó ... talvez Tuple poderia ser usado, mas isso é mais claro:

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; }
}

Então, em C # nós pode fazer um tipo recursivo, mesmo isso é incomum:

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) { }
}

Agora, vou citar algumas das código de Brian, com modificações de estilo LINQ ligeiras:

1. Em C # Fold é chamada Aggregate
2. métodos LINQ são métodos de extensão que têm o item como primeiro parâmetro com "isto" -palavra-chave.
3. loop pode ser privado

...

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);
    }
}

Agora, o uso é bastante C # de estilo:

[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();
}

Eu ainda gosto F # mais.