方案 - 找到最深的嵌套列表 [英] Scheme - find most deeply nested lists

问题描述

我需要在 Scheme 的列表中找到叶子.

I need to find the leaves in a list in Scheme.

例如，如果我有 (1 (2 3) (4 (5) (7 (8) (10 11 12))))))，我的叶子是 (8) 和 (10 11 12).所以我的函数将返回 (1 (2 3) (4 (5) (7 Leaf1 Leaf2))))).

For example, if I have (1 (2 3) (4 (5) (7 (8) (10 11 12)))))), my leaves are (8) and (10 11 12). So my function will return (1 (2 3) (4 (5) (7 leaf1 leaf2))))).

定义:叶子是嵌套最深的元素.

Definition: a leaf is an element with the deepest nesting possible.

示例:在 (1 (2 (3))) 中，元素 (3) 是叶子.

Examples: In (1 (2 (3))) the element (3) is a leaf.

在((1 2) (3 4))中，元素(1 2)和(3 4)是叶子.

我尝试使用 map 函数，该函数将检查列表是否由列表组成.如果是 - 所以我再次调用该函数，如果不是，我打破并将列表更改为叶子符号.它不起作用.

I tried to use the map function, that will check if the list is composed from lists. If it is - so I call the function again, and if not, I break and change the lists to symbols of leafs. It doesn't work.

我已经坚持了 2 天.我试图找到一个想法，而不是实现.谢谢.

I have been stuck on it for 2 days. I am trying to find an idea, not an implementation. Thanks.

推荐答案

这有点棘手.以下是有关一种方法的一些建议:

This is a little tricky to get right. Here are a few suggestions on one way to do it:

如前所述，问题是遍历列表，找到不包含任何其他列表(有时称为原子列表")的嵌套最深的列表，并用其他内容替换它们.可以在一个递归函数中执行此操作，但我认为将其分解为多个部分会更清楚:

As stated, the problem is to walk the list, finding the most deeply nested lists that don't contain any other lists (these are sometimes called "lists of atoms"), and replacing them with something else. It's possible to do this in one recursive function, but I think it's clearer to break it up into parts:

1. 首先，我们需要一个谓词(一个返回布尔值 #t 或 #f 的函数)来确定一个列表是否是一个原子列表.(这有时称为lat?).你可以把它写成一个简单的递归函数，或者你可以使用库函数 any 和 list?

1. First, we need a predicate (a function that returns a boolean #t or #f) to determine whether a list is a list of atoms. (This is sometimes called lat?). You can write this as a simple recursive function, or you could use the library functions any and list?

然后我们需要一个函数 (define (max-lat-depth lst) ...) 来查找其参数中最深嵌套原子列表的嵌套深度.这将是一个双重递归函数——它需要检查每个列表的 first 以及 rest 中的所有元素.我们可以定义max-lat-depth如下:

Then we need a function (define (max-lat-depth lst) ...) to find how deeply nested the most-deeply-nested list of atoms in its argument is. This will be a doubly recursive function -- it needs to check the first of each list as well as all the elements in the rest. We can define max-lat-depth as follows:

一个.如果参数是 lat 本身，则最大深度为零，所以 (max-lat-depth '(1 2 3)) == 0

a. If the argument is a lat itself, the maximum depth is zero, so (max-lat-depth '(1 2 3)) == 0

B.如果参数的第一个元素不是列表，则不会影响整体的最大嵌套深度.因此，在这种情况下，整个参数的 max-lat-depth 将与 rest 的 max-lat-depth 相同(cdr) 的列表:(max-lat-depth '(1 (2 (3 4))) == (max-lat-depth '((2 (3 4))) == 2

b. If the first element of the argument isn't a list, it can't affect the maximum nesting depth overall. So in this case the max-lat-depth of the whole argument will be the same as the max-lat-depth of the rest (cdr) of the list: (max-lat-depth '(1 (2 (3 4))) == (max-lat-depth '((2 (3 4))) == 2

c.棘手的情况:如果参数的第一个元素是一个列表(如 ((1 2) (3 4)))，我们需要在 first<lst 的/code>(或 car)和 rest(或 cdr)，返回这些值的最大值.但是，在取最大值之前，我们需要将这两个结果之一加 1.我会让你弄清楚是哪一个以及为什么.

c. The tricky case: if the first element of the argument is a list (as in ((1 2) (3 4))), we'll need to recur on both the first (or car) and rest (or cdr) of lst, returning the maximum of these values. However, we need to add 1 to one of these two results before taking the maximum. I'll let you figure out which one and why.

最后，我们编写了一个函数 (define (replace-lats-at-depth lst r) ...) 它将采用从 max 返回的嵌套深度-lat-depth、列表 lst 和替换 r.它将返回 lst 的副本，其中深度 depth 的所有原子列表已被 r 替换.例如:

Finally, we write a function (define (replace-lats-at-depth depth lst r) ...) that will take a nesting depth as returned from max-lat-depth, a list lst, and a replacement r. It will return a copy of lst where all the lists-of-atoms at depth depth have been replaced by r. For example:

(replace-lats-at-depth 0 '(1 2 3) '*) == '*

(replace-lats-at-depth 1 '(1 (2) 3) '*) == '(1 * 3).

像max-lat-depth一样，replace-lats-at-depth在first和rest上都重复出现lst 的代码>.它将对其递归调用的结果调用 cons 以构造一个新的树结构.也像 max-lat-depth 一样，它有几种情况，它需要在其递归调用之一中从 depth 中减去 1.

Like max-lat-depth, replace-lats-at-depth recurs on both the first and rest of lst. It will call cons on the result of its recursive calls to construct a new tree structure. Also like max-lat-depth, it has several cases, and it will need to subtract 1 from depth in one of its recursive calls.

一旦你让 replace-lats-at-depth 工作用常量值 r 替换嵌套列表，用它改进它应该不会太难生成 leaf1、leaf2 等的函数，如原始示例中所示.

Once you have replace-lats-at-depth working to replace the nested lists with a constant value r, it shouldn't be too hard to improve it with a function that produces leaf1, leaf2, etc. as in your original example.

我希望这会有所帮助，而不必说太多.如果没有，请告诉我，我可以尝试澄清.

I hope that's helpful without saying too much. Let me know if not and I can try to clarify.

这篇关于方案 - 找到最深的嵌套列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！