方案:是否可以将S表达式列表转换为原子列表? [英] Scheme: Is it possible to convert a list of S-expressions into a list of atoms?

问题描述

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

I am trying to convert a list of S-expressions to a plain list of atoms similar to a problem in the book The Little Schemer.

我的代码是(在Dr.Racket中键入):

My code is (as typed in 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)

上面的代码将返回与输入列表相同的列表.我尽力了，但是得到了不同的答案，例如:

The above code is returning back the list the same as input list. I tried my best, but getting different answers like:

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

对于程序中的各种修改.

for various modifications in the program.

我想知道，我们能达到答案吗?

I would like to know, can we achieve the answer:

'(coffee cup tea cup and hick cup)

给予

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

，仅使用 cond cons car 和 cdr .

by using cond cons car and cdr only.

推荐答案

进行调整:

(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)的地鼠" 技巧，将树向右旋转，直到最左边的原子暴露在左上角，然后将其拆分并继续.

Uses John McCarthy's "gopher" trick, rotating the tree to the right until the leftmost atom is exposed in the top left position, then splitting it off and continuing.

这篇关于方案:是否可以将S表达式列表转换为原子列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！