1

如何检查 Scheme 中两个列表的结构相等性？例如，(a (b) (c d))等于(a b (c d) (e f g))，(a b)等于(a b c)。列表的数据内容无关紧要，只是其中嵌套列表的结构层次，即子列表的数量，以及那些子列表的子列表数量，等等。

我做了一个函数eqStruct，它接受两个列表作为参数。它应该计算每个列表中的子列表的数量，a然后b返回一个布尔值。该函数查看 list 的每个元素a，然后查看list 的每个元素b。它使用c和分别d作为和中子列表数量的计数器，a并且当在列表的元素上调用b时返回 false 时，这些计数器会递增。atom?每次查看列表的第一个原子后，列表设置为等于自身，没有第一项（列表尾），并且unless当查看整个列表 'a 和 'b 时，循环终止。

(define (eqStruct 'a 'b)

    (define c 0)
    (define d 0)

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

    (unless (null? a)
         (unless (atom? (first a)) (set! c (+ c 1))
         (set! a (list-tail a 1))
    )
    (unless (null? b)
         (unless (atom? (first b)) (set! d (+ d 1))
         (set! b (list-tail b 1))
    )

    (eq? c d)
)

最后一行应该是一个返回语句，因为我希望该函数成为一个谓词并返回列表是否具有相同的结构，一个布尔值，但我不知道如何做到这一点，或者如果我甚至以正确的方式思考这个问题。

4

1 回答 1

4

你的方法

您的代码（以及您对它的评论）指出了对某些 Racket 结构的一些误解。

一个大问题是这unless不是循环结构；它只是有条件地执行一些代码。例如，如果你评估(unless (= 1 2) (display 'x))，你不会x永远打印，而只是打印一次。这意味着你得到的代码不会像你期望的那样做。

但是，如果我们假设是这样（以便我们了解您的代码试图做什么），那么您就有了一个合理的想法。您正在尝试向下迭代列表a并计算它有多少是列表的元素。

    (unless (null? a)
         (unless (atom? (first a)) (set! c (+ c 1))
         (set! a (list-tail a 1))
    )

如果您的列表总是只有一层深，这是一个好主意。例如，您会检查((a b) c)and((a) b c)正确，但您不会得到((a (b)) c)(which has structure ((())())) and (((a) (b)) c)(which has structure ((()())())right。如果您只是想检查和是否a具有b与列表相同数量的元素（如果unless是一个循环结构），你会走在正确的轨道上。

略有不同（但相似）的方法

您尝试从每个输入列表中提取代表列表结构的一些值（在您的情况下为数字）并比较这些代表值时所采用的一般方法是一种很好的方法。我认为您只需要使用稍微不同的代表值，并对它们进行稍微不同的比较（eq?我认为这对您的情况很好，但我想到的代表值需要equal?）。

请注意，鉴于它们的定义方式，结构可以与equal?. 鉴于这一观察，我认为最简单的方法可能是编写一个接受列表并返回其规范结构的过程。还要注意，通过list?在内部使用if，我们可以正确处理((a b) ())结构为 的情况(() ())。

(define (structure list)
  (if (null? list)
      list
      (if (list? (car list))
          (cons (structure (car list)) (structure (cdr list)))
          (structure (cdr list)))))

> (structure '(a (b) (c d)))
(() ())
> (structure '((a b) ()))
(() ())

然后，要比较两个列表的结构，只需获取两个列表的结构并进行比较即可。

(define (structure-equal? list1 list2)
  (equal? (structure list1)
          (structure list2)))

> (structure-equal? '(a b) '(a b c))
#t
> (structure-equal? '(a (b) (c d)) '(a b (c d) (e f g)))
#t

理解为什么equal?在结构上工作不应该太难，但理解如何 structure工作更重要。让我们更仔细地看一下

(define (structure list)
  (if (null? list)
      list ; or '()
      (if (list? (car list))                                    
          (cons (structure (car list)) (structure (cdr list)))
          (structure (cdr list)))))

我们假设list进来的那个实际上是一个列表。这意味着它要么是空列表()（(null? list)确实如此），要么是具有carand的对cdr。空列表的结构显然是空列表，所以我们可以直接返回list（因为它是空的）。另一种情况更复杂； list是一对，其car是某个值，而其cdr是列表的其余部分。如果car也是一个列表，那么它会在 的结构中添加一些东西list，但如果不是，那么它只是一些元素，不会对列表的结构做出贡献。更具体地说，何时list是对(x . y)：

  • 如果x是一个列表，那么它的结构(x . y)是(<structure of x> . <structure of y>)
  • 如果x不是列表，则结构(x . y)为<structure of y>。

这应该解释内部的逻辑if（我们创建一对(a . b)）(cons a b)。

于 2013-10-15T23:03:37.340 回答