Cos'è un anamorfismo e come appare in C#?

Question

Sto cercando di riprendere il concetto di anamorfismo.

Nella programmazione funzionale, un anamorfismo è una generalizzazione del concetto di dispiegarsi negli elenchi. Formalmente, gli anamorfismi sono funzioni generiche che possono costruire in modo corecante un risultato di un certo tipo e che sono parametrizzati da funzioni che determinano il successivo singolo passo della costruzione.

---

sua doppia, catamorphism, è ben descritto in questo post: What is a catamorphism and can it be implemented in C# 3.0?.

Un bell'esempio di comportamento catamorfico in C# è il metodo Aggregate di LINQ.

---

Cosa sarebbe un equivalente anamorfico? È corretto pensare ad un generatore di numeri pseudo-casuali Random come un costrutto anamorfico o se il processo di spiegamento includa sempre una funzione di accumulatore come quella seguente (frammento di codice preso da 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

metodo aggregato di LINQ ha la firma

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

Così il corrispondente dispiegarsi sarebbe

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); 
    } 
} 

Nella programmazione funzionale pura, piegatura e spiegamento deve includere una funzione deterministica. Per C# System.Random, questo è vero se si considera il suo deterministic internals come una funzione implicita, come suggerito. Si potrebbe ricreare questo PRNG preciso usando Unfold, quindi non può usare pieghevole ma essere funzionalmente e semanticamente equivalente in una piega.

I due ripiegamento e dispiegamento delle liste sopra sono casi speciali di piegatura più generale di liste:

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, questa generalità è presente in altri combinatori come Select.

As Brian's answer alla domanda Che cos'è un catamorfismo e può essere implementato in C# 3.0?:

Catamorphisms in generale si riferisce al modello di pieghevole per un tipo di dati arbitrari .

Allo stesso modo, si può costruire anamorphisms su alberi binari in C#:

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); 
} 

Ecco un esempio piuttosto stupido di come costruire il Collatz numbers in this XKCD strip:

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); 
} 

Ecco un esempio eteronormativo di costruzione di un albero genealogico:

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); 
} 

Non ho eseguito nessuno dei codici sopra indicati, quindi potrebbero esserci degli errori.