Finding the depth of a list using (constrained) Racket

Question

Another question of logic, the task is to find the depth of a list, for example: given a list of (A B (C D (E))) it should somehow indicate that the depth is 2 (or 3 if you include the base list). I am restricted to a set of common Racket functions of which I will list below. Where I am at I can iterate through the list but end up halting at the first sub-list, i.e: (A (B (C)) (D (E (F)))) comes out as only 2.

Here is the list of functions available:

• cons, car, cdr, define, quote, if, cond, else
• Basic forms of arithmetic (+, -, *, /)
• Very basic tests (null?, list?, eq?, numeric comparisons)

Here is my definition so far, I would really appreciate if someone could just shift me in the right direction.

(define (len l) (if (null? l) 0 (+ 1 (len (cdr l)))))

(define A '(A (B) (C (D))))

(define (depth l) (cond

                    [(null? l) '()]

                    [(list? (car l)) (cons (car l) (depth (car l)))]

                    [else (depth (cdr l))]

                    ))

(depth A)

(len (depth A))

Answer 1

Here is my definition in Common Lisp

(defun list-depth (list &optional (depth 0))
  (cond ((null list) depth)
        ((atom (first list)) (list-depth (rest list) depth))
        (t (max (list-depth (first list) (1+ depth))
                (list-depth (rest list) depth)))))

I don't have Racket installed on this computer, so here is an untested translation to Scheme/Racket:

(define (list-depth lst depth)
  (cond ((null? lst) depth)
        ((not (list? (car lst)) (list-depth (cdr list) depth))
        (else (max (list-depth (car lst) (+ 1 depth))
                   (list-depth (cdr lst) depth)))))

Logic is as follows:

• If the list is empty, return current depth.
• If the car of the list is atom (not list), it won't increase the depth, find the depth of the rest (cdr) of the list.
• Otherwise, the depth is going to be the maximum between the +1 depth of car (remember, it is the list now) and the depth of the cdr of the list. Notice increase of the depth for car and not for cdr.

Pre-defined procedures used: +, max, null?, list?, car, cdr, not.

Answer 2

In my answer here, lists start with a depth of 0 and increase by 1 for each level of nesting. If you'd like for them to start with a depth of 1, you can change (y 0) to (y 1) in the list-depth procedure

This can be implemented with a straightforward fold

(define (list-depth xs (y 0))
  (foldl (λ (x z)
           (if (list? x)
               (max z (list-depth x (+ 1 y)))
               (max z y)))
         y
         xs))

foldl has a simple implementation of

(define (foldl f y xs)
  (if (null? xs)
      y
      (foldl f (f (car xs) y) (cdr xs))))

Here's some outputs

(list-depth '())                              ; ⇒ 0
(list-depth '(A))                             ; ⇒ 0
(list-depth '(A (B)))                         ; ⇒ 1
(list-depth '(A (B (C))))                     ; ⇒ 2
(list-depth '(A (B (C (D (E)))) (B (C)) (B))) ; ⇒ 4

---

If you don't want to use the fold abstraction, you can expand the fold within list-depth to

;; THIS CODE IS BROKEN, DO NOT USE
;; @mobiuseng found bugs
(define (list-depth xs (y 0))
  (cond
    [(null? xs) y]
    [(list? (car xs))
     (max y (list-depth (car xs) (+ 1 y)))]
    [else
     (max y (list-depth (cdr xs) y))]))

Both result in the same output, but in this implementation, the two concepts of folding and max are tangled together. Seeing the guts of the fold makes it much harder to read this answer compared to the first one.

The guts of the fold made it easy for bugs to hide in this last snippet. I can't suggest writing this way in the first place, so I'm not going to bother spending effort to fix it.

Answer 3

Every list is built of a current element, under its car, and the rest of the list, under the cdr.

• The depth of the list is the same as depth of the rest of the list, if that's the deepest.

• The depth of the list is one more than the depth of its car, if that's the deepest.

So,

(define (depth lst)
  (define a-depth (+ 1 (depth (car lst))))
  (define d-depth (depth (cdr lst)))
  (if (< ..... ) ..... 
    ; or else
    ...... ))

And of course, don't forget to handle the case when the list is empty, or an atom (not a pair — you can't call car or cdr with a non-pair argument, it would cause an error if you did):

• The depth of an empty list is zero.

• The depth of an atom is zero.