什麼是變形，可以在C＃3.0中實現？

28

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

來源

2008-10-13 01:06:37 Brian

9

我一直在做更多的閱讀，包括functional programming with catamorphisms ("bananas")一個Micorosft研究論文，它似乎是catamorphism僅僅指需要一個列表中的任何功能，通常將其分解爲單一值（IEnumerable<A> => B），如Max（）,Min（），在一般情況下，Aggregate（），都將是列表的變形。

我以前的印象是，它提到創建一種可以概括不同摺疊的功能的方法，以便它可以摺疊樹形結構樹和列表。實際上可能還有這樣的事情，某種函子或箭頭也許，但現在這超出了我的理解水平。

來源

2008-10-12 23:47:41

+1

爲什麼你問一個問題，然後立即自己回答？顯然你已經知道答案。 – 2008-10-12 23:52:38

3

我知道這是一個褶皺的概括（即，映射一個值爲多個值的結構，其中一個值爲，其中一個值列表爲另一個列表）。

我不會說一個值，它將它映射到另一個結構。

也許一個例子可以澄清.let的說法總結一個列表。

foldr相似（\ X - > \ý - > X + Y）0 [1,2,3,4,5]

現在這將減少到15 但實際上，它可以被看作映射到一個純粹的句法結構1 + 2 + 3 + 4 + 5 + 0. 只是編程語言（在上面的例子中，haskell）知道如何將上面的語法結構減少到15.

基本上，一個catamorphism替換上述列表的另一one.In情況下，一個數據構造，

[1,2,3,4,5] = 1：2：3：4：5：[]（：是缺點操作者，[]是零e lement）上面的變形取代：+和[]與0.

它可以推廣到任何遞歸數據類型。

來源

2010-01-28 12:08:49 Thiagarajan

2

布賴恩偉大的系列賽在他的博客文章。此外Channel9上有一個nice video。沒有爲.Aggregate沒有LINQ語法糖（），所以它的問題，如果有LINQ聚合方法的定義或沒有？這個想法當然是一樣的。摺疊樹......首先，我們需要一個節點...也許可以使用元組，但這是更爲清晰：

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

現在，我將引用一些Brian的代碼，有輕微的LINQ風格的修改：

在C＃中折叫做聚合
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＃以上。

來源

2012-07-20 17:03:23

4

Brian在第一段中的回答是正確的。但他的代碼示例並不能真正反映一個如何解決在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) 
    ); 
}

對於變形我們應該指定數據的狀態，節點可以爲null，或者有子節點。通用參數決定了我們在兩種情況下所做的工作。注意迭代策略（在這種情況下，遞歸）隱藏在摺疊函數中。

現在不是寫：

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＃使用閉包，作爲隱式數據結構來觸發尾部調用優化。 Brian的答案中的例子還考慮了F＃中的優化，以避免重構樹。我不確定C＃是否支持尾部調用優化，也許In_Order_fold可能會寫得更好，但在討論處理這些變形時C＃的表達方式時，這兩點都不相關。

在翻譯語言之間的代碼時，需要理解該技術的核心思想，然後使用該語言的原語實現該思想。

也許現在您可以說服您的C＃同事更認真地對待摺疊。

來源

2014-01-13 23:03:53 Polymer

什麼是變形，可以在C＃3.0中實現？

回答

相關問題