Nesting level of a list

Q&A's, tips, howto's
Locked
cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Nesting level of a list

Post by cameyo »

I use the following function to calculate the maximum nesting deep of a list:

Code: Select all

(define (nesting lst)
  (cond ((null? lst) 0)
        ((atom? lst) 0)
        (true (max (+ 1 (nesting (first lst)))
                   (nesting (rest lst))))
  )
)

(nesting '(a (((b c (d)))) (e) ((f)) g))
;-> 5
Is there a better/faster way to do this?
Thanks.

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Nesting level of a list

Post by rickyboy »

Here's another way to do it.

Code: Select all

(define (nesting lst)
  (if (null? lst) 0
      (atom? lst) 0
      (+ 1 (apply max (map nesting lst)))))
You be the judge if it's "better". Beware though that, although the code length is shorter, timing tests show that it is slightly *slower* than the original. map has to create more cells, so the slowdown is probably due to that -- which also means increased space overhead! So, maybe you should stick with the original. :)
(λx. x x) (λx. x x)

cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Nesting level of a list

Post by cameyo »

The magic of "map" :-)

fdb
Posts: 66
Joined: Sat Nov 09, 2013 8:49 pm

Re: Nesting level of a list

Post by fdb »

Not very elegant but maybe faster (for short lists I presume)

Code: Select all


(define (nesting lst prev (t 0))
	(if (= lst prev)
		t
	  (nesting (flat lst 1) lst (inc t))))


> (nesting '(a (((b c (d)))) (e) ((f)) g))
5

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Nesting level of a list

Post by rickyboy »

Excellent, fdb! Faster than mine by about a factor of 3 (on the sample input)! 2.5 times faster than the original.
(λx. x x) (λx. x x)

cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Nesting level of a list

Post by cameyo »

Wow!!!
Thanks fdb

Locked