1

如果我有一个 s 表达式，例如 '(1 2 (3) (4 (5)) 6 7)，我将如何将其转换为类似 (1 2 3 4 5 6 7) 的列表？我基本上需要从 s 表达式中提取所有原子。是否有内置功能可以帮助我做到这一点？

(define (convert-to-list s) ... )

到目前为止，我的算法是，如果第一个元素是原子，则将其附加到列表中。如果第一个元素是列表，则获取该元素的汽车，然后使用该函数调用函数（转换为列表），以便捕获递归的基本情况。并将在 convert-to-list 上调用的该列表的 cdr 附加到它的 car 上。我正在尝试从计算机程序的结构和解释中自学方案，而我只是在尝试随机的东西。事实证明，递归执行此操作比我预期的要困难。

4

5 回答 5

4

要从字面上回答您的问题，“是否有内置功能可以帮助我做到这一点？”，在 Racket 中是的。flatten正是这样做的：“将任意 S 表达式对的结构展平为一个列表。”

Examples:
> (flatten '((a) b (c (d) . e) ()))
'(a b c d e)
> (flatten 'a)
'(a)

然而，思考如何编写flatten自己是一个很好的练习。

Chris Jester-Young 的评论有一个优雅方式的链接。如果她将其发布为答案而不是评论，我建议将她的答案标记为已接受，而不是我的。:)

于 2013-05-09T03:38:32.987 回答
1

你的算法看起来不错，只是少了一两步。

(define (flatten lst) ; 'flatten' is a better name for this function IMO
  (cond
    ((null lst) nil)
    ;; Don't worry that I'm calling (flatten (cdr lst)) without any checking;
    ;;  the above case handles it
    ((atom (car lst)) ; The car's okay
     (cons (car lst) (flatten (cdr lst))))
    ((cons? (car lst)) ; The car still needs flattening; note the use of
                       ;  'append' here (the car-list may have any number of elements)
     (append (flatten (car lst)) (flatten (cdr lst))))))

在(flatten (car lst))处理第一个元素的(flatten (cdr lst))调用和递归处理列表其余部分的调用之间，输入列表最终是一个平面列表（即没有元素是 conses）。

（警告：我不是方案专家；上面的代码可能包含错误。）

于 2013-05-09T02:58:44.453 回答
1

现在，如果您想要更快的实现，则根本不需要append。

这个想法是传递您将附加的内容作为参数。我称之为尾巴。如果你有一个空的 s-exp，你只需返回尾部，因为没有什么可以添加到它的。

我有代码，flatand flat2， whereflat使用match语句，在球拍中的东西，并且flat2只使用 a cond，我发现它有点难以阅读，但我提供它以防你还没有看到match。

#lang racket


(define (flat s-exp tail)
  (match s-exp
         ['() tail]
         [(cons fst rst)
          (let ([new-tail (flat rst tail)])
            (flat fst new-tail))]
         [atom
          (cons atom tail)]))

(define (flat
  (cond
    [(empty? s-exp) tail]
    [(list? s-exp)
     (let* ([fst (first s-exp)]
            [rst (rest  s-exp)]
            [new-tail (flat])
       (flat fst new-tail))]
    [#t 
     (cons s-exp tail)]))

要使用它们，请像这样称呼它们(flat '(1 () (2 (3)) 4) '())===> '(1 2 3 4)。您需要为他们提供空列表才能开始。

于 2013-05-09T03:43:07.607 回答
1

您的案例应涵盖空列表、原子、 (car s) 是原子、 (car s) 是列表。

这行得通，尽管我因为不记得内置函数是什么而取消了列表附加函数。在 Racket Advanced Student 工作。

(define (list-glue left-list right-list)
  (cond
    ((null? left-list) right-list)
    (else (cons (car left-list) (list-glue (cdr left-list) (right-list))))))

(define (convert-to-list s)
  (cond 
    ((null? s) '())
    ((not (list? s)) (cons s (quote ())))
    ((not (list? (car s))) (cons (car s) (convert-to-list (cdr s))))
    (else 
      (list-glue 
        (convert-to-list (car s))
        (convert-to-list (cdr s))))))
于 2013-05-09T03:12:10.017 回答
0

这可以简单地通过递归子列表和休息列表来完成。你可以看到这段代码读起来有多容易。像这样：

(define (convert-to-list list)
  (if (null? list)
      '()
      (let ((next (car list))
            (rest (cdr list)))
        (if (list? next)
            (append (convert-to-list next) (convert-to-list rest))
            (cons next (convert-to-list rest))))))
> (convert-to-list '(a b c))
(a b c)
> (convert-to-list '((a b) (((c d) e f) g h) i j))
(a b c d e f g h i j)
>
于 2013-05-09T18:13:31.090 回答