nested - 我如何在 LISP 中使用嵌套列表

Question

我正在做家庭作业，第一个函数让我做一些事情，比如删除列表的给定元素，或显示列表的给定元素。接下来的功能要我删除嵌套列表，或显示它们。您有任何使用嵌套列表的一般技巧吗？我想这些功能将与我之前编写的功能非常相似，只是做了一些调整。

这是我目前编写的两个函数示例。注意我必须使用“cond”风格来编写函数。

(defun delnth(L A)
  (cond ((= A 1) (rest L))
        (t (cons (first L) (delnth (rest L) (- A 1))))))


(defun remv(A L)
  (cond ((eq A (first L)) (remv A (rest L)))
        ((null L) nil)
        (t (cons (first L) (remv A (rest L) )))))

Answer 1

您的两个函数都适用于嵌套的 cons。 '(1 2 3) 是 (1 . (2 . (3 . ())) 和 (cons 1 (cons 2 (cons 3 '() )))。嵌套列表是您还在 cons 的 car 中嵌套了 cons。例如，((1 . ()) . ()) ; ==> ((1))。

能够看到 ((1) (2 3)) 并理解它是 ((1 . ()) . ((2 . (3 . ( ))) . ())) 所以如果你想访问 3 它显然是路径 d,a,d,a 反过来你可以构造访问器 cadadr.

cons 和 car 部分中的 cons 是树。当你创建一个遍历树的函数时，你需要同时遍历 car 和 cdr，如果它们是 cons。因此:

;; generic function to walk trees and reduce
;; by combiner every value accessed by term 
;; the default argument to combiner is tree-null
(defun accumulate-tree (tree term combiner null-value)
  (labels ((rec (tree)
             (cond ((null tree) null-value)
                   ((atom tree) (funcall term tree))
                   (t (funcall combiner (rec (car tree)) 
                                        (rec (cdr tree)))))))
    (rec tree)))

(defun sum-numbers (tree)
  (accumulate-tree tree
                   #'identity
                   #'+
                   0))

(defun count-numbers (tree)
  (accumulate-tree tree
                   (lambda (v) (if (numberp v) 1 0)) 
                   #'+
                   0))

(sum-numbers '((1) (2 3) (((4)) 5)))   ; ==> 15
(count-numbers '(a b 4 3 (e f 5) . 9)) ; ==> 4

组合器不需要缩减为一个原子:

(defun reverse-tree (tree)
  (accumulate-tree tree
                   #'identity
                   (lambda (a d) (cons d a))
                   '()))
(reverse-tree '((1 2) (3 4))) 
; ==> ((nil (nil . 4) . 3) (nil . 2) . 1)