9

我正试图围绕变形的概念。

在函数式编程中，变形是对列表展开概念的概括。形式上，变形是通用函数，可以核心递归地构造某种类型的结果，并由确定下一个构造步骤的函数参数化。

它的双重性，catamorphism，在这篇文章中有很好的描述：什么是 catamorphism，它可以在 C# 3.0 中实现吗？.

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

什么是变形等价物？将伪随机数生成器Random视为变形构造是否正确，或者展开过程是否应该始终包含如下所示的累加器函数（取自Intro to Rx的代码片段）？

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

1 回答 1

8

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

Catamorphisms 通常是指任意数据类型的折叠模式。

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

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

于 2015-06-16T01:21:03.027 回答