Hi everyone
I have a little task I'm wondering about. Because I'm suppose to figure out, how deep a list is.
Lets say f.ex a function like:
( ( ) , ( ( ) ( ) ) , ( ( ( ( ) ) ) ) )
And I figure out this list should be like "4" or something.
I've set the function like this:
(defun ld (x)
(if (listp x)
(if (null x)
else (if (ld (car x))
(if (ld (cdr x))
)
)
)
But I don't get this function: ( ( ) , ( ( ) ( ) ) , ( ( ( ( ) ) ) ) ) to work. Yes, I'm a newb in CL.
But hopefully some of you could explain something for me.
Thanks Ceenth
How deep is a list?
-
- Posts: 4
- Joined: Thu Nov 05, 2009 2:54 pm
Re: How deep is a list?
Firstly, commas don't get included in lists in Lisp - instead of "( ( ) , ( ( ) ( ) ) , ( ( ( ( ) ) ) ) )" it's "( ( ) ( ( ) ( ) ) ( ( ( ( ) ) ) ) )". Secondly, that is not a function, it's a list. Also, you use "else" in an "if" and use closing parentheses as if you're trying to make Lisp look like C. You probably need to do some reading up on Lisp - the first few chapters of Practical Common Lisp should do you well.
If you're determined to plough on, what I would make a function do is:
If you're determined to plough on, what I would make a function do is:
- If the input is an atom, treat it as a "list" of depth 0.
- Otherwise, the input is a list. Find the depth of the deepest list it contains, and add one to it.
Re: How deep is a list?
First of all, thanks for an answer, I'm trying really to figure this out.
I have to deliver this to my teacher at monday.
Ok, so far I've done this:
And then when I try to f.ex type a list like: (ld '( ( ) ( ( ) ( ) ) ( ( ( ( ) ) ) ) )
I get an error message: Stack overflow on value stack. [Condition of type CCL::STACK-OVERFLOW-CONDITION]
So with simple words, what does that mean? Am I near an solution or will there more hours with "head knocking, to the wall"?
Thanks again
I have to deliver this to my teacher at monday.
Ok, so far I've done this:
And then when I try to f.ex type a list like: (ld '( ( ) ( ( ) ( ) ) ( ( ( ( ) ) ) ) )
I get an error message: Stack overflow on value stack. [Condition of type CCL::STACK-OVERFLOW-CONDITION]
So with simple words, what does that mean? Am I near an solution or will there more hours with "head knocking, to the wall"?
Thanks again
Re: How deep is a list?
Don't include code as a screenshot, use
Code: Select all
tags. There is even a button above the post editing area for it.
[quote="Ceenth"]And I figure out this list should be like "4" or something.[/quote]
In programming precision of thought is all important. If you don't know how to do something, then it will be impossible to express it in a way understandable to a computer.
[quote="Ceenth"]I get an error message: Stack overflow on value stack. [Condition of type CCL::STACK-OVERFLOW-CONDITION][/quote]
It means that your recursive function did not terminate before the stack memory ran out. When writing a recursive function you have to consider a base case, for which recursion does not occur, which terminates the function. This is analogous to [url=http://en.wikipedia.org/wiki/Mathematical_induction]mathematical induction[/url]. Your function does not have a base case.
Also, the recursion step will require either using [url=http://www.lispworks.com/documentation/HyperSpec/Body/f_reduce.htm]REDUCE[/url] built in operator or writing your own variant. Also the [url=http://www.lispworks.com/documentation/HyperSpec/Body/f_1pl_1_.htm]1+[/url] function which adds one to a number.
Always remember to think about what you have to do first, and only express it in a programming language later. Trying to assemble a program by randomly assembling keywords rarely works, and even when it does it doesn't teach anything.
Re: How deep is a list?
Code: Select all
(defun depth (tree)
(if (atom tree) 0
(1+ (apply #'max (mapcar #'depth tree)))))
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).