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

这是一个折叠。这是许多操作的有效概括。例如，如果使用0asknil和+as 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) '())))

通过使用appendforkons和'()for 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)

Answer 2

显示的过程是一个实现fold：

在函数式编程中，折叠（也称为减少、累积、聚合、压缩或注入）是指一组高阶函数，它们分析递归数据结构并通过使用给定的组合操作重新组合递归处理的结果它的组成部分，建立一个返回值

记笔记：

• 该kons参数是一个有两个参数的函数，用于将正在处理的列表的当前元素与累积值“组合”
• knil参数为累计输出结果

要了解它是如何工作的，请想象一下我们有这样一个函数：

(define (reverse knil lst)
  (if (null? lst)
      knil
      (reverse (cons (car lst) knil) (cdr lst))))

(reverse '() '(1 2 3 4))
=> '(4 3 2 1)

上面knil是用来累积结果的，它从一个值开始，'()因为我们正在构建一个列表作为输出。并且kons被称为cons，它构建列表。让我们看另一个例子：

(define (add knil lst)
  (if (null? lst)
      knil
      (add (+ (car lst) knil) (cdr lst))))

(add 0 '(1 2 3 4))
=> 10

上面knil是用来累积结果的，它从一个值开始，0因为我们正在构建一个数字作为输出。并且kons被称为+，它添加数字。

到现在为止，您一定已经意识到两个示例共享相同的解决方案结构，都使用输入列表，唯一改变的是我们如何“组合”从列表中提取的值和起始累积值。如果我们很聪明，我们可以将变化的部分分解成一个更高阶的过程，接收变化的部分作为参数——因此fold1诞生了：

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

上面两个例子都可以很容易地用 表示fold1，只需传递正确的参数：

(define (reverse lst)
  (fold1 cons '() lst))

(define (add lst)
  (fold1 + 0 lst))

现在对于问题的第二部分：如果你想用你来展平一个列表，fold1你可以试试这个：

(define (helper x lst)
  (if (pair? x)
      (fold1 helper lst x)
      (cons x lst)))

(define (flatten lst)
  (reverse (helper lst '())))

(flatten '(1 2 (3) (4 (5)) 6))
=> '(1 2 3 4 5 6)

Answer 3

以下代码使用'named let'和'for'循环可用于展平本身可能是列表的元素列表：

(define (myflatten ll)
  (define ol '())
  (let loop ((ll ll))
    (for ((i ll))
      (if (list? i)
          (loop i)
          (set! ol (cons i ol)))))
  (reverse ol))


(myflatten '(a () (b e (c)) (((d))))) 

输出：

'(a b e c d)

但是，它使用'set!'通常不是首选的。

'for'循环也可以用递归'named let'代替：

(define (myflatten ll) 
  (define ol '())
  (let outer ((ll ll))
    (let inner ((il ll))
      (cond
        [(empty? il)]
        [(list? (first il))
         (outer (first il))
         (inner (rest il))]
        [else
         (set! ol (cons (first il) ol))
         (inner (rest il))])))
  (reverse ol))

Answer 4

更短

(define (myflatten lists)
   (foldr append empty lists))

(myflatten (list (list 1 2) (list 3 4 5) (list 6 7) (list 8 9 10)))
> (list 1 2 3 4 5 6 7 8 9 10)