lisp - 每个级别上的原子数，Scheme

Question

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

Write function, that return count of atoms on the each level in the list. For example:

(a (b (c (d e (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)

您对此有何看法？

Answer 1

你知道运行这个会得到什么吗？

(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-expression 是一对(好吧，不是原子)

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

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

您的函数在任何层级都只会找到第一个列表。如果是这样，您会如何将第一个列表中该级别的计数添加到第二个列表？您需要仔细考虑如何在包含多个嵌套列表的列表中完全重复以及如何在每个级别保存信息。有不止一种方法可以做到，但您还没有找到其中任何一种。