non-linear list conversion to linear

[haplo]

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:

Code: Select all

(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.

[bsdfish]

Look at your

Code: Select all

 ((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.

[haplo]

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.

[lnostdal]

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

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

Code: Select all

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)

[VincentToups]

You can implement a fun flatten with foldl quite easily:

Code: Select all

(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.

[Paul Donnelly]

...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.

[VincentToups]

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.

[VincentToups]

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

[findinglisp]

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.

[lnostdal]

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?