代码之家 › 专栏 › 技术社区 › Paul Hollingsworth

方案:使用fold实现n参数合成

scheme functional-programming

Paul Hollingsworth · 技术社区 · 15 年前

我试图在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)

现在要进行“n参数”组合,我可以这样做:

(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

问题是“初始”函数用于folder命令。它已经建成:

(compose identity (compose list identity))

所以…我不确定解决这个问题的最佳方法。”“foldl”似乎是一个自然的更好的选择,因为我想从“identity”开始左边不是 正确的 …

但是一个幼稚的实现:

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

哪个工作(必须颠倒功能应用程序的顺序):

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

不能解决这个问题,因为现在我不得不把身份函数放在左边!

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

就像,我需要使用“folder”,但是需要一些不同于标识函数的“初始”值…或者更好的身份识别功能?很明显我很困惑!

我想实施它没有必须编写一个显式的尾部递归“循环”…似乎应该有一个优雅的方式来做这件事,我只是被卡住了。

4 回复 | 直到 15 年前

Community CDub 8 年前

你可能想试试 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))

这不是火箭科学:当我把这个贴在IRC频道的时候, Eli 注意到这是 compose . :-)(作为奖励,它还与您的示例一起工作得很好。)

Chris Jester-Young 15 年前

OP提到(在对我答案的评论中)他实施的方案没有 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))))

它所做的是用一个以 <价值观; 符号。在 使用值调用 站点,它检查这个符号是否存在,如果不存在,则将其视为单个值。

如果链中最左边的函数可能返回多个值,则调用代码必须准备解包 <价值观; -标题列表。(当然,如果您的实现没有多个值,那么您可能不会太担心这个问题。)

Apocalisp 15 年前

这里的问题是您试图混合不同数量的过程。你可能想要咖喱清单然后这样做:

(((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元函数:

(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

在种类上有区别。 列表 的类型由两个元素构成(即,列表的类型具有类型 * => * => * 同时 identity 的类型是从一个类型构造的(标识的类型具有类型 * => * )

组合具有以下类型:

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

看看你申请的时候会发生什么 compose 到 列表 和 身份 . A 与 列表 函数,所以它必须是一对(或空列表,但我们将对此进行润色)。 C 与 身份 函数,所以它必须是一个原子。那么,这两个函数的组成必须是一个取原子的函数。 C 并生成一个列表 B . 如果我们只给出这个函数原子,这不是问题,但是如果我们给出它的列表,它将阻塞,因为它只需要一个参数。

咖喱的作用如下:

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

应用 curry 到 列表 你可以看到发生了什么。输入到 列表 统一与 (a)B) . 结果函数接受一个原子(car)并返回一个函数。该函数依次获取列表的其余部分(类型为 乙 ,最后生成列表。

重要的是,课程 列表 功能与 身份 ,这样它们就可以毫无问题地组合起来。这也适用于其他方面。如果您创建一个接受对的标识函数,它可以由 列表 功能。

Paul Hollingsworth 15 年前

虽然“空”列表可以很好地转移到标识函数,但是放弃它似乎会导致以下结果,这并不太糟糕:

(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)