non-linear list conversion to linear

Discussion of Common Lisp
haplo
Posts: 4
Joined: Sun Oct 26, 2008 2:01 pm

non-linear list conversion to linear

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

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

Re: non-linear list conversion to linear

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

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

Re: non-linear list conversion to linear

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

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

Re: non-linear list conversion to linear

Post by 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)

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

Re: non-linear list conversion to linear

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

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

Re: non-linear list conversion to linear

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

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

Re: non-linear list conversion to linear

Post by 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

Post by VincentToups » Thu Oct 30, 2008 7:15 am

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

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: non-linear list conversion to linear

Post by 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/

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

Re: non-linear list conversion to linear

Post by 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:

Post Reply