function - 使用方案查找两个字符串在结构上是否相等

Question

编写一个 Scheme 谓词函数来测试两个给定列表的结构相等性。如果两个列表具有相同的列表结构，则它们在结构上是相等的，尽管它们的原子可能不同。

(123) (456) 可以 (1(23))((12)3) 不行

我不知道该怎么做。任何帮助，将不胜感激。

Answer 1

这里有一些提示。这个写起来有点重复，因为这个问题看起来像家庭作业我会让你填写细节：

(define (structurally-equal l1 l2)
  (cond ( ? ; if both lists are null
         #t)
        ( ? ; if one of the lists is null but the other is not
         #f)
        ( ? ; if the `car` part of both lists is an atom
         (structurally-equal (cdr l1) (cdr l2)))
        ( ? ; if the `car` part of one of the lists is an atom but the other is not
         #f)
        (else
         (and (structurally-equal ? ?)     ; recur over the `car` of each list
              (structurally-equal ? ?))))) ; recur over the `cdr` of each list

Answer 2

有两种方法可以解决这个问题。第一个使用函数生成表示列表结构的输出。

1. 考虑一种方法，您可以将任何列表的结构表示为唯一的字符串或数字，这样任何具有相同结构的列表都将具有相同的表示形式，并且没有其他列表会生成相同的输出。
2. 编写一个函数来分析任何列表的结构并生成该输出。
3. 通过函数运行两个列表并比较输出。如果相同，则它们具有相同的结构。

第二种方法是 Oscar 采用的方法，即同时遍历两个列表。在这里，您将两个列表传递给一个函数，该函数执行以下操作：

1. 第一个列表的第一个元素是否（结构上）与第二个列表的第一个元素相同？如果不是，则返回 false。
2. 这些是第一个元素列表吗？如果是，则返回结果(and (recur on the first element of both lists) (recur on the rest of both lists))
3. 如果不是，则返回 的结果(recur on the rest of both lists)。

第二种方法在您想要比较两个列表的简单情况下更有效。一旦发现差异，它就会立即返回，只需要完整地处理两个列表，其中两个列表实际上在结构上是相同的。

如果您有大量列表并且可能想要随时比较任意两个列表，则第一种方法可能更有效，因为您可以存储结果，因此任何列表只需要处理一次。它还允许您

• 例如，通过创建一个哈希映射来组织您的列表集合，该哈希映射将具有相同结构的所有列表组合在一起。
• 比较列表的结构相似性（例如，这些列表是否以相同的结构开始和/或结束，即使它们在中间不同？）

不过，我怀疑你的作业最好用第二种方法。