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)
part at that), and would like to learn more.

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
                original head.

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?
hotline://twoaday.cjb.net/



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)
> part at that), and would like to learn more.

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)
> part at that), and would like to learn more.

> 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
>            original head.

> 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)
> part at that), and would like to learn more.
> 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  
 
 [ 5 post ] 

 Relevant Pages 

1. reversing lists within lists

2. Liked list question

3. Thoughts on a bytecode and reverse engineering code

4. Reverse Engineering Continued (Am I on the right track)

5. I am thinking about becoming a Head Hunter

6. I am thinking of if this is possible

7. How to reverse a list in gopher?

8. excess parens in reversed list

9. Excess Parentheses in Reversed List

10. Reverse a List?

11. Immutable list reverse function

12. Reverse a list??

 

 
Powered by phpBB® Forum Software