什么是变形,在C#中看起来如何？

Question

我试图围绕变形的概念.

在函数式编程中,anamorphism是对列表展开概念的概括.形式上,anamorphisms是泛型函数,它们可以共同构造某种类型的结果,并通过确定构造的下一个单一步骤的函数进行参数化.

---

它的双重,同态,在这篇文章中有很好的描述:什么是catamorphism并且可以在C#3.0中实现？.

一个很好的C#中的变形行为的例子是LINQ的Aggregate方法.

---

变形等价物会是什么？将伪随机数生成器Random视为变形结构或者展开过程是否总是包含如下所示的累加器函数(从Intro到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的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,如果您将其确定性内部结构视为隐式函数,则这是正确的,如您所建议的那样.人们可以使用重新创建这个精确的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对问题的答案什么是catamorphism并且可以在C#3.0中实现？:

Catatorphisms通常指的是任意数据类型的折叠模式.

同样,可以在C#中的二叉树上构造anorporphisms:

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条带中构建Collat​​z数字的一个相当愚蠢的示例:

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

我没有运行上面的任何代码,所以可能会有错误.