From: student <no-s...@sonic.net>
User-Agent: Mozilla/5.0 (X11; U; Linux i586; en-US; rv:1.7.3) Gecko/20040913
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: comp.lang.prolog
Subject: Re: Prolog newbie trying to write nth-member
References: <87zn0bfjml.fsf@ileriseviye.org>
In-Reply-To: <87zn0bfjml.fsf@ileriseviye.org>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 120
Message-ID: <kXbxd.13197$_3.148757@typhoon.sonic.net>
Date: Sun, 19 Dec 2004 09:35:12 GMT
NNTP-Posting-Host: 209.148.113.61
X-Complaints-To: a...@sonic.net
X-Trace: typhoon.sonic.net 1103448912 209.148.113.61 (Sun, 19 Dec 2004 01:35:12 PST)
NNTP-Posting-Date: Sun, 19 Dec 2004 01:35:12 PST

Emre Sevinc wrote:
> Hello,
> 
> I keep on practicing and trying to understand
> Prolog using (Bratko, 2001). In his book, Chapter 4,
> he wants the reader to implement a family relationship,
> namely nth_child and in order to do that I need a
> basic procedure nth_member which is:
> 
>  nth_member(N, List, X) returns true if X is the nth member
>                         of the list.
> 
> Now I try to think recursively, the Prolog way,
> but I'm just stuck. (I know there are nth0/3 and nth1/3 procedures
> but I need to do it by myself in order to have
> a solid grasp of the subject).
> 
> Here's my thinking aloud to write nth_member(N, List, X):
> 
>  Let's have a Counter, its initial value is 1
>  if Element is the first element of the list,
>  namely [Element | Tail] and N =:= Counter then it is OK,
> 
>  otherwise
>  Counter is Counter + 1
>  if Element is the first element of the remaining
>  part, namely [Tail | Rest] and Tail = Element 
>  and N =:= Counter then it is OK.
> 
> 
> I have trouble mapping my thinking into Prolog language,
> I try to write something like that:
> 
> nth_member(N, [], Element) :- N = 0.  % is this OK as a terminating condition?
> 
> nth_member(N, [Head | Tail], Element) :-
>         Counter is 1       
>         Head = Element,
>         N =:= Counter             % ok, if everything's fine finish ???
>                                   % otherwise I must continue but how?
>         Counter is Counter + 1 
>         nth_member(N1, [Tail | Tail2], Element),  % will this lead to infinity?
>         N is N1 + 1.
> 
> 
> How should I code that "otherwis"e part in a recursive manner
> without leading to infinity, stack overflow, etc.? 
> 
> I'll be very glad if Prolog experts here can enlighten
> me and show me if (and how) my thinking is flawed, how
> can I map it into Prolog.
> 
> Thanks in advance,
> 

  I am no expert, but I know that because I came to Prolog after
working many years as a Fortran programmer, I was very much
inclined to thinking i.t.o.  function definitions -- i.e.,
stepwise-imperative procedures that "returned" a single value
-- when I began, rather than just describing things and
letting the Prolog Inference Engine do the heavy lifting, so
to speak.

  I find that if I start with an informal definition of the
predicate that I have in mind, I am somewhat less likely to
immediately try to force my thinking into the functional
programming mold.

  For example, in the present case, I might start by saying

    Let nth(X,List,N) <=> term X is the first member of List and N is 1
or X is the Mth member of the tail of List and N is M + 1.

  That is, using pseudo-Prolog, and successor arithmetic,

    nth(X,List,N) if List is of the form [X|_] and N is s(zero)

and

    nth(X,List,N) if List is of the form [_|RemList] and 
					  
                                          nth(X,RemList,M) and N is s(M).
  
  Interpreting the phrase "is of the form" as predicate
language, I get

    nth(X,[X|_],s(zero)).

and

    nth(X,[_|L],s(M)) :- nth(X,L,M)

which is already Prolog, but is not restricted to only getting
the Nth member of a given list.

That is,
*/

?- nth(X,[a,b,c,d,d,e,f,g],s(s(s(zero)))).

X = c ;

No

/*
but also
*/

?- nth(d,[a,b,c,d,d,e,f,g],N).

N = s(s(s(s(zero)))) ;

N = s(s(s(s(s(zero))))) ;

No


--
billh