Was ist ein catamorphism und kann es C # 3.0 implementiert werden in?
https://stackoverflow.com/questions/196294
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, über catamorphisms zu lernen, und ich habe gelesen Wikipedia-Artikel die ersten paar Beiträge in der Reihe des Themas für F # auf dem Innen F # Blog.
Ich verstehe, dass es sich um eine Verallgemeinerung von Falten ist (das heißt Abbilden eine Struktur vieler Werte auf einen Wert, einschließlich einer Liste der Werte in einer anderen Liste). Und ich höre, dass die Klappliste und faltet Baum ein kanonisches Beispiel ist.
Kann dies gezeigt wird in C # zu tun, Aggregate Operator oder eine andere übergeordnete Methode der Verwendung von LINQ?
Lösung
LINQ Aggregate() ist nur für IEnumerables. Catamorphisms im allgemeinen bezieht sich auf das Muster für einen beliebigen Datentyp des Faltens. So Aggregate() ist zu IEnumerables was FoldTree (unten) ist (siehe unten) Trees; beide sind catamorphisms für ihre jeweiligen Datentypen.
Ich übersetzte einige der Code in Teil 4 der Serie rel="nofollow in C #. Der Code ist unten. Beachten Sie, dass das Äquivalent # F verwendet, um drei weniger als Zeichen (für generische Typparameter Anmerkungen), während das C # -Code mehr als 60 Beweise Dies ist verwendet, warum niemand einen solchen Code in C # schreibt - es gibt zu viele Typenannotationen. Ich stelle den Code für den Fall, es hilft den Menschen, die C # wissen aber nicht F # Spiel mit diesem. Aber der Code ist so dicht in C #, ist es sehr schwierig ist, einen Sinn zu geben.
die folgende Definition für einen binären Baum Gegeben:
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);
}
}
Man kann Bäume falten und z.B. messen, wenn zwei Bäume haben verschiedene Knoten:
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);
}
}
In diesem zweiten Beispiel wird ein weiterer Baum rekonstruiert anders:
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);
}
}
Und in diesem dritten Beispiel einen Baum Faltung wird für die Zeichnung:
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))));
}
}
Andere Tipps
Ich habe mehr Lesung getan, darunter ein Micorosft Forschungspapier auf funktionale Programmierung mit catamorphisms ( „Bananen“) , und es scheint, dass catamorphism bezieht sich nur auf jede Funktion, die eine Liste nimmt und bricht es in der Regel auf einen einzigen Wert nach unten ( IEnumerable<A> => B), wie Max(), Min(), und im allgemeinen Fall, Aggregate(), würden alle ein catamorphisms für Listen sein.
Ich war vorher unter dem Eindruck, dass sie auf eine Art und Weise refefred eine Funktion zu schaffen, die verschiedenen Falten verallgemeinern kann, so dass es einen Baum faltet und eine Liste. so etwas tatsächlich noch Es kann eine Art von Funktors oder Pfeil vielleicht aber gerade das ist jenseits meiner Ebene des Verstehens.
Brians Antwort im ersten Absatz ist richtig. Aber sein Codebeispiel nicht wirklich überlegen, wie man ähnliche Probleme in einem C # Stil lösen würde. Betrachten wir eine einfache Klasse 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;
}
}
Mit diesem können wir einen Baum in Haupt erstellen:
var Tree =
new Node(4,
new Node(2,
new Node(1),
new Node(3)
),
new Node(6,
new Node(5),
new Node(7)
)
);
Wir definieren eine generische Falzfunktion in Node Namespace:
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)
);
}
Für catamorphisms wir die Zustände der Daten angeben sollten, können Knoten null sein, oder Kinder haben. Die allgemeinen Parameter bestimmen, was wir in jedem Fall tun. Beachten Sie die Iterationsstrategie (in diesem Fall Rekursion) innerhalb der Falzfunktion versteckt.
Jetzt statt zu schreiben:
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;
}
Wir können schreiben
public static int sum_tree_fold(Node tree) {
return Node.fold(
(x, l, r) => x + l + r,
0,
tree
);
}
Elegant, einfach, Typ-geprüft, wartbar, etc. Einfach Console.WriteLine(Node.Sum_Tree(Tree)); zu verwenden.
Es ist einfach, neue Funktionen hinzuzufügen:
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 # gewinnt in der Prägnanz Kategorie für In_Order_fold aber das ist zu erwarten, wenn die Sprache für die Herstellung und Verwendung von Listen engagierte Betreiber zur Verfügung stellt.
Der dramatische Unterschied zwischen C # und F # scheint auf F # 's Verwendung von Verschlüssen zu sein, als implizite Datenstrukturen zu wirken, um den Schwanz Call-Optimierung für die Auslösung. Das Beispiel in Brians Antwort nimmt auch Konto Optimierungen in F # in, zum Ausweichen auf den Baum zu rekonstruieren. Ich bin nicht sicher, C #, um den Schwanz Call-Optimierung unterstützt, und vielleicht könnte In_Order_fold besser geschrieben werden, aber keiner dieser Punkte ist relevant, wenn die Diskussion, wie expressiv C # ist, wenn sie mit diesem Catamorphisms handelt.
Wenn Code zwischen den Sprachen zu übersetzen, müssen Sie die Kernidee der Technik verstehen, und dann die Idee, in Bezug auf die Sprache des Primitiven zu implementieren.
Vielleicht ist jetzt können Sie Ihre C # Mitarbeiter davon zu überzeugen, Falten mehr ernst zu nehmen.
Ich verstehe, dass es eine Verallgemeinerung von Falten (d.h., mapping eine Struktur vieler Werte in einem Wert, einschließlich einer Liste von Werten eine andere Liste).
Ich würde nicht sagen, ein value.It ordnet sie in einer anderen Struktur.
Vielleicht wäre ein Beispiel clarify.let sagen die Summe über eine Liste.
foldr (\ x -> \ y -> x + y) 0 [1,2,3,4,5]
Nun würde dies auf 15 reduzieren. Aber tatsächlich kann es Zuordnung zu einer rein syntaktischen Struktur 1 + 2 + 3 + 4 + 5 + 0 angesehen werden. Es ist nur, dass die Programmiersprache (im obigen Fall, Haskell) weiß, wie die obige syntaktische Struktur auf 15 zu reduzieren.
Im Grunde ein catamorphism ersetzt einen Datum Konstruktor mit einem anderen one.In Fall von oben aufgeführte Liste,
[1,2,3,4,5] = 1: 2: 3: 4: 5: [] (: wird der Operator cons, [] ist das Null-Element) die catamorphism oben ersetzt. mit + und [] mit 0
Es kann auf alle rekursiven Datentypen verallgemeinert werden.
Brian hatte große Reihe von Beiträgen in seinem Blog. Auch hatte Channel9 eine schönes Video . Es gibt keinen LINQ syntaktischen Zucker für .Aggregate (), so macht es aus, wenn es die Definition von LINQ Aggregaten Methode hat oder nicht? Die Idee ist natürlich das gleiche. Umklappen Bäume ... Zuerst müssen wir einen Knoten ... vielleicht Tuple verwendet werden könnte, aber das ist mehr klar:
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; }
}
Dann in C # we können eine rekursive Art machen, auch das ist ungewöhnlich:
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) { }
}
Nun, ich werde einige von Brians Code zitieren, mit leichten LINQ-style Änderungen:
- In C # Falten heißt Aggregate
- LINQ Methoden sind Erweiterungsmethoden, die das Element als ersten Parameter mit „dieser“ -keyword haben.
- Schleife kann privat sein
...
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);
}
}
Nun ist die Verwendung recht C # -Stil:
[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();
}
ich immer noch wie F # mehr.
