Reversing a list, I thought it was like this, but...
Author Message
Reversing a list, I thought it was like this, but...

Wondering if someone could point out the problem in the following.  I'm pretty
new to Prolog, only took it as part of a course (a very minor (read ~2 weeks)

I'd like to reverse a list:

reverse([1,2,3], X).

Would yield:

X = [3,2,1].

I thought the following would work:

reverse([],[]).
reverse([H|T],X) :- reverse(T,TR),append(TR,H,X).

Where the append funciton is defined as:

append(<list1>,<list2>,<list3>): - <list3> = <list1> + <list2>.

My logic was as follows:

Base case: the empty list reversed is the empty list.
Recursive case: Reverse the tail of the given list, and create a new
list via append which consists of the reversed tail, plus the

The code works on the empty list:

reverse([],X).

And on a list of one element:

reverse([1],X).

But crashes with a 'no' with anything else.

Any ideas?

Thanks,
Patrick

--

http://www.*-*-*.com/
Like anime?   Got hotline?

Tue, 01 Jun 2004 11:50:18 GMT
Reversing a list, I thought it was like this, but...

Quote:

> Wondering if someone could point out the problem in the following.  I'm pretty
> new to Prolog, only took it as part of a course (a very minor (read ~2 weeks)

You should consider getting a book. reverse/2 is basic stuff.

Quote:
> I'd like to reverse a list: [...]
> I thought the following would work:
>    reverse([],[]).
>    reverse([H|T],X) :- reverse(T,TR),append(TR,H,X).
> [...]
> Any ideas?

`H' is an element but append wants a list, so it should be:

| reverse([],[]).
| reverse([H|T],X) :- reverse(T,TR),append(TR,[H],X).

/Tomas

Tue, 01 Jun 2004 15:06:59 GMT
Reversing a list, I thought it was like this, but...
Give this a shot:
------------------------
reverse(List,RevList):-
rev(List,[],RevList).

rev([H|T],S,R):-
rev(T,[H|S],R).
rev([],R,R).
------------------------
Collected from: http://kti.ms.mff.cuni.cz/~bartak/prolog.old/samples.html
===========================================================================
later!
Greg
========

Quote:

> Wondering if someone could point out the problem in the following.  I'm pretty
> new to Prolog, only took it as part of a course (a very minor (read ~2 weeks)

> I'd like to reverse a list:

>    reverse([1,2,3], X).

> Would yield:

>    X = [3,2,1].

> I thought the following would work:

>    reverse([],[]).
>    reverse([H|T],X) :- reverse(T,TR),append(TR,H,X).

> Where the append funciton is defined as:

>    append(<list1>,<list2>,<list3>): - <list3> = <list1> + <list2>.

> My logic was as follows:

>    Base case: the empty list reversed is the empty list.
>    Recursive case: Reverse the tail of the given list, and create a new
>            list via append which consists of the reversed tail, plus the

> The code works on the empty list:

>    reverse([],X).

> And on a list of one element:

>    reverse([1],X).

> But crashes with a 'no' with anything else.

> Any ideas?

> Thanks,
> Patrick

Tue, 01 Jun 2004 16:37:53 GMT
Reversing a list, I thought it was like this, but...

Quote:

> Wondering if someone could point out the problem in the following.  I'm pretty
> new to Prolog, only took it as part of a course (a very minor (read ~2 weeks)
> I'd like to reverse a list:
>    reverse([1,2,3], X).
> Would yield:
>    X = [3,2,1].
> I thought the following would work:
>    reverse([],[]).
>    reverse([H|T],X) :- reverse(T,TR),append(TR,H,X).

almost right. Note that H is an element, not (neccesarily) a list.
Thus in order to append it, you want to append the list [H].

of course, this definition of reverse is known as 'naive' for its
inefficiency. In a few weeks from now, try to define a better version
of reverse which runs in linear time.

Gj

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord

Tue, 01 Jun 2004 16:56:08 GMT
Reversing a list, I thought it was like this, but...

Quote:
> of course, this definition of reverse is known as 'naive' for its
> inefficiency. In a few weeks from now, try to define a better version
> of reverse which runs in linear time.

if you look  on the source code of GNU Prolog, you will find the file
.../gprolog-1.2.8/src/BipsPl/list.pl

And into this file you get definitions of lists predicates

Reverse definition of GNU prolog :

reverse([], []).

reverse([H|T], L) :-
'\$reverse1'(T, L, [H]).

'\$reverse1'([], L, L).

'\$reverse1'([H|T], L, L1) :-
'\$reverse1'(T, L, [H|L1]).

Jean Michel LECONTE

ps : for your idea you have to write :

reverse([],[]).
reverse([H|T],X) :- reverse(T,TR),append(TR,[H],X). % here H is the head
of a list but isnt a list !

Wed, 02 Jun 2004 05:54:16 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages