Что такое анаморфизм, и как выглядит на C#?

Question

Я пытаюсь обернуть голову вокруг концепции анаморфизма.

В функциональном программировании анаморфизм является обобщением концепции разворачивания в списках. Формально анаморфизмы представляют собой общие функции, которые могут привести к конструированию результата определенного типа и который параметризуется функциями, которые определяют следующий один шаг конструкции.

---

Его двойной, катаморфизм, красиво описано в этом посте: What is a catamorphism and can it be implemented in C# 3.0?.

Хорошим примером катаморфического поведения в C# является метод LINQ Aggregate.

---

Что такое анаморфотный эквивалент? Правильно ли считать генератор псевдослучайных чисел Random как анаморфную конструкцию или должен ли процесс разворота всегда включать в себя функцию аккумулятора, подобную приведенной ниже (фрагмент кода, взятый из 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

Совокупный метод Linq имеет подпись,

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

Таким образом, соответствующее раскрытие будет

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

В чистом функциональном программировании, складывании и раскладывании должны включать детерминированный функцию. Для C# System.Random это верно, если вы считаете его deterministic internals неявной функцией, как вы предлагаете. Можно было бы воссоздать этот точный PRNG, используя Unfold, поэтому он может не использовать складной, но быть функционально и семантически эквивалентным в складку.

Два складывания и раскладывания списков выше, являются частными случаями более общего складывания списков:

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

В LINQ, эта общность присутствует в других комбинаторов, таких как Select.

Как Brian's answer на вопрос Что такое катаморфизм и может ли он быть реализован в C# 3.0?:

катаморфизма в целом относится к схеме складывания для произвольного типа данных .

Аналогично, можно построить anamorphisms на бинарных деревьев в 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); 
} 

Вот довольно простой пример того, как строить Collatz numbers в 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); 
} 

Вот гетеронормативный пример построения генеалогического древа:

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

У меня не было никакого кода выше, поэтому могут быть ошибки.