展平列表的列表 [英] Flattening a List of Lists

问题描述

一般来说，我是Scheme和函数编程的新手。有人可以解释这段代码吗？特别是 kons 和 knil 是什么？我们的目标是将一列列表弄平。

 （define（fold1 kons knil lst）
（if（null （b）b 
 
（k1（kons（car lst）knil）（cdr lst））））
  

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

解决方案

这是一个（奇怪的）fold

。在Lisp中，列表由cons单元格和空列表表示，其中每个（正确）列表或者是空列表（），或者是一个cons单元格，其中 car 是列表中的一个元素，其 cdr 是列表的其余部分。例如，一个清单（1 2 3 4 5）可以由

 <$ c $ （cons 1（cons 2（cons 3（cons 4（cons 5'（））））））
  

您显示的 fold1 函数：

  （定义（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）））））
  pre> 
 
 
这是折叠。这是大量操作的有效概括。例如，如果您使用 0 作为 knil 和 + 作为 kons ，您可以计算列表中元素的总和。
 
 
 
通常折叠是右或左关联。一个适当的左联合折叠将转换为b / b 
 
 （kons（kons（kons（kons knil 1）2）3） 4）5）
  
使用 +   

右边的联合折叠会变成

 （1 +（2 +（3 +（4 +（5 + 0）））））
  

左边的联合折叠效率更高，因为自然实现是尾递归的，并且元素从列表中消耗，可以从列表中提取元素。例如，在正确的左边关联示例中，可以首先计算（kons knil 1），以产生一些值 v ，然后，在相同的堆栈空间中，可以评估（kons v 2），依此类推。正确的关联方法需要先遍历列表的末尾。一个简单的实现需要堆栈空间与列表长度成正比。

这个 fold1 混合了一些东西，因为它正在以左关联的方式处理列表中的元素，但是对于组合函数的参数的顺序是相反的。

定义类型可以在任何时候使用代数数据类型。由于Lisp中的列表要么是空列表，要么是与cons相结合的元素和列表，您可以编写一个处理这些情况的函数，并通过替换 cons 与一个组合函数和具有一些指定值的空列表。

展平列表列表

$ b $因此，如果你有一个列表清单，例如（（ab）（cd）（ef）），它是由

 （cons'（ab）（cons'（cd）（cons'（ef）'（））））
  

使用正确的关联折叠，您可以将它转换为：

<$ p $ （ab）（append'（cd）（append'（ef）'（））））


通过使用 append 为 kons 和



'（）为 knil 。然而，在这个稍微混合的折叠中，你的结构将会是

pre code $（kons'（ef）（kons'（cd）（ kons'（ab）knil）））


so knil 仍然可以是'（），但 kons 需要是一个调用 append ，但交换了参数顺序：

 （define（flatten lists）
（fold1（lambda（right left）
（append left right））
'（）
 lists））
  

所以我们有：

 （flatten'（（ab）（cd ）（ef）））
; => （abcdef）
  

展平更深入的列表清单

<鉴于这是一个 fold 练习，我预计列表的列表只嵌套一层。但是，由于我们已经看到了如何实现一个简单的 flatten

  （define flatten lists）
（fold1（lambda（right left）
（append left right））
'（）
 lists））
  

我们可以修改它以确保更深的列表也被平铺。现在 kons 函数

 （lambda（right left）
（追加左右））
  

只需将两个列表附加在一起。 left 是我们已经建立的已经附加和扁平的列表。 右边是我们现在采用的新组件。如果我们调用 flatten ，那么这也应该使任意嵌套的列表扁平化：



 < code（define（flatten lists）
（fold1（lambda（right left）
（append left（flatten right）））;递归地展平子列表
'（）
列表））
  

这几乎是正确的，除了现在当我们调用（flatten'（（ab）（cd））），我们最终会调用（flatten'（ab）），然后调用（flatten'a），但 flatten 是一个用于 fold1 和 fold1 的包装器，它的参数是列表。当使用非列表调用 flatten 时，我们需要决定如何处理。一个简单的方法是让它返回一个包含非列表参数的列表。

 （define（flatten lists）;列表不一定是a列表中不再列出
（if（not（pair？lists））;也许应该选择一个更好的名字
（列表列表）
（fold1（lambda（right left）
）（附加左（扁平右）））
'（）
 list）））
  

现在我们有

$ $ $ $ $ $ $ $ $ $ $ $（$（$） ）
; => （a b c d）

I'm new to Scheme and functional programming in general. Can someone explain this code — specifically what kons and knil are? The goal is to flatten a list of lists.

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

I'm fairly certain kons is a function as it's being applied to two arguments but still not totally sure about its functionality.

解决方案

This is a (weird) fold

This is a generalized folding procedure. In Lisps, lists are represented by cons cells and the empty list, where each (proper) list is either the empty list (), or a cons cell whose car is an element of the list and whose cdr is the rest of the list. E.g., a list (1 2 3 4 5) can be produced by

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

The fold1 function that you've shown:

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

is a a way of taking a list like the one shown above and transforming it to:

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

This is a fold. This is an efficient generalization of lots of operations. For instance, if you use 0 as knil and + as kons, you compute the sum of the elements in the list.

Usually folds are right or left associative. A proper left-associative fold would transform to

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

which might be clearer when viewed with + and infix notation:

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

The right associative fold would become

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

The left associative fold can be more efficient because the natural implementation is tail recursive, and elements are consumed from the list in the order that they can be extracted from the list. E.g., in the proper left associatve example, (kons knil 1) can be evaluated first to produce some value v, and then, in the same stack space, (kons v 2) can be evaluated, and so on. The right associative method requires traversing to the end of the list first. A naïve implementation requires stack space proportional to the length of the list.

This fold1 mixes things up a bit, because it's processing the elements of the list in a left associative manner, but the order of the arguments to the combining function is reversed.

This type of definition can be used any time that you have a algebraic datatype. Since a list in Lisps is either the empty list, or an element and a list combined with cons, you can write a function that handles each of these cases, and produces a new value by "replacing" cons with a combination function and the empty list with some designated value.

Flattening a list of lists

So, if you've got a list of lists, e.g., ((a b) (c d) (e f)), it's constructed by

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

With a right associative fold, you transform it to:

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

by using append for kons, and '() for knil. However, in this slightly mixed up fold, your structure will be

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

so knil can still be '(), but kons will need to be a function that calls append, but swaps the argument order:

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

And so we have:

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

Flattening deeper lists of lists

Given that this is a folding exercise, I expected that the list of lists are nested only one layer deep. However, since we've seen how to implement a simple flatten

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

we can modify this to make sure that deeper lists are flattened, too. The kons function now

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

simply appends the two lists together. left is the already appended and flattened list that we've been building up. right is the new component that we're taking on now. If we make a call to flatten that, too, that should flatten arbitrarily nested lists:

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

This is almost right, except that now when we call (flatten '((a b) (c d))), we'll end up making a call to (flatten '(a b)), which will in turn make a call to (flatten 'a), but flatten is a wrapper for fold1, and fold1 expects its arguments to be lists. We need to decide what to do when flatten is called with a non-list. A simple approach is to have it return a list containing the non-list argument. That return value will mesh nicely with the append that's receiving the value.

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

Now we have

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

这篇关于展平列表的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！