麻省理工学院计划的折叠程序有哪些方向？

Question

如果我想在MIT Scheme中反转一个列表,我可以这样做(fold cons '() list),如果列表是(define lis '(1 2 3 4)),则(fold cons '() lis)给出(4 3 2 1).有两种折叠,左右折叠,但如果我使用(fold-right cons '() lis),我会(1 2 3 4)这样,普通折叠不能是那个.此外,如果我使用(fold-left cons '() lis)我得到((((() . 1) . 2) . 3) . 4)这样也不能在原始例子中折叠.反转清单需要什么样的折叠？

我问,因为我希望能够制作一个通用折叠,以便:

(define ls '((1 2 3) (4 5 6)))
(gen-fold cons '() ls)
=> ((6 5 4) (3 2 1))
(define l2 '(((1 2) (2 3)) ((3 4) (4 5))))
(gen-fold cons '() ls)
=> (((5 4) (4 3)) ((3 2) (2 1)))

编辑:为了更好地呈现问题,这些图表描述了我认为在'(fold cons '() '(1 2 3))调用时发生的列表的轮换, 假设它fold是fold-left根据alexis king 修改的:

(define lis (list '(1 2 3))

     cons
    /   \
   1    cons
        /  \
       2   cons
           /  \
          3   '()

(cons lis '())

         cons
        /  \
      cons '()
     /  \
    1   cons
       /   \
      2    cons
           /  \
          3   '()

(fold-left (cons lis '()))

        cons
       /    \
    cons     cons
   /  \      /  \
  2   cons  1   '()
      /  \
     3   '()


        cons
       /    \
    cons     cons
   /  \       /  \
  3   '()    2    cons
                  /   \
                1     '()

   cons
  /  \
 3   cons
     /  \
    2   cons
        /  \
       1   '()

Answer 1

MIT Scheme fold在其基本库中不包含函数,仅用于fold-left和fold-right.但是,确实存在foldSRFI-1声明的功能,它由MIT Scheme支持并展示您描述的行为.

该fold函数是左折叠 - 也就是说,它通过从左到右的迭代累加列表 - 但它与MIT Scheme的fold-left函数的不同之处在于翻转累加器过程的参数顺序.也就是说,fold适用于与所述蓄能器的参数所提供的程序最后,同时fold-left施加与蓄能器的参数的过程的第一.

为了说明这一点,这是一个可以如何定义fold来讲fold-left:

(define (fold proc init lst)
  (fold-left (lambda (x acc) (proc acc x)) init lst))

根据我的经验,fold参数顺序在Lisp实现中更常见,而fold-left参数顺序在其他函数语言中更常见.究其原因,acc要提供的参数最后是正是你发现了原因:它可以更容易使用fold与cons接受的累计值作为他们的第二个参数样的程序.

顺便说一句,你似乎混淆了fold-left,并fold-right在你原来的问题:它是fold-right一个返回列表不变,并fold-left返回倒组对.如果您了解如何fold-left和fold-right定义,这是有道理的.

在某种特定类型的方式,fold-left并fold-right倍以上从起始列表左侧,因为计划列表是单链表,不能从正确的读取.不同之处在于左折叠是迭代的,而右折叠是递归的.

左侧折叠逐个将过程应用于每个元素,然后将结果线程化到下一个应用程序中.当作为嵌套应用程序查看时,这最终会颠倒元素的顺序:

(proc eN ... (proc e1 (proc e0 init)) ...)

相反,右侧折叠以递归方式应用过程,使嵌套应用程序中的顺序保持一致:

(proc e0 (proc e1 ... (proc eN init) ...))

当使用时cons,左侧折叠反转,但右侧折叠只是标识.

(这在像Haskell这样的懒惰语言中可能更有趣,因为正确折叠并不依赖于整个列表,尽管它应该从"右边"开始,因此它可以在无限流上运行......但是,这在Scheme中的相关性要小得多. )