CODEWITHSUNDEEP
listrecursionschemeracket
pesho
pesho

Reputation: 111

Depth of list in scheme

I'm trying to write a program in scheme that will find the maximum depth of a list. My code so far is:

(define (depth l)
  (define (helper l count)
    ( cond
        ((null? l) count)
        ((not(list? (car l))) (helper (cdr l) count))
        (else (helper (car l) (+ count 1)) )
    )
  )
  (helper l 1)
)

It works for lists of this type (depth '(1 2 3 (2))) -> 2, but obviously not for list of the type (depth '( (2) ((3))) -> 3. The problem is that when I first encounter a list, I automatically jump to it increment the count and call it recursively again, ignoring the other elements of the list. I want to fix this problem and I thought of adding another variable temp which to hold the current count for each element in the list and check if it is bigger than count and if it is true I set! count to temp, but again I have a problem with the recursion. My other idea was to use another list in which to append count on every step and find the maximum value in that list, but I couldn't realize that too. Any ideas how to do this problem?

Upvotes: 0

Views: 2652

Answers (1)

Alexis King
Alexis King

Reputation: 43902

Here's an implementation using map:

(define (max-depth l)
  (define (helper depth el)
    (cond
      [(null? el) (add1 depth)]
      [(list? el)
       (apply max
               (map (curry helper (add1 depth))
                    el))]
      [else depth]))
  (helper 0 l))

While I think this implementation is fairly elegant, it admittedly is not tail-recursive.

Here is a slightly more complex, breadth-first tail-recursive implementation:

(define (max-depth l)
  (define (helper depth els)
    (define remaining (filter list? els))
    (if (zero? (length remaining))
        depth
        (helper (add1 depth) (apply append remaining))))
  (helper 1 l))

Upvotes: 1

Related Questions