0

我正在尝试在 Scheme 中定义一个函数，使用 Pretty Big 语言（在 Racket 博士中），它将获取一个列表并将所有“原子”转换为顶级元素。例如，如果给定：

(level '(a b (c d) (e f (g 4 h))))
;=> (a b c d e f g 4 h)

这是我到目前为止的代码：

;;level -takes list and returns list w/all elements as top-level
(define level
  (lambda (L)
    (cond ((null? L) L)
          ((not( pair? L)) L)
          (else (append (level(car L)) (level(cdr L)))))))

我的错误如下：

append: contract violation
  expected: list?
  given: d

谁能帮我解决这个错误？

4

3 回答 3

2

有关如何实现的更多信息flatten（通常称为这种函数），请查看

至于您的具体错误，append预计其所有（通常可能需要两个以上）参数都是列表。例如，

> (append '(1 2 3) '(4 5 6))
;=> (1 2 3 4 5 6)
> (append '(1 2 3) '(4 5 6) '(7 8 9))
;=> (1 2 3 4 5 6 7 8 9)

现在，您正在编写函数，并且您已经说过level应该返回一个列表。这意味着如果level有几个不同的执行路径，每个都需要生成一个列表。所以，让我们看看你的实现。

(define level
  (lambda (L)
    (cond ((null? L) L)
          ((not( pair? L)) L)
          (else (append (level(car L)) (level(cdr L)))))))

在问题中，您说您正在编写一个应该采用列表的函数，因此L可以是两件事之一；它可以是空列表，也可以是一对。不过，目前，您cond有三个案例。 

(cond ((null? L) L)                                  ; handle an empty list
      ((not( pair? L)) L)
      (else (append (level(car L)) (level(cdr L))))) ; handle a pair

如果您总是level使用列表调用，则不需要第二种情况。但是，由于在第三种情况下，您确实调用了(level (car L))，并且您不知道是否(car L)会成为列表，因此您似乎最终会使用非列表进行调用。level例如，您需要决定是否(level 'a)应该合法，如果应该，应该是什么。目前，您似乎正在尝试(level 'a)合法并返回(a)。没关系，但您应该指定合同。如果这是您想要做的，那么您确实需要在您的第二个案例cond，但是由于(level 'a)应该返回(a)，您实际上需要那个案例来返回(list L)，而不是L。

这里的另一个选项，如果你确实想要level严格，并且总是需要一个列表作为参数，那么你需要添加更多的逻辑来确定它是否(car L)是一个列表，如果是，递归调用level它，并且打电话append给结果。一种方法是这样的：

(define (level L)
  (cond
    ((null? L) L)
    ((pair? L) (append (if (list? (car L))
                           (level (car L))
                           (list L))
                       (level (cdr L))))))
于 2013-10-14T19:29:47.943 回答
1

在列表上追加作品。如果您level使用列表调用'(1 2 3)第一次迭代，它将执行(append (level '1) (level (cdr '(2 3)))。现在 '1 不是对因此将评估为 1，这不是一个列表。这就像打电话(append '1 ...)是违反合同一样。

编辑

这是flattenPretty Big 中的一个实现。这是基于 Chris Jester-Young对类似问题的回答。它比append版本更有效。

(define (flatten lst)
  ;; helper function that accumulates
  (define (reverse-flatten-into x lst)
    (if (pair? x)
        (foldl reverse-flatten-into lst x)
        (cons x lst)))

  (reverse (reverse-flatten-into lst '())))
于 2013-10-14T18:15:55.740 回答
0

任何时候定义递归函数，每个子句都应该返回相似类型的对象。在您的情况下，第三个子句中的递归调用期望返回一个列表（供 by 使用append），但第二个子句返回一个“原子”。因此编译器/运行时抱怨“预期列表”。

对此的解决方法是(list L)在第二cond个子句中返回。

于 2013-10-15T01:29:26.973 回答