0

Nested lists in Common Lisp really confused me. Here is the problem:

By using recursion, let (nested-list 'b '(a (b c) d)) return t if the first argument appears in the second argument (which could be a nested list), and nil otherwise.

I tried find, but it only works if the first argument is '(b c). I turned my eyes on lambda expressions. I want to flatten the second argument first, and then use eq to compare the arguments.

(defun nested-list (x y)
  (cond     
    ((null y) ())    
    (t (append (lambda (flatten) (first y))

Then I got stuck. Even though I read a lot of stuff about lambda expessions, it still confused me. I do not know how to recall it when I need, I knew the funcall function, but you know I just cannot get it. I just learnt Common Lisp for 5 days, so I hope you can give me a hint. Thanks a lot!

1
  • 2
    The name for that function is incredibly bad. It should be something like tree-contains-p.
    – Svante
    Sep 1, 2011 at 10:44

1 Answer 1

2

First of all unless you mistyped if instead of iff the problem is quite trivial, just return t and you're done :-)

Seriously speaking instead when you need to solve a problem using recursion the idea often is simply:

  1. if we're in a trivial case just return the answer
  2. otherwise the answer is the same answer we'd get by solving a problem that it's just a little bit simpler that this, and we call ourself to solve this simplified version.

In the specific consider:

  1. If the second argument is an empty list the answer is NIL
  2. If the first argument is equal to the first element of the second argument then just return T instead
  3. Otherwise if the first element of the second list is a list (therefore also possibly a nested list) and the element is contained in this multilist then return true (to check this case the function is calling itself)
  4. Otherwise just check the same problem, but first dropping the first element of the second argument, because it has been checked (this also calls recursively the same function)

So basically 1 and 2 are the trivial cases; 3 and 4 are the cases in which you solve a simpler version of the problem.

1
  • Thanks a lot, I think the way how I deal this problem is unclear. eventhrough I read your suggestion carefully, I’m still entangled with the code. just like I know how to plan it, but don't know how to make a proper implemention
    – roccia
    Sep 3, 2011 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.