展平列表列表

Question

我是Scheme和函数式编程的新手.有人可以解释这个代码-具体是什么kons以及knil是谁？目标是压缩列表列表.

(define (fold1 kons knil lst)  
  (if (null? lst)  
      knil  
      (fold1 kons (kons (car lst) knil) (cdr lst))))

我相当肯定kons是一个函数,因为它被应用于两个参数但仍然不完全确定它的功能.

Answer 1

这是一个(奇怪的)折叠

这是一种通用的折叠程序.在Lisps中,列表由cons单元和空列表表示,其中每个(正确的)列表是空列表(),或者car是列表元素的cons单元,其列表cdr的其余部分.例如,一个清单(1 2 3 4 5)可以通过以下方式生成

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))

该 fold1您显示功能:

(define (fold1 kons knil lst)
  (if (null? lst)
      knil
      (fold1 kons (kons (car lst) knil) (cdr lst))))

采用如上所示的列表并将其转换为:

(kons 5 (kons 4 (kons 3 (kons 2 (kons 1 knil)))))

这是一个折叠.这是许多操作的有效概括.例如,如果您使用0as knil和+askons,则计算列表中元素的总和.

通常折叠是右或左关联的.一个合适的左关联折叠将转换为

(kons (kons (kons (kons (kons knil 1) 2) 3) 4) 5)

使用+和中缀符号查看时可能更清楚:

(((((0 + 1) + 2) + 3) + 4) + 5)

正确的联想折叠将成为

(1 + (2 + (3 + (4 + (5 + 0)))))

左关联折叠可以更有效,因为自然实现是尾递归的,并且元素从列表中按照它们可以从列表中提取的顺序被消耗.例如,在适当的左关联示例中,(kons knil 1)可以首先计算以产生一些值v,然后,在相同的堆栈空间中,(kons v 2)可以评估,依此类推.右关联方法需要首先遍历列表的末尾.天真的实现需要堆栈空间与列表的长度成比例.

这fold1有点混淆,因为它以左关联方式处理列表的元素,但是顺序组合函数的参数是相反的.

只要您拥有代数数据类型,就可以使用此类定义.由于Lisp中的列表要么是空列表,要么是元素和列表与缺点相结合,您可以编写一个处理这些情况的函数,并通过cons组合函数和空列表"替换"来生成新值有一些指定的价值.

展平列表列表

所以,如果你有一个列表列表,例如((a b) (c d) (e f)),它是由...构建的

(cons '(a b) (cons '(c d) (cons '(e f) '())))

使用右关联折叠,您可以将其转换为:

(append '(a b) (append '(c d) (append '(e f) '())))

通过使用appendfor kons和'()forknil.然而,在这个略微混合的折叠中,你的结构将是

(kons '(e f) (kons '(c d) (kons '(a b) knil)))

所以knil仍然可以'(),但kons需要是一个调用函数append,但交换参数顺序:

(define (flatten lists)
  (fold1 (lambda (right left)
           (append left right))
         '()
         lists))

所以我们有:

(flatten '((a b) (c d) (e f)))
;=> (a b c d e f)

扁平更深的列表列表

鉴于这是一个fold练习,我希望列表列表只嵌套一层.但是,因为我们已经看到了如何实现一个简单的flatten

(define (flatten lists)
  (fold1 (lambda (right left)
           (append left right))
         '()
         lists))

我们可以修改它以确保更深层次的列表也被展平.该kons现在功能

(lambda (right left)
  (append left right))

只需将两个列表附加在一起即可. left是我们一直在建立的已经附加和展平的列表. right是我们现在正在采用的新组件.如果我们打电话给flatten它,那应该压缩任意嵌套列表:

(define (flatten lists)
  (fold1 (lambda (right left)
           (append left (flatten right)))  ; recursively flatten sublists
         '()
         lists))

这几乎是正确的,除了现在当我们调用时(flatten '((a b) (c d))),我们最终会调用(flatten '(a b)),然后调用(flatten 'a),但是它flatten是一个包装器fold1,并fold1期望它的参数是列表.我们需要决定在flatten使用非列表调用时要执行的操作.一种简单的方法是让它返回一个包含非列表参数的列表.该返回值将与接收值的追加很好地匹配.

(define (flatten lists)               ; lists is not necessarily a list of lists anymore, 
  (if (not (pair? lists))             ; perhaps a better name should be chosen
      (list lists)
      (fold1 (lambda (right left)
               (append left (flatten right)))
             '()
             lists)))

现在我们有

(flatten '(a (b (c)) (((d)))))
;=> (a b c d)