CATAMORPHISM이란 무엇이며 C# 3.0에서 구현할 수 있습니까?
https://stackoverflow.com/questions/196294
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 catamorphism에 대해 배우려고 노력하고 있으며 읽은 것입니다 위키 백과 기사 그리고 첫 커플 게시물 f#에 대한 주제의 일련 에 내부 F# 블로그.
나는 그것이 폴드의 일반화라는 것을 이해합니다 (즉, 많은 값의 구조를 다른 값 목록을 다른 목록에 포함하여 하나의 값에 매핑). 그리고 나는 폴드리스트와 폴드 트리가 정식의 예라고 모았습니다.
LINQ를 사용하여 C#에서 수행되는 것으로 표시 될 수 있습니다. Aggregate 연산자 또는 다른 고차 방법?
해결책
LINQ Aggregate() 그냥 용입니다 IEnumerables. Catamorphism은 일반적으로 임의의 데이터 유형에 대한 접이식 패턴을 나타냅니다. 그래서 Aggregate() 그렇습니다 IEnumerables 무엇 FoldTree (아래)입니다 Trees (아래에); 둘 다 각각의 데이터 유형에 대한 catamorphism입니다.
코드 중 일부를 번역했습니다 시리즈의 4 부 C#에. 코드는 다음과 같습니다. 동등한 F#은 일반 유형 매개 변수 주석의 경우 3 개의 문자보다 3 개의 문자를 사용했지만이 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))));
}
}
다른 팁
나는 Micorosft 연구 논문을 포함하여 더 많은 독서를하고 있습니다. Catamorphisms를 사용한 기능 프로그래밍 ( "Bananas"), 그리고 그것은 것 같습니다 촉매 목록을 취하고 일반적으로 단일 값으로 나누는 함수를 나타냅니다.IEnumerable<A> => B), 처럼 Max(), Min(), 일반적인 경우, Aggregate(), 모두 목록에 대한 촉매제 일 것입니다.
나는 이전에 다른 주름을 일반화 할 수있는 함수를 만드는 방법으로 재조정하여 나무를 접을 수 있다는 인상을 받았습니다. 그리고 목록. 실제로는 여전히 그런 것이있을 수 있습니다. untctor 또는 화살 어쩌면 지금은 내 이해 수준을 넘어서는 것입니다.
첫 번째 단락에서 브라이언의 대답은 정확합니다. 그러나 그의 코드 예제는 실제로 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)
);
}
Catamorphism의 경우 데이터 상태를 지정해야합니다. 노드는 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# 동료가 더 심각하게 접을 수 있도록 설득 할 수있을 것입니다.
나는 그것이 폴드의 일반화라는 것을 이해합니다 (즉, 많은 값의 구조를 다른 값 목록을 다른 목록에 포함하여 하나의 값에 매핑).
나는 하나의 값을 말하지 않을 것입니다. 그것은 다른 구조에 그것을 맵핑합니다.
아마도 예를 들어 명확하게 할 것입니다. 목록에 대한 요약은 말할 것입니다.
foldr ( x-> y-> x + y) 0 [1,2,3,4,5
이제 이것은 15로 감소 할 것입니다. 그러나 실제로, 그것은 순수한 구문 구조 1 + 2 + 3 + 4 + 5 + 0에 매핑하는 것을 볼 수 있습니다. 단지 프로그래밍 언어 (위의 경우 Haskell)가 방법을 알고 있습니다. 위의 구문 구조를 15로 줄입니다.
기본적으로 Catamorphism은 하나의 데이터 생성자를 다른 데이터 생성자로 대체합니다.
1,2,3,4,5] = 1 : 2 : 3 : 4 : 5 : [] (:] (: cond operator, []는 nil 요소입니다) 위의 catamorphism : +와 []가 0으로 대체됩니다. .
재귀적인 데이터 유형으로 일반화 될 수 있습니다.
브라이언은 블로그에 훌륭한 일련의 게시물을 가지고있었습니다. 또한 Channel9에는 a 좋은 비디오. .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) { }
}
이제 약간의 LINQ 스타일 수정으로 Brian의 코드 중 일부를 인용하겠습니다.
- C# 폴드에서는 집계라고합니다
- LINQ 메소드는 항목을 "this"-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#을 더 좋아한다.
