2

我正在寻找一个将原子列表递归地转换为单个列表的答案。

一个例子是，(slist '(a (b c) (d e (f) g) h))进入(slist (a b c d e f g h))

任何答案都会有所帮助。

4

3 回答 3

3

您正在尝试做的事情称为展平列表。这里有一堆选项：

; required predicate

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

; naïve version using append

(define (flatten1 lst)
  (cond ((null? lst)
         '())
        ((not (pair? lst))
         (list lst))
        (else
         (append (flatten1 (car lst))
                 (flatten1 (cdr lst))))))

; naïve version using append, map, apply

(define (flatten2 lst)
  (if (atom? lst)
      (list lst)
      (apply append (map flatten2 lst))))

; efficient version using fold-left

(define (flatten3 lst)
  (define (loop lst acc)
    (if (atom? lst)
        (cons lst acc)
        (foldl loop acc lst)))
  (reverse (loop lst '())))

; very efficient version with no higher-order procedures

(define (flatten4 lst)
  (let loop ((lst lst)
             (acc '()))
    (cond ((null? lst)
           acc)
          ((not (pair? lst))
           (cons lst acc))
          (else
           (loop (car lst) (loop (cdr lst) acc))))))

以上任何一项都将按预期工作。例如，使用flatten4：

(flatten4 '(a (b c) (d e (f) g) h))
=> '(a b c d e f g h)

根据您使用的解释器，它很可能已经包含一个实现。例如，在球拍中：

(flatten '(a (b c) (d e (f) g) h))
=> '(a b c d e f g h)
于 2013-08-07T13:48:15.410 回答
1

在 Lisp 中，与 Scheme 不同，您必须接受这样一个事实，即原子nil在列表结构中表示一个空列表。所以，严格来说，当你展平一个列表时，你并没有从树结构中获得所有的原子。只有那些不代表空列表和列表终止符的。

您还必须做出设计决定：您的代码是否处理不正确的列表和循环列表？也就是说，这些case应该怎么做：

(flatten '(a . b))  ;; (a b), accurate diagnostic or failure?

(flatten '#1=(a . #1#))  ;; (a), accurate diagnostic or failure?

您是否处理这种情况并收集树结构中存在的实际非列表原子，而不管循环或不正确的终止？或者您是否准确地检测到情况并报告有意义的诊断？或者只是忽略这种可能性，让代码在较低级别的函数中爆炸，或者执行失控递归？

如果您不关心处理不正确的列表和循环结构，则将列表展平是这样递归定义的。

  1. 通过返回包含该原子的列表来展平非列表。
  2. 列表通过展平其所有元素并将它们连接起来来展平。

在 Lisp 中，编写代码通常比英文规范或伪代码更容易和更清晰：

(defun flatten (obj)
"Simple flatten: no handling of improper lists or cycles"
   (if (listp obj)
     (mapcan #'flatten obj)
     (list obj)))

请注意，虽然mapcan是破坏性的，但这并不存在问题，因为它只连接在我们的函数调用中构造的列表结构，而不是任何传入的列表结构。换句话说，我们的输出与输入不共享结构。

于 2013-08-07T23:03:07.257 回答
0

您已经检查了一个正确的答案，但这是一个简单的实现，它清楚地表明了递归：

(define (slist list)
  (if (null? list)
      '()
      (let ((next (car list))
            (rest (cdr list)))
        (if (list? next) 
            (append (slist next) (slist rest))
            (cons next (slist rest))))))
于 2013-08-08T04:06:52.197 回答