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

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

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

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

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

Что было бы анаморфным эквивалентом? Правильно ли думать о генераторе псевдослучайных чисел Random как анаморфная конструкция, или если процесс разворачивания всегда включает функцию накопителя, подобную приведенной ниже (фрагмент кода взят из Введение в Rx)?

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

c# functional-programming recursion-schemes catamorphism anamorphism
person Jaanus Varus    schedule 15.06.2015    source источник
comment
В Wikipediaentry говорится, что Zip является примером. Это берет две последовательности и соединяет их вместе. LINQ имеет функцию под названием Zip. Приведенный вами пример также подходит под определение. Однако нет предиката завершения, который указывается как необязательный.   -  person CSharpie    schedule 15.06.2015
comment
Согласно enumeratethis.com/category/c, Observable.Generate является примером анаморфизма. Хотя, как и Aggregate, это не настоящие реализации, поскольку они не являются действительно универсальными и специфичны для определенных типов данных.   -  person David Arno    schedule 15.06.2015

Ответы (1)


arrow_upward
8
arrow_downward

Метод LINQ Aggregate имеет подпись

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 это верно, если учесть его детерминированные внутренние компоненты в качестве неявной функции, как вы предлагаете. Можно воссоздать этот точный ГПСЧ с помощью 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);
}

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

person Simon Shine    schedule 16.06.2015
comment
Мне нужно чаще использовать деревья. - person CSharpie; 16.06.2015