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

Question

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

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

---

Его двойственный, катаморфизм, хорошо описан в этом посте: что такое катаморфизм и можно ли его реализовать в C# 3.0?,

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

---

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

Как ответ Брайана на вопрос, что такое катаморфизм и можно ли его реализовать в C# 3.0?:

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

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

Вот довольно глупый пример того, как построить числа Коллатца в этой полосе XKCD:

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

Я не запускал ни один из приведенных выше кодов, поэтому могут быть ошибки.