序列“基元”的最小集合是什么？ 任何序列计算都需要吗？

Question

我正在用解释器编写类似计划的内容。 类似Scheme 的解释器应该能够很好地与任何实现 IEnumerable 的对象一起工作，这似乎很自然。

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

由于 IEnumerable 不可克隆（请参阅此处），我无法实现迭代该列表有效地使用 car 和 cdr。

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

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

1. 过滤
2. 器映射（完整的映射，而不仅仅是 mapcar）
3. foldr

但我怀疑，例如，我可能可以使用映射和折叠的组合来实现“过滤器”。

我需要公开为“内置函数”的最小原语集是什么，以便我可以通过 IEnumerable 实例实现任何其他功能，而无需过多的运行时或空间成本，并且不必引入突变？

Answer 1

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

1. 过滤=其中
2. 地图=选择
3. 折叠/减少=聚合（foldr=反转然后聚合）

您会发现更多。 例如

SelectMany = 地图 + 地图 + 展平
GroupBy = 分区

remq 和朋友可以用过滤器来完成。

更新

这些显然只需要 1 个列表参数，与正常的方案定义不同。

Answer 2

您并不严格要求 map 是一个原语，因为您可以根据 foldr 来定义它。

示例（在 Haskell 中）：

map f = foldr (\a b->f a:b) []

这实际上是 mapcar 而不是 map，但完整的 map 在 Haskell 中很难表达为 apply 不可用。

更完整的例子（在Scheme中）：

(define (mapcar f l)
  (foldr (lambda (x t) (cons (f x) t)) ‛() l))

(define (heads ls) (mapcar car ls))

(define (tails ls) (mapcar cdr ls))

(define (any-null? ls) (foldr or? ﹟f (mapcar null? ls)))

(define (map f . ls)
  (if (any-null? ls)
      ‛()
      (cons (apply f (heads ls)) (apply map f (tails ls)))))

如果你没有car和cdr，还有其他方法来定义它们，例如，如果你有闭包& 您的语言中的变量：

(define (car a) (foldr (lambda (x y) x) ﹟f a))

(define (cdr a)
  (let ((prev ‛())
        (tmp #f))
    (foldr (lambda (h t) (set! tmp (cons h t)) (set! prev t) tmp)
           ‛()
           a)
    prev))

Answer 3

我不太确定您的序列计算的目标是什么功能，但连接操作（即展平嵌套序列）可能也非常有用。 看一下 Haskell 的列表推导式是如何脱糖的以了解原因。