Page 1 of 2

non-linear list conversion to linear

Posted: Wed Oct 29, 2008 12:45 am
by 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.

Re: non-linear list conversion to linear

Posted: Wed Oct 29, 2008 1:42 am
by 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.

Re: non-linear list conversion to linear

Posted: Wed Oct 29, 2008 2:57 am
by 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.

Re: non-linear list conversion to linear

Posted: Wed Oct 29, 2008 6:21 am
by 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)

Re: non-linear list conversion to linear

Posted: Wed Oct 29, 2008 7:12 pm
by 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.

Re: non-linear list conversion to linear

Posted: Wed Oct 29, 2008 7:57 pm
by Paul Donnelly
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.

Re: non-linear list conversion to linear

Posted: Thu Oct 30, 2008 6:00 am
by 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.

Re: non-linear list conversion to linear

Posted: Thu Oct 30, 2008 7:15 am
by VincentToups
That should really be listp rather than list? up there. All my lisps run together.

Re: non-linear list conversion to linear

Posted: Thu Oct 30, 2008 9:02 am
by findinglisp
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.

Re: non-linear list conversion to linear

Posted: Thu Oct 30, 2008 9:05 am
by lnostdal
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? :lol: