Code: Select all
(defun depth (tree)
(if (atom tree) 0
(1+ (apply #'max (mapcar #'depth tree)))))
I think I need to learn how to do this more simply, but I took the above advice from Ramarren, except I didn't seem to need REDUCE. As a base case, I know the depth of an atom (which I checked, includes nil, the empty list) is 0. For every other case, just add one to the maximum depth of all the elements in the list.
But getting that meaning out the the line of code is hard for a newcomer to lisp (at least it was for me). The first problem is one of terminology: I thought to myself that I need to recursively apply depth to each element in
tree. But to do that, you can't use
apply. I had to realize that
mapcar runs a function on each element of a list and returns one list with all the depths.
It also took me the longest time to understand the difference between
funcall and
apply - and to finally realize that
(max (mapcar #'depth tree)) is wrong because
(max '(2 3 1 2 3 4)) is wrong. I need to write
(max 2 3 1 2 3 4). How, I asked myself, do I flatten a list as a return value?! I still don't think I fully understand in general (though I have found a flatten function in the book "Let over Lambda" - a fantastic read).
But
(apply #'max '(2 3 1 2 3 4)) would work, so
(apply #'max (mapcar #'depth tree)) seems to do the trick. Though if you are worried that you might be passed in a cyclic structure, this will bomb out with a blown stack. I think.
The last newcomer hurdle is why you have to use #' instead of nothing. In scheme you don't, but in CL you do. I think of it as it Perl: $var @var %var and &var are all different namespaces. In CL, there is only $var and &var because any variable can have a list. That's not the whole story because any variable can have a function too. But defun puts the function definition into a different spot than setf, so you need either #'max or the (function max).
