ما هو التحول وهل يمكن تنفيذه في C# 3.0؟

Question

أحاول أن أتعلم عن التحولات وقد قرأت مقالة ويكيبيديا والمشاركات الزوجية الأولى في سلسلة موضوع F# على ال داخل F # مدونة.

أفهم أنه تعميم للطيات (أي تعيين بنية العديد من القيم إلى قيمة واحدة، بما في ذلك قائمة القيم إلى قائمة أخرى).وأنا أجمع أن قائمة الطي وشجرة الطي هي مثال أساسي.

هل يمكن إظهار ذلك في لغة C#، باستخدام LINQ Aggregate المشغل أو بعض الطرق الأخرى ذات الترتيب الأعلى؟

Answer 1

لينك Aggregate() هو فقط من أجل 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))));
    }
}    

Answer 2

لقد قمت بالمزيد من القراءة، بما في ذلك ورقة بحثية عن Micorosft البرمجة الوظيفية مع التحولات ("الموز"), ، ويبدو ذلك التحول يشير فقط إلى أي وظيفة تأخذ قائمة وتقسمها عادةً إلى قيمة واحدة (IEnumerable<A> => B)، يحب Max(), Min(), ، وفي الحالة العامة، Aggregate(), ، سيكون كل ذلك بمثابة انقلاب للقوائم.

كان لدي انطباع سابقًا بأنها أشارت إلى طريقة لإنشاء دالة يمكنها تعميم طيات مختلفة، بحيث يمكنها طي شجرة و قائمة.ربما لا يزال هناك في الواقع شيء من هذا القبيل، نوع ما عامل أو سهم ربما ولكن الآن هذا يتجاوز مستوى فهمي.

Answer 3

والجواب براين في الفقرة الأولى هي الصحيحة. لكن المثال رمز له لا تعكس حقا كيف يمكن لأحد أن يحل مشاكل مماثلة في 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)
    );
}

لcatamorphisms يجب علينا تحديد ولايات البيانات، العقد يمكن أن تكون فارغة، أو لديك أطفال. المعلمات العامة تحدد ما نقوم به في كلتا الحالتين. لاحظ استراتيجية التكرار (في هذه الحالة العودية) كانت مخبأة داخل وظيفة أضعاف.

والآن بدلا من الكتابة:

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 # زملاء العمل لاتخاذ طيات أكثر جدية.

Answer 4

<اقتباس فقرة>   

وأنا أفهم أنه من   تعميم طيات (أي رسم الخرائط   هيكل من العديد من القيم واحد   القيمة، بما في ذلك قائمة من القيم ل   قائمة أخرى).

ولن أقول واحد value.It خرائط هو داخل بنية أخرى.

وربما على سبيل المثال أن clarify.let نقول جمع أكثر من قائمة.

وfoldr (\ س -> \ ذ -> س + ص) 0 [1،2،3،4،5]

والآن هذا من شأنه أن يقلل إلى 15. لكن في الواقع، يمكن أن ينظر التعيين إلى بنية النحوية بحتة 1 + 2 + 3 + 4 + 5 + 0. هو مجرد أن لغة البرمجة (في الحالة المذكورة أعلاه، هاسكل) يعرف ذلك كيفية الحد من هيكل النحوي أعلاه إلى 15.

والأساس، وcatamorphism محل منشئ بيانات واحد مع آخر one.In حالة من القائمة أعلاه،

[1،2،3،4،5] = 1: 2: 3: 4: 5: [] (: هو مشغل سلبيات، [] هو العنصر صفر) وcatamorphism فوق استبدال: مع + و[] 0

ويمكن تعميمها على أي أنواع البيانات متكررة.

Answer 5

كان لدى براين سلسلة رائعة من المشاركات في مدونته.كما كان لدى 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) { }
}

الآن، سأقتبس بعضًا من أكواد Brian، مع تعديلات طفيفة على نمط LINQ:

1. في C# Fold يسمى التجميع
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 # أكثر.