カタモフィズムとは何ですか？C＃3.0で実装できますか？
https://stackoverflow.com/questions/196294
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
カタモフィズムについて学ぼうとしていますが、ウィキペディアの記事を読みました。 F＃の一連のトピックの最初のカップルの投稿 Inside F＃ブログで。
それは折り畳みの一般化（つまり、値のリストを別のリストに含む、多くの値の構造を1つの値にマッピングすること）であることを理解しています。そして、fold-listとfold-treeは標準的な例であるということをまとめています。
これは、LINQのAggregate演算子または他の高次メソッドを使用して、C＃で実行されるように表示できますか？
解決
LINQのAggregate()はIEnumerables専用です。カタモフィズムは一般に、任意のデータ型の折りたたみのパターンを指します。したがって、FoldTreeはTreesに、<=>（下）は<=>（下）になります。どちらも、それぞれのデータ型のカタモフィズムです。
シリーズのパート4のコードの一部を翻訳しましたをC＃に追加します。コードは次のとおりです。同等のF＃では3つの小なり記号（ジェネリック型パラメーターアノテーション用）を使用しましたが、このC＃コードでは60を超えるコードを使用していることに注意してください。 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);
}
}
木を折りたたむことができます。 2つのツリーに異なるノードがあるかどうかを測定します。
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);
}
}
この2番目の例では、別のツリーが異なる方法で再構築されます。
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);
}
}
この3番目の例では、ツリーの折りたたみが描画に使用されます：
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の論文を含め、もっと読み続けています。カタモフィズム（<！> quot; bananas <！> quot;）で、 catamorphism は、リストを取り、通常はIEnumerable<A> => B、Max()などの単一の値（Min()）に分解します。一般的な場合、Aggregate()はすべてリストのカタモフィズムになります。
以前は、さまざまな折り畳みを一般化できる関数を作成して、ツリーを 折り畳むことができるようにする方法を拒否したという印象を受けました。実際にはまだそのようなことがあるかもしれません。何らかの種類の functor または arrow かもしれませんが、現時点では私の理解レベルを超えています。
最初の段落のブライアンの答えは正しいです。しかし、彼のコード例は、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;
}
}
これでmainにツリーを作成できます：
var Tree =
new Node(4,
new Node(2,
new Node(1),
new Node(3)
),
new Node(6,
new Node(5),
new Node(7)
)
);
Nodeの名前空間で一般的なfold関数を定義します：
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にするか、子を持つことができます。汎用パラメーターは、どちらの場合でも何をするかを決定します。繰り返し戦略（この場合は再帰）がfold関数内に隠されていることに注意してください。
今では書く代わりに：
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＃がテールコールの最適化をサポートしているかどうかはわかりませんが、おそらく<=>の方が適切に記述できますが、これらのカタモフィズムに対処する場合のC＃の表現力について説明するときは、これらの点のどちらも関係ありません。
コードを言語間で翻訳する場合、この手法の核となる概念を理解してから、言語のプリミティブの観点からその概念を実装する必要があります。
おそらく、C＃の同僚を説得して、折り目をもっと真剣に取ることができるでしょう。
それは 折り畳みの一般化（つまり、マッピング 多くの値から1つの構造 値、値のリストを含む 別のリスト）。
1つの値とは言いません。別の構造にマップします。
たぶん、例が明確になるでしょう。リストの要約を言ってみましょう。
foldr（\ x-<！> gt; \ y-<！> gt; 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には nice video 。 .Aggregate（）にはLINQ構文糖衣はないので、LINQ Aggregateメソッドの定義があるかどうかは重要ですか？アイデアはもちろん同じです。 木の上で折り畳む...最初にノードが必要です...多分タプルを使用できますが、これはより明確です：
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スタイルを少し変更します。
- C＃では、FoldはAggregateと呼ばれます
- LINQメソッドは、<！> quot; this <！> quot; -keywordを持つ最初のパラメーターとしてアイテムを持つ拡張メソッドです。
- ループはプライベートにすることができます
...
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＃が好きです。
