c# - 任何序列计算所需的最小序列集 "primitives"是多少？

Question

我正在用解释器编写类似 Scheme 的程序。类似 Scheme 的解释器应该可以很好地与任何实现 IEnumerable 的对象一起工作，这似乎很自然。

解释器不允许突变 - 没有暴露有副作用的函数。

因为 IEnumerable 不可克隆(参见 here )，我无法使用 car 和 cdr 有效地实现列表迭代。

为了让任何“高阶”东西变得高效，我不得不将一些原语实现为解释器的 C# 内置函数。

到目前为止，我已经将以下“原语”实现为 C# 内置函数:

1. 过滤器
2. map (完整 map ，不仅仅是 map 车)
3. 文件夹

但我怀疑，例如，我可能会使用 map 和 foldr 的组合来实现“过滤器”。

我需要公开为“内置”的最小原语集是什么，这样我就可以在 IEnumerable 实例上实现任何其他功能，而无需额外的运行时或空间成本，也不必引入变异？

Answer 1

System.Linq 命名空间中已经为您提供了所有函数。

1. 过滤器 = 在哪里
2. map = 选择
3. fold/reduce = Aggregate(foldr = Reverse then Aggregate)

您会发现更多。例如

SelectMany = map + map + flattenGroupBy = 分区

remq和filter方面的 friend 可以做。

更新

与普通的 Scheme 定义不同，这些显然只接受 1 个列表参数。