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

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

  •  9
  • 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 年前
        1
  •  4
  •   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 . :-)(作为奖励,它还与您的示例一起工作得很好。)

        2
  •  4
  •   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))))
    

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

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

        3
  •  2
  •   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)并返回一个函数。该函数依次获取列表的其余部分(类型为 ,最后生成列表。

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

        4
  •  1
  •   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)