functional-programming - 展平列表列表

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 单元格和空列表表示，其中每个(正确的)列表是空列表 () , 或一个 cons 单元格，其 car是列表的一个元素，其 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)))))

这是 fold .这是许多操作的有效概括。例如，如果您使用 0如 knil和 +如 kons ，您计算列表中元素的总和。

通常折叠是右或左关联的。适当的左关联折叠将转换为

(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有点困惑，因为它以左关联方式处理列表的元素，但是组合函数的参数顺序是相反的。

只要您有代数数据类型，就可以使用这种类型的定义。由于 Lisps 中的列表要么是空列表，要么是一个元素和一个结合了 cons 的列表，因此您可以编写一个函数来处理每种情况，并通过“替换” 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) '())))

通过使用 append对于 kons , 和 '()对于 knil .但是，在这个稍微混杂的折叠中，您的结构将是

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