CODEWITHSUNDEEP
nestedlisp
Ryan Miles
Ryan Miles

Reputation: 309

How do I work with nested list in LISP

I am working on a homework assignment, and the first functions had me doing things like deleting a given element of a list, or displaying a given element of a list. The next functions want me to delete nested lists, or display them. Do you have any general tips for working with nested lists? I imagine the functions will be very similar to the ones I wrote before, just tweaked a bit.

Here are two example of functions I have written so far. Note I must use the "cond" style of writing functions. 

(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) )))))

Upvotes: 0

Views: 2966

Answers (1)

Sylwester
Sylwester

Reputation: 48775

Both of your functions work with nested cons. '(1 2 3) is (1 . (2 . (3 . ())) and (cons 1 (cons 2 (cons 3 '()))). A nested list would be that you also have nested cons in the car of cons. eg. ((1 . ()) . ()) ; ==> ((1)).

It's important to be able to see ((1) (2 3)) and understand that it is ((1 . ()) . ((2 . (3 . ())) . ())) so that if you want to access 3 it's obviously the path d,a,d,a and in the reverse you can construct the accessor cadadr.

cons with cons in the car part are trees. When you make a function that walks the tree you need to walk both the car and the cdr in the event they are cons. Thus:

;; 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

The combiner doesn't need to reduce to an atom:

(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)

Upvotes: 1

Related Questions