Page 1 of 1
Nesting level of a list
Posted: Mon May 27, 2019 8:50 am
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.
Re: Nesting level of a list
Posted: Mon May 27, 2019 2:52 pm
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. :)
Re: Nesting level of a list
Posted: Mon May 27, 2019 9:02 pm
by cameyo
The magic of "map" :-)
Re: Nesting level of a list
Posted: Mon May 27, 2019 9:42 pm
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
Re: Nesting level of a list
Posted: Mon May 27, 2019 11:26 pm
by rickyboy
Excellent, fdb! Faster than mine by about a factor of 3 (on the sample input)! 2.5 times faster than the original.
Re: Nesting level of a list
Posted: Tue May 28, 2019 6:09 am
by cameyo
Wow!!!
Thanks fdb