什么是变形（anamorphism），在C#中它是什么样子？

Question

我正在努力理解“anamorphism”的概念。

在函数式编程中，anamorphism是对列表展开概念的一般化。形式上，anamorphisms是通用函数，可以递归地构造某种类型的结果，并且由决定构造下一个单步的函数参数化。

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

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

那么，anamorphic等效物会是什么呢？是否正确认为伪随机数生成器Random是一个anamorphic构造，或者展开过程总是包括像下面这个累加器函数（代码片段取自Intro to Rx）？

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

- Jaanus Varus

---

维基百科条目中提到Zip是一个例子。它将两个序列“压缩”在一起。LINQ有一个名为Zip的函数。您提供的示例也符合该定义。但是，没有“完成”谓词，这被说明为可选项。 - CSharpie

根据http://enumeratethis.com/category/c/的说法，`Observable.Generate`是一个展开函数(anamorphism)的例子。然而，就像Aggregate一样，它们并不是真正的通用实现，而是特定于某些数据类型的。 - David Arno

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，如果您将其确定性内部视为隐式函数，则此函数是正确的，正如您所建议的那样。可以使用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对问题“什么是catamorphism并且它可以在C# 3.0中实现吗？”的回答：

总的来说，catamorphisms是指对任意数据类型进行折叠的模式。

同样地，在C#中可以构建二叉树的anamorphisms。

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

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

- sshine

---

我需要更经常地使用树。 - CSharpie