## non-linear list conversion to linear

Discussion of Common Lisp

### 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:
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.
haplo

Posts: 4
Joined: Sun Oct 26, 2008 2:01 pm

### Re: non-linear list conversion to linear

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

Posts: 5
Joined: Sat Jul 12, 2008 4:32 am

### Re: non-linear list conversion to linear

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

Posts: 4
Joined: Sun Oct 26, 2008 2:01 pm

### Re: non-linear list conversion to linear

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)
lnostdal

Posts: 20
Joined: Thu Jul 03, 2008 2:01 pm
Location: Skien, Norway

### Re: non-linear list conversion to linear

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

Posts: 9
Joined: Tue Jul 01, 2008 1:15 pm

### Re: non-linear list conversion to linear

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

Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

### Re: non-linear list conversion to linear

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

Posts: 9
Joined: Tue Jul 01, 2008 1:15 pm

### Re: non-linear list conversion to linear

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

Posts: 9
Joined: Tue Jul 01, 2008 1:15 pm

### Re: non-linear list conversion to linear

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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/
findinglisp

Posts: 440
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX

### Re: non-linear list conversion to linear

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?
lnostdal

Posts: 20
Joined: Thu Jul 03, 2008 2:01 pm
Location: Skien, Norway

Next

### Who is online

Users browsing this forum: No registered users and 9 guests