Was ist ein Anamorphismus und wie sieht man in C# aus?

Question

Ich versuche, meinen Kopf um das Konzept des Anamorphismus zu wickeln.

In der funktionalen Programmierung ist ein Anamorphismus eine Verallgemeinerung des Begriffs der entfaltet auf Listen. Formal sind Anamorphismen generische Funktionen, die ein Ergebnis eines bestimmten Typs kursiv konstruieren können und die durch Funktionen parametrisiert werden, die den nächsten einzelnen Schritt der Konstruktion bestimmen.

---

Sein Dual, catamorphism, ist schön in diesem Beitrag beschrieben: What is a catamorphism and can it be implemented in C# 3.0?.

Ein schönes Beispiel für katamorphes Verhalten in C# ist die Methode von LINQ.

---

Was wäre ein anamorphotisches Äquivalent? Ist es richtig, an einen Pseudozufallszahlengenerator Random als anamorphotisches Konstrukt zu denken oder sollte der Entfaltungsprozess immer eine Akkumulatorfunktion wie die folgende beinhalten (Codeausschnitt aus Intro to Rx)?

IEnumerable<T> Unfold<T>(T seed, Func<T, T> accumulator) 
{ 
    var nextValue = seed; 
    while (true) 
    { 
     yield return nextValue; 
     nextValue = accumulator(nextValue); 
    } 
} 

Answer 1

Aggregate Methode des LINQ hat die Signatur

T Aggregate<T>(IEnumerable<T> source, Func<T, T, T> accumulator) 

So entspricht das Entfalten

IEnumerable<T> Unfold<T>(T seed, Func<T, Nullable<T>> accumulator) 
{ 
    Nullable<T> nextValue = new Nullable<T>(seed); 
    while (nextValue.HasValue) 
    { 
     yield return nextValue.Value; 
     nextValue = accumulator(nextValue); 
    } 
} 

In rein funktionaler Programmierung würde, Falten und Entfalten muss eine deterministische Funktion umfassen. Für C# System.Random gilt dies, wenn Sie seine deterministic internals als eine implizite Funktion betrachten, wie Sie vorschlagen. Man könnte diesen präzisen PRNG unter Verwendung von Unfold neu erstellen, so dass er nicht falten kann, sondern funktionell und semantisch äquivalent zu einer Falte ist.

Die beiden Falten und Entfalten der obigen Listen sind Spezialfälle der allgemeineren Faltung von Listen:

B Fold<A, B>(Func<A, B, B> acc, B seed, IEnumerable<A> source); 
IEnumerable<B> Unfold<A, B>(Func<A, Nullable<Tuple<A, B>>> acc, A seed); 

In LINQ ist diese Allgemeinheit in anderen Kombinatoren wie Select.

Wie Brian's answer zu der Frage Was ist ein Katamorphismus und kann es in C# 3.0 implementiert werden?:

Catamorphisms im allgemeinen bezieht sich auf das Muster für einen beliebigen Datentyp des Faltens.

Ebenso kann man anamorphisms auf binäre Bäume in C# konstruieren:

public class Tree<T> { 
    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> right) 
    { 
     this.Data = data; 
     this.Left = left; 
     this.Right = right; 
    } 
} 

public struct Triple<T> { 
    public T Result; 
    public Nullable<T> LeftSeed; 
    public Nullable<T> RightSeed; 
} 

public static Tree<T> Unfold<T>(Func<T, Triple<T>> water, T seed) 
{ 
    Triple<T> tmp = water(seed); 
    Tree<T> leftTree = null; 
    Tree<T> rightTree = null; 

    if (tmp.LeftSeed.HasValue) 
     leftTree = Unfold<T>(water, tmp.LeftSeed.Value); 

    if (tmp.RightSeed.HasValue) 
     rightTree = Unfold<T>(water, tmp.RightSeed.Value); 

    return new Tree(tmp.Result, leftTree, rightTree); 
} 

hier ein ziemlich dumm Beispiel dafür, wie die Collatz numbers in this XKCD strip zu bauen:

public static Tree<int> CollatzTree(int max) 
{ 
    return Unfold<int>(i => { 
     if (i >= max) return new Triple(i, null, null); 
     int? tpo = (i - 1) % 3 == 0 ? (i - 1)/3 : null; 
     return new Triple(i, tpo, 2*i); 
    }, max); 
} 

Hier ist ein heteronormatives Beispiel für den Aufbau eines Stammbaums:

public static Tree<Person> FamilyTree(Person youngestPerson) { 
    return Unfold<Person>(child => { 
     Person mother = GetMotherFromDatabase(child); 
     Person father = GetFatherFromDatabase(child); 
     return new Triple(p, mother, father); 
    }, youngestPerson); 
} 

Ich habe den obigen Code nicht ausgeführt, daher können Fehler auftreten.