non-linear list conversion to linear

Hello again, can you please help me with this? I've been working on it all night. What I want to do is to take a non-linear list and to convert it to linear. For example the list: (1 (2 (1 3 (2 4) 3) 1) (1 4)) should be made: (1 2 1 3 2 4 3 1 1 4). So far I've managed to produce half a result: (1 2 1 3 2 4) and I really don't know where I'm going wrong since the code seems valid to me.
Here is the code:

(defun lin(x)
  (cond
   ((null x) nil)
   ((listp (car x)) (cons NIL (lin (car x)))) 
   ((atom (car x)) (cons (car x) (lin (cdr x))))
  )
)

Also, if you figure out how to do it can you please tell me how to get each atom only once in the resulting list since I fear my approach on this last bit is a bit blunt.

Look at your

 ((listp (car x)) (cons NIL (lin (car x))))  

That line means means 'if the first element of your list is a list itself, you call lin on it and attach nil to the front.' What you really want to be doing is appending the linearization of (car x) to the linearization of the remainder of x.

It works, thank you. I can't believe I made such a stupid mistake. Sorry to spam the forum with such imbecile questions but I needed this answer fast and didn't have the time to mess around with the code.

and didn't have the time to mess around with the code.

check out Alexandria .. it provides many common utilities, like flatten:

CL-USER> (alexandria:flatten '(1 (2 (1 3 (2 4) 3) 1) (1 4)))
(1 2 1 3 2 4 3 1 1 4)

http://common-lisp.net/project/alexandria/ (get the one from darcs)

You can implement a fun flatten with foldl quite easily:

(defun flatten (lst)
    (reverse
     (foldl
      (lambda (item output)
        (cond ((list? item)
               (foldl #'cons output (flatten item)))
              (t
               (cons item output)))) '() lst)))

Fold is one of my favorite abstractions. This is not tail recursive, unfortunately, but CL does not support tail calls anyway.

VincentToups wrote:...CL does not support tail calls anyway.

Doesn't mandate tail call optimization, you mean. CL implementations are free to implement it if they wish.

If you can't depend on it and you want to be cross-implementation, then it basically isn't supported. This is a whole other can of worms, though.

That should really be listp rather than list? up there. All my lisps run together.

VincentToups wrote:If you can't depend on it and you want to be cross-implementation, then it basically isn't supported. This is a whole other can of worms, though.

Yup. See also: threading, sockets, unicode, etc. This is why we need to come up with a CLv2.

findinglisp wrote:

VincentToups wrote:If you can't depend on it and you want to be cross-implementation, then it basically isn't supported. This is a whole other can of worms, though.

Yup. See also: threading, sockets, unicode, etc. This is why we need to come up with a CLv2.

Oh, you mean SBCL?

findinglisp wrote:

VincentToups wrote:If you can't depend on it and you want to be cross-implementation, then it basically isn't supported. This is a whole other can of worms, though.

Yup. See also: threading, sockets, unicode, etc. This is why we need to come up with a CLv2.

A de facto or community-driven standard composed of compatibility layers and perhaps some libraries would probably be a more realistic approach for now.

Just use Clojure.
Seriously.

qbg wrote:

findinglisp wrote:

VincentToups wrote:If you can't depend on it and you want to be cross-implementation, then it basically isn't supported. This is a whole other can of worms, though.

Yup. See also: threading, sockets, unicode, etc. This is why we need to come up with a CLv2.

A de facto or community-driven standard composed of compatibility layers and perhaps some libraries would probably be a more realistic approach for now.

Yes, agreed. I wasn't suggesting anything more heavyweight than that.

VincentToups wrote:Just use Clojure.
Seriously.

I wouldn't want to miss out on all the goodies in Common Lisp; CLOS, MOP etc. is awesome stuff -- and the SBCL compiler and the integration with Slime is very good.

SBCL has "threading, sockets, unicode, etc.", and it also has FSet: http://common-lisp.net/project/fset/

Having Lisp all the way down (well, almost -- the GC-stuff is in C) is also very cool. I can keep pressing M-. M-. M-. and end up in the SBCL internals (Lisp code!) when I want to know what's going on.

Scott mentions on c.l.l. he's making a new release of FSet this weekend.

I admit, that CL has a lot of great stuff (CLOS/MOP is really excellent), and Lisp all the way down is nice too, but I am tired if fighting with different implementations, libraries that won't compile, and old/esoteric design.

Clojure is clean, functional, and has a large library set which "just works" - it is by far the most painless Lisp I've ever worked with, if you can get used to the purely functional data types (you can, just use them like lists) and live temporarily without tail recursion (you can recur, of course, and regular old recursion is fine, it just will explode at some point).

This is off topic, though.