什么是变形，它在 C# 中是什么样子的？

Question

我正在努力思考变形的概念。

In functional programming, an anamorphism is a generalization of the concept of unfolds on lists. Formally, anamorphisms are generic functions that can corecursively construct a result of a certain type and which is parameterized by functions that determine the next single step of the construction.

它的对偶，变形，在这个 post 中得到了很好的描述：What is a catamorphism and can it be implemented in C# 3.0?。

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

什么是变形等效物？想想伪随机数生成器是否正确Random as an anamorphic construct or should the process of unfolding always include an accumulator function like the one below (code snippet taken from 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 视为一个隐式函数，这是正确的，正如您所建议的那样。可以使用 Unfold 重新创建这个精确的 PRNG，因此它可能不会使用折叠，但 在功能和语义上等同于 折叠。

上面列表的两次折叠和展开是更一般的列表折叠的特例：

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 中实现吗？:

Catamorphisms in general refer to the pattern of folding for an arbitrary data type.

同样，可以在 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 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);
}

这是构建家谱的异规范示例：

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

我没有运行上面的任何代码，所以可能有错误。

什么是变形，它在 C# 中是什么样子的？

What is an anamorphism, and how does one look like in C#?

c#

functional-programming

catamorphism

anamorphism

recursion-schemes