1

请帮我做一个关于该计划的简单练习。

编写函数，返回列表中每个级别的原子数。例如：

(a (b (c (de (f) k 1 5) e))) –> ((1 1) (2 1) (3 2) (4 5) (5 1))

我的解决方案：

(define (atom? x)
  (and (not (pair? x)) (not (null? x))))
(define (count L)
  (cond ((null? L) 0)
        ((pair? (car L))
         (count (cdr L)))
        (else
         (+ 1 (count (cdr L))))))
(define (fun L level)
  (cons 
   (list level (count L))
   (ololo L level)))
(define (ololo L level)
  (if (null? L)
      '()
      (if (atom? (car L))
          (ololo (cdr L) level)            
          (fun (car L) (+ level 1)))))
(fun '(a (b (c (d e (f) k 1 5) e))) 1)

它工作正常，但没有给出这个列表的正确答案：

(a (b (c (d e (f) (k) 1 5) e)))

是：

((1 1) (2 1) (3 2) (4 4) (5 1))

但是我们假设“f”和“k”在一个层次上，答案必须是：

((1 1) (2 1) (3 2) (4 4) (5 2))

我应该如何编辑代码以使其正常工作？

UPD（29.10.12）：我的最终解决方案：

(define A '(a (b (c (d e (f) k 1 5) e))))

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

(define (unite L res)
  (if (null? L) (reverse res)
      (unite (cdr L) (cons (car L) res))))

(define (count-atoms L answ)
  (cond ((null? L) answ)
        ((pair? (car L))
         (count-atoms (cdr L) answ))
        (else
         (count-atoms (cdr L) (+ answ 1)))))

(define (del-atoms L answ)   
  (cond ((null? L) answ)
        ((list? (car L))
         (begin
         (del-atoms (cdr L) (unite (car L) answ))))
        (else
         (del-atoms (cdr L) answ))))

(define (count L)
(define (countme L level answ)
  (if (null? L)  (reverse answ)
      (countme (del-atoms L '()) (+ level 1) (cons (cons level (cons (count-atoms L 0) '())) answ))))
  (countme L 1 '()))

(count A)

对此你能说什么？

4

2 回答 2

2

你知道如果你运行它会得到什么吗？

(fun '(a (b (c (d e (f) k 1 5) e)) (a (b (c)))) 1)

你得到这个：

((1 1) (2 1) (3 2) (4 5) (5 1))

我在右侧添加的整个额外嵌套结构已被忽略。这就是为什么...

函数的每次递归都会做两件事：

  1. 计算当前“级别”的所有原子
  2. 向下移动直到找到一个成对的 s 表达式（嗯，不是原子）

一旦它找到一个嵌套对，它就会调用它自己。等等

当fun从第一个嵌套对返回时， oLoLo会发生什么？为什么，它回来了！它不会继续在列表中查找另一个。

您的函数永远不会在任何级别找到超过第一个列表。如果是这样，您会怎么做呢？将该级别的第一个列表中的计数添加到第二个列表中？您需要仔细考虑如何通过包含多个嵌套列表的列表完全递归，以及如何在每个级别保存信息。有不止一种方法可以做到这一点，但你还没有找到任何一种方法。

于 2012-10-09T14:55:47.697 回答
0

请注意，根据您的实现，此处使用的库可能需要以其他方式导入。可能很难找到必须导入的方式以及要使用的函数的确切名称。filter有些人会把它当作reduce-left代替。require-extension可能是也可能不是Guile特有的，我真的不知道。

(require-extension (srfi 1))
(define (count-atoms source-list)
  (define (%atom? x) (not (or (pair? x) (null? x))))
  (define (%count-atoms source-list level)
    (if (not (null? source-list))
        (cons (list level (count %atom? source-list))
                (%count-atoms (reduce append '()
                       (filter-map
                        (lambda (x) (if (%atom? x) '() x))
                        source-list)) (1+ level))) '()))
  (%count-atoms source-list 1))

当然，正如我之前提到的，最好使用哈希表来做到这一点。使用列表进行操作可能会产生一些教学效果。但我强烈反对那种让你写出本质上糟糕的代码的说教效果。

于 2012-10-09T14:56:27.420 回答