Hi!
I have one assigment to do... I have to write function which returns most
nested list within a list.
(most-nested '(1 2 3 (4 5) 6 ((7 8) 9)))
would return (7 8)
since I'm a complete beginner, I need some advice.
OK, I even know how to solve this problem, but I think that's not the
optimal way. so my not-optimal solution would go something like this:
(defun flatp (sez)
(cond
((null sez) t)
((not (atom (car sez))) nil)
(t (flatp (cdr sez)))
)
)
(defun paren-depth (list)
(cond
((flatp list) 0)
(t (max (+ 1 (paren-depth (first list))) (paren-depth (rest list))))
)
)
from my function I would first call paran-depth on my list. and then go
through the list recursively AGAIN (and that's the problem - it's not
effective!), until I reach n-th level then return list on that level up the
recursion tree.
What's better idea to do that? thank you a lot!
David
David Krmpotic wrote:
>
> Hi!
>
> I have one assigment to do... I have to write function which returns most
> nested list within a list.
>
> (most-nested '(1 2 3 (4 5) 6 ((7 8) 9)))
> would return (7 8)
>
> since I'm a complete beginner, I need some advice.
You don't mention if you've covered VALUES and MULTIPLE-VALUE-BIND
in class, but if you want to compute this in one pass, you'll need
them to carry along the two pieces of information you need:
1) The most-nested-list seen thus far.
2) How deep it is.
You need to walk the tree, carrying along these two pieces of
information, comparing each element to what you've got so far.
You have three basic cases (which you've correctly noticed
in your first attempt): null, an atom, and a list, which has
two subcases -- one where you've found a new deepest-list, and
one where you haven't.
If multiple-values are beyond the scope of the class, then you
can fake them by returning a list or vector of the values, then
crack this list apart in the caller.
> If multiple-values are beyond the scope of the class, then you
> can fake them by returning a list or vector of the values, then
> crack this list apart in the caller.
thank you! I knew I was missing something. I'll try to grasp multiple-values
by
myself. I have gentle lisp pdf, which I think is great.
I didn't mention this in my earlier mail, but this way another try to solve
my problem:
(defun depth (sez)
(cond
((flatp (cadr sez)) (list '0 (cadr sez)))
(t
(let ((sez1 (depth (list (+ 1 (car sez)) (caadr sez))))
(sez2 (depth (cdadr sez))))
(cond
((< (car sez1) (car sez2)) (cadr sez1))
(t (cadr sez2))
))
)
)
)
as you can see, I in fact tried to carry around 2 values. a list, head of
which
is depth and tail is actual nested list. I thought that was silly and didn't
even
mention that. now you said that's the alternative to multiple-values. well,
I'm kinda proud of myself ;)
maybe I'll even try to make my current try work for fun.
OK, I'm going to sleep now 'cause I'm babbling already:)
David Krmpotic wrote:
> as you can see, I in fact tried to carry around 2 values. a list, head of
> which
> is depth and tail is actual nested list. I thought that was silly and didn't
> even
> mention that. now you said that's the alternative to multiple-values. well,
> I'm kinda proud of myself ;)
I wouldn't use this approach unless the teacher says that multiple
values
are off-limits. Multiple values are potentially much more efficient
since most (maybe all) CL implementations implement multiple return
values
without consing, by either pushing them all to the return stack, or
laying
them out in multiple registers, or something along those lines.