CODEWITHSUNDEEP
listlispcommon-lispdepthclisp
Norby
Norby

Reputation: 57

LISP Determine the depth of a list

I'm trying to write a function that determines the depth of a list. So for

and so on.

This is what I've written so far and it works only for linear lists (depth = 1) and for lists with depth = 2.

I think I'm close to the correct solution but I feel I'm missing something..

(defun detlen (lst count)
    (
        cond
            ((null lst) count)
            ((LISTP (car lst)) (setq count (+ count 1)) (detlen (cdr lst) count))
            (t (detlen (cdr lst) count))
    )
)

Upvotes: 1

Views: 1381

Answers (2)

user5920214
user5920214

Reputation:

I was thinking about this, and I realised that you can generalise it nicely. If you have two operations, along which moves a cursor along some objectanddownwhich moves down into elements of it, as well as anapplicable?predicate which tells you ifdowncan be called, then you can write this rather general function to compute thedown`-depth of something (this is in Racket, where it's easier because of Lisp-1-ness):

(define (dual-depth thing down along applicable?)
  ;; given dual operations down and along, and a test, applicable?,
  ;; return the down depth of thing.
  ;; This is zero if applicable? is false, and can fail to terminate if
  ;; the structure has cycles either in down or along.
  (let dd ([it thing])
    (if (applicable? it)
      (let dd-loop ([tail it] [so-far 0])
        (if (not (applicable? tail))
            so-far
            (dd-loop (along tail) (max so-far (+ 1 (dd (down tail)))))))
      0)))

And then

(define car-depth
  ;; the depth of a cons tree thought of the way it is written
  (λ (l) (dual-depth l car cdr cons?)))

(define cdr-depth
  ;; the depth of a cons tree thought of the other way
  (λ (l) (dual-depth l cdr car cons?)))

Or even:

(define car-depth
  (curryr dual-depth car cdr cons?))

(define cdr-depth
  (curryr dual-depth cdr car cons?))

Upvotes: 1

Rainer Joswig
Rainer Joswig

Reputation: 139251

The depth of a list is:

(+ 1 (reduce #'max (mapcar #'depth list) :initial-value 0))

Compute all depths and then take the maximum. Add one. A non-list has depth 0.

CL-USER 195 > (defun depth (list)
                (if (listp list)
                    (+ 1 (reduce #'max (mapcar #'depth list)
                                 :initial-value 0))
                    0))
DEPTH

CL-USER 196 > (depth '(((2)) (1)))
3

Upvotes: 6

Related Questions