non-linear list conversion to linear

Discussion of Common Lisp

non-linear list conversion to linear

Postby haplo » Wed Oct 29, 2008 12:45 am

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

Postby bsdfish » Wed Oct 29, 2008 1:42 am

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

Postby haplo » Wed Oct 29, 2008 2:57 am

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

Postby lnostdal » Wed Oct 29, 2008 6:21 am

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

Postby VincentToups » Wed Oct 29, 2008 7:12 pm

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

Postby Paul Donnelly » Wed Oct 29, 2008 7:57 pm

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

Postby VincentToups » Thu Oct 30, 2008 6:00 am

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

Postby VincentToups » Thu Oct 30, 2008 7:15 am

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

Postby findinglisp » Thu Oct 30, 2008 9:02 am

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

Postby lnostdal » Thu Oct 30, 2008 9:05 am

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:
lnostdal
 
Posts: 20
Joined: Thu Jul 03, 2008 2:01 pm
Location: Skien, Norway

Next

Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 3 guests

cron