Scheme：使用fold实现n参数

Question

我试图在Scheme中找到多个参数“compose”的“最佳”实现（我知道这是在某些实现中的内建，但假设我现在是使用一个没有这个的）。

对于2参数构建功能我有这样的：

(define compose 
    (lambda (f g) 
    (lambda x 
     (f (apply g x))))) 

这样做的好处是，如果最右侧的功能需要额外的参数，这些仍然可以通过组合功能通过。这具有令人满意的特性，即在某物上组合身份功能不会改变该功能。

例如：

(define identity 
    (lambda (x) x)) 

(define list1 
    (compose identity list)) 

(define list2 
    (compose identity list1)) 

(list2 1 2 3) 
> (1 2 3) 

现在做一个“正论证”撰写我可以这样做：

(define compose-n 
    (lambda args 
    (foldr compose identity args))) 

((compose-n car cdr cdr) '(1 2 3)) 
> 3 

但这不再保留那该多好“身份”属性：

((compose-n identity list) 1 2 3) 
> procedure identity: expects 1 argument, given 3: 1 2 3 

问题是用于foldr命令的“初始”函数。它已内置：

(compose identity (compose list identity)) 

所以......我不确定最好的解决方法。 “与foldl”似乎是天然的更好的选择，因为我想将它与“身份”开始对左不是权 ...

但天真的实现：

(define compose-n 
    (lambda args 
    (foldl compose identity args))) 

其中工程（必须扭转的功能应用程序的顺序）：

((compose-n cdr cdr car) '(1 2 3)) 
> 3 

因为现在我最终把身份功能左侧没有解决不了的问题！这就像，我需要使用“foldr”，但需要一些不同的“初始”值比身份函数...或更好的身份函数？显然我很困惑！

我想实现它无需编写明确的尾递归“循环” ...这似乎应该有一个优雅的方式来做到这一点，我只是卡住了。

Answer 1

你可能想尝试this version（使用reduce从SRFI 1）：

(define (compose . fns) 
    (define (make-chain fn chain) 
    (lambda args 
     (call-with-values (lambda() (apply fn args)) chain))) 
    (reduce make-chain values fns)) 

这不是火箭科学：当我张贴这对#scheme IRC频道，Eli指出，这是标准的落实compose 。 :-)（作为奖励，它也适用于你的例子。）

Answer 2

虽然它会一直为“空”名单下放给身份功能不错，交出这似乎导致在下面，这是不是太糟糕：

(define compose-n 
    (lambda (first . rest) 
    (foldl compose first rest))) 

((compose-n cdr cdr car) '(1 2 3)) 

((compose-n list identity identity) 1 2 3) 

Answer 3

这里的问题是你正在尝试混合不同的程序。你可能想咖喱列表，然后做到这一点：

(((compose-n (curry list) identity) 1) 2 3) 

但这并不是很令人满意。

你可能会考虑n元身份功能：

(define id-n 
    (lambda xs xs)) 

然后你就可以创建一个撰写程序专为撰写n元功能：

(define compose-nary 
    (lambda (f g) 
    (lambda x 
     (flatten (f (g x)))))) 

撰写的N-任意数量ary功能与：

(define compose-n-nary 
    (lambda args 
    (foldr compose-nary id-n args))) 

其中的作品：

> ((compose-n-nary id-n list) 1 2 3) 
(1 2 3) 

编辑：它有助于思考的类型。让我们为我们的目的发明一种类型符号。我们将表示作为(A . B)对类型，并且作为[*]列表的类型，与约定[*]相当于(A . [*])其中A是列表的car（的类型，即一个列表是一个对的原子的和一个列表）。让我们进一步将函数表示为(A => B)，意思是“带一个A并返回一个B”。 =>和.都与右侧相关，所以(A . B . C)等于(A . (B . C))。

那么现在，因为，这里有list（读::为 “有型”）类型：

list :: (A . B) => (A . B) 

而这里的身份：

identity :: A => A 

有实物的区别。 list的类型由两个元素构成（即，列表的类型具有种类* => * => *），而identity的类型由一种类型构建（身份的类型具有种类* => *）。

组合物具有这种类型：

compose :: ((A => B).(C => A)) => C => B 

见，当你申请compose到list和identity会发生什么。 A与list函数的域统一，所以它必须是一对（或空列表，但我们会对此进行说明）。 C与identity函数的域统一，所以它必须是一个原子。那么两者的组成就必须是一个函数，它需要一个原子C并产生一个列表B。如果我们只给这个函数原子，这不是一个问题，但是如果我们给它列表，它会窒息，因为它仅仅期待一个参数。

这里的咖喱如何帮助：

curry :: ((A . B) => C) => A => B => C 

应用curry到list，你可以看到发生了什么。输入到list与(A . B)统一。由此产生的功能需要一个原子（汽车）并返回一个函数。该函数反过来将剩下的列表（B类型的cdr），并最终生成列表。

重要的是，咖喱的list功能与identity的功能相同，因此它们可以毫无问题地组成。这也适用于其他方式。如果创建一个带有成对的身份识别功能，则可以使用常规的list功能组成该功能。

Answer 4

OP提到（在我的回答评论中）他的Scheme的实现没有call-with-values。这是伪造它的一种方法（如果您可以确保<values>符号从未在您的程序中使用过：您可以用(void),(if #f #f)或任何您不喜欢的未使用的代码替换它，并且您的实现支持这一功能）：

(define (values . items) 
    (cons '<values> items)) 

(define (call-with-values source sink) 
    (let ((val (source))) 
    (if (and (pair? val) (eq? (car val) '<values>)) 
     (apply sink (cdr val)) 
     (sink val)))) 

这样做的目的是通过以<values>符号为首的列表伪造一个多值对象。在call-with-values网站上，它会检查该符号是否存在，如果不存在，则将其视为单个值。

如果链中最左边的函数可能返回一个多值，那么您的调用代码必须准备好解压<values>-heads列表。 （当然，如果你的实现没有多个值，这可能不会让你太担心。）