reverse not working: CL-USER> (rvrs '(1 2 3)) (((NIL . 3) . 2) . 1)

ssecorp wrote:
> On Aug 23, 6:55 pm, Kenny <kentil...@gmail.com> wrote:
>
>>ssecorp wrote:
>>
>>>my reverse:
>>>(defun rvrs (lista)
>>> (if (null lista)
>>> '()
>>> (cons (rvrs (cdr lista)) (car lista))))
>>
>>>CL-USER> (rvrs '(1 2 3))
>>>(((NIL . 3) . 2) . 1)
>>
>>>built-in:
>>>CL-USER> (reverse '(1 2 3))
>>>(3 2 1)
>>
>>>So my reverse gets the spirit right but doesnt deliver exactly what I
>>>want. How do I cons without adding dots?
>>
>>Do you know what a cons is, and how a proper list is defined in terms of
>>conses?
>>
>>kt
>
>
> yes

no.

Show us how to create the list (1 2) using only cons.

then take that list and the list (3 4) and create (1 2 3 4) using only
cdr and setf. it's ok if the solution works only if the first list is
length 2.

kt

ssecorp <circularfunc@gmail.com> writes:
> but Im still trying to figure out how to do it with just one simple
> reucrsive function just as an exercise.

Doing it with a simple recursive function, you will either need a lot
of time, or a little more space.


Assume you want to reverse list = (a b c d e)

(first list) = a
(rest list) = (b c d e)

(rev (rest list)) = (e b c d)

which is almost what you want, only with a appended. If you use
(nconc (rev (rest list)) (list (first list))) you will spend O(N^2)
time walking the reversed sublists to add the last element. And if
you use append instead of nconc, you will allocate also O(N^2)
temporary cons cells.


So let's do otherwise. Instead of taking the reverse of the rest, you
could remark that
(rev (list (first list))) == (list (first list)) == (a)
and that you can build (b a), the reverse of list = (a b)
with (cons (first (rest list)) (list (first list)))

Then you can build the reverse of the list by taking the first
element, and cons it to the resulting, reversed list. You need two
parameters:

(defun rev (list reversed) ...)

(rev '(a b c) '()) --> (c b a)



--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962O20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/

On Sat, 23 Aug 2008 09:25:34 -0700, ssecorp wrote:

> So my reverse gets the spirit right but doesnt deliver exactly what I
> want. How do I cons without adding dots?

Please do yourself a favor and read (up to) Chapter 3 of Graham's ANSI
Common Lisp.

Tamas

On Aug 23, 6:25*pm, ssecorp <circularf...@gmail.com> wrote:
> my reverse:
> (defun rvrs (lista)
> * (if (null lista)
> * * * '()
> * * * (cons (rvrs (cdr lista)) (car lista))))
>
> CL-USER> (rvrs '(1 2 3))
> (((NIL . 3) . 2) . 1)
>
> built-in:
> CL-USER> (reverse '(1 2 3))
> (3 2 1)
>
> So my reverse gets the spirit right but doesnt deliver exactly what I
> want. How do I cons without adding dots?



( defun my-reverse ( list)
(if ( null list)
nil
(append ( my-reverse ( cdr list)) (list ( car list)))))
Not very elegant, but it works!!

ardaliev <ardaliev@gmail.com> writes:

> On Aug 23, 6:25Â*pm, ssecorp <circularf...@gmail.com> wrote:
> > my reverse:
> > (defun rvrs (lista)
> > Â* (if (null lista)
> > Â* Â* Â* '()
> > Â* Â* Â* (cons (rvrs (cdr lista)) (car lista))))
> >
> > CL-USER> (rvrs '(1 2 3))
> > (((NIL . 3) . 2) . 1)
> >
> > built-in:
> > CL-USER> (reverse '(1 2 3))
> > (3 2 1)
> >
> > So my reverse gets the spirit right but doesnt deliver exactly what I
> > want. How do I cons without adding dots?

These first remarks are to ssecorp:

The dots are not really there. They are visual artifact, not something in
your code. All lists have them, but they are almost always not shown to
you. That is,

(a . (b . (c . ())))

is the same as (a b c), the printer just doesn't show you. But the dot is
there. What the dot tells you, when you see it appear, is that none of the
shorthand rules for eliding the dot applies. Since all of the shorthanding
rules rely on there being a proper list to the right of the dot, what this
tells you is that you've built a cons that is not a proper list; that is,
it is not a list whose righthand backbone ultimately terminates in an
empty list. And since the reverse of a proper list is a proper list, what
you're really learning is that you have not correctly constructed either the
base case [which is fine here] or the inductive step.

So consider your inductive step:

(cons (rvrs (cdr lista)) (car lista))

What this implies is that there is some list

( first . rest )

such that

( rest . first )

is its reverse. And that assumption is false. The reverse of a right-handed
list is not a left-handed list. It is a right-handed list that has its
elements in the other order. That is,

(1 2 3)

which is the list

(1 . (2 . (3 . ())))

must reverse to

(3 . (2 . (1 . ())))

not to

(((() . 3) . 2) . 1)

So you must write the recursion differently. I'm not going to do that
for you. But hopefully seeing that the dot is not the problem but rather
your understanding of the structure to be achieved is the problem, you'll
get there.

Getting back to ardaliev's reply:

> ( defun my-reverse ( list)
> (if ( null list)
> nil
> (append ( my-reverse ( cdr list)) (list ( car list)))))
> Not very elegant, but it works!!

It's partly not elegant because of the spaces between th open parens
and the operators. That's a superficial matter, but you should definitely
avoid this. There are many variations of good Lisp style, but there is
almost no reason for ever doing this. [I could cite exceptions. Nearly all
style rules have exceptions, after all. But I know of no exceptions that
would apply here.]

The really inelegant part is the call to APPEND. APPEND is an O(n),
not an O(1) function. In sloppy terms, it means it has to do work
proportional to the number of elements in the list it's appending to.
That is, if you're adding one element to the end of an n-length list
inside a loop from 0 to n, then APPEND will get called, on average n/2
(the average length of the list) times n (the number of times you
looped) or 1/2 n^2, which we notate as just O(n^2) ignoring the constant
factor of 1/2 because as the problem goes, the dominant bit of interest
is the exponent, not the constant factor.

Anything O(n^2) can be trouble even if n gets only moderately large.
You're better off sticking to CONS when you're in a loop, since it is
O(1). That doesn't mean you can just substitute CONS for APPEND and
be done with it--it's not the same function, and so what you have to
do with CONS is different. But it does mean when you see APPEND in a
loop [or in a recursion] in your code, you should always be nervous
and double-checking your algorithmic complexity VERY carefully.

So the speed issue is the true inelegance of what you offer, and in
truth although what you have is probably functionally correct (returns
the intended answer--I didn't try it, actually, but it looks
plausible), it's a major hurdle in the learning of Lisp that you must
not accept this as correct because there is more to a program,
especially a very general subroutine like a REVERSE function, than
functional correctness. If you tolerate algorithmic inefficiency,
your programs (even when compiled with heavy optimization) will run
very slowly when they get to even intermediate size, and you'll
probably blame the language rather than your own coding. (That's
convenient if you're in the kind of verbal debate where people don't
do much fact-checking and want to believe an unfounded claim that Lisp
is slow anyway; you'll probably find many people rushing to agree with
you because they want to believe that Lisp is slow and they applaud
you for 'proving' it. But it's less good if you actually care about
what the truth of why your program runs slowly is.)

* Frank Buss <12gp6bgi1a0zr$.tfebivh3tkwl$.dlg@40tude.net> :
Wrote on Sat, 23 Aug 2008 19:39:57 +0200:

| One idea would be to implement (a slightly modified) useful Haskell
| function like this one:
|
| (defun foldl (fun id list)
| (if list
| (foldl fun
| (funcall fun (car list) id)
| (cdr list))
| id))
|
| (defun rvrs (list)
| (foldl #'cons nil list))

[SNIP]

| Of course, Common Lisp doesn't guarantee to be tail recursive, so for long
| lists you would use something like this:
|
| (defun rvrs (list)
| (loop for i in list
| with result = nil
| do (push i result)
| finally (return result)))
|
| And for sum you would just write (reduce #'+ list).

I hope you aren't forgetting REDUCE (with :FROM-END argument) _is_
FOLDL/FOLDR.

I think your definition of FOLDL could be written as

(defun foldl (fun id list)
(reduce (lambda (x y) (funcall fun y x)) list :initial-value id))

without worrying about tail recursion

I notice I sometimes do not want to use `FOLDL' or `FOLDR' explicitly
when I can just use the REDUCE expression: The rationale is the same as
using anonymous functions i.e. using a LAMBDA instead of naming that
abstraction.

--
Madhu