方案：是否可以将 S 表达式列表转换为原子列表？

Question

我正在尝试将 S 表达式列表转换为简单的原子列表，类似于书中的问题 The Little Schemer。

我的代码是（在 Dr.Racket 中输入）：

> (define lat '((coffee) cup ((tea) cup) (and (hick)) cup))
> (define f
    (lambda (lat)
      (cond
        ((null? lat) (quote ()))
        ((atom? (car lat)) (cons (car lat) (f (cdr lat))))
        (else (cons (f (car lat)) (f (cdr lat)))))))
> (f lat)
'((coffee) cup ((tea) cup) (and (hick)) cup)

以上代码返回与输入列表相同的列表。我尽力了，但得到了不同的答案，例如：

(coffee)
(cup . cup)
( () (()) (()) )

对于程序中的各种修改。

我想知道，能否实现答案：

'(coffee cup tea cup and hick cup)

给出

'((coffee) cup ((tea) cup) (and (hick)) cup)

仅使用 cond cons car 和 cdr.

Answer 1

您只需将最后一个 cons 替换为 append，即可展平子列表：

(define f
  (lambda (lat)
    (cond
      ((null? lat) (quote ()))
      ((atom? (car lat)) (cons (car lat) (f (cdr lat))))
      (else (append (f (car lat)) (f (cdr lat)))))))

append已经是一个内置的原语，但是如果你想的话，按照你说的原语程序实现起来很简单（当然不推荐：直接使用内置的！ ).

(define (append l1 l2)
  (cond ((null? l1) l2)
        ((null? l2) l1)
        (else (cons (car l1) (append (cdr l1) l2)))))

现在它按预期工作了：

(f '((coffee) cup ((tea) cup) (and (hick)) cup))
=> '(coffee cup tea cup and hick cup)

仅供参考，您尝试实现的过程称为 flatten 并且非常常见，并且一些 Scheme 风格（例如 Racket）已经包含它。在现实生活中，你会做的是：

(flatten '((coffee) cup ((tea) cup) (and (hick)) cup))
=> '(coffee cup tea cup and hick cup)

Answer 2

这似乎接近每个人都想在某个时候编写的标准 flatten 函数。我总是喜欢看看如何使用 append 使用制定议程的好技巧（我认为）来编写这些内容而不会被淘汰。以下是这样做的：注意这可能是 Racket 特有的。

(define (tree->atoms tree)
  (define atom?
    ;; Something is an atom if it is not a cons
    (compose not cons?))
  (define (rev thing)
    ;; this is just reverse
    (let rev-loop ([rt thing] [rrt '()])
      (if (null? rt)
          rrt
          (rev-loop (rest rt) (cons (first rt) rrt)))))
  (let tree->atoms-loop ([it tree]
                         [agenda '()]
                         [results '()])
    (cond [(null? it)
           ;; no more left
           (if (null? agenda)
               ;; no more agenda: we're done, so reverse
               ;; the results and return that
               (rev results)
               ;; more agenda, so carry on
               (tree->atoms-loop (first agenda)
                                 (rest agenda)
                                 results))]
          [(atom? it)
           ;; we've found an atom which is not ()
           (if (null? agenda)
               ;; we're done
               (rev (cons it results))
               ;; there is more
               (tree->atoms-loop (first agenda)
                                 (rest agenda)
                                 (cons it results)))]
          [else
           ;; cons: look at the car, and stuff the cdr onto the agenda
           (tree->atoms-loop (car it)
                             (cons (cdr it) agenda)
                             results)])))

Answer 3

调整它：

(define f
    (lambda (lat)
      (cond
        ((null? lat) (quote ()))
        ;; add this clause
        ((null? (car lat)) (f (cdr lat)))
        ((atom? (car lat)) (cons (car lat) (f (cdr lat))))
        (else ;; (cons (f (car lat)) (f (cdr lat)))
             (f (cons (car (car lat))       ; rotate the tree to the right
                      (cons (cdr (car lat)) (cdr lat))))))))  ; and repeat

使用 John McCarthy 的 "gopher" 技巧，向右旋转树，直到最左边的原子暴露在左上角的位置，然后将其拆分并继续。

方案：是否可以将 S 表达式列表转换为原子列表？

Scheme: Is it possible to convert a list of S-expressions into a list of atoms?

lisp

recursion

scheme

flatten

the-little-schemer