🚀 go-pugleaf

In article <1992Apr7.172958.5219@ugle.unit.no>, baustad@idt.unit.no (Jostein Baustad) writes:
> I have a Prolog-predicate that gives me the n'th element of a list:

> % list_index(List,Index,Element)
> 
> list_index([Head|_],1,Head).
> list_index([_|Tail],Index,Elt) :-
> 	Index>1,
> 	NewIndex is Index-1,
> 	list_index(Tail,NewIndex,Elt).

You would be making life easier for yourself if you adopted an argument
order convention that was consistent with the Prolog evaluabale predicates
and other library predicates.  arg/3 sets the pattern: index precedes
collection precedes element.  It is good that the order of the parts of
the symbol of your predicate name matches the order of the arguments, so
I'll swap the parts to preserve that property:
	index_list(Index, List, Element)
would be easier to remember.  The Quintus library has two such predicates:

	nth0(Index, List, Element)	-- 0 origin
	nth1(Index, List, Element)	-- 1 origin

The code you have is logically determinate:  a number cannot both
satisfy Index > 1 and Index = 1.  However, many Prolog compilers work
a clause at a time (for example, BinProlog) and won't realise this.
So your code would be more efficient as

	index_list(Index, List, Element) :-
		integer(Index),
		Index > 0,
		index_list_loop(Index, List, Element).

	index_list_loop(1, [Head|_], Element) :- !,
		Element = Head.
	index_list_loop(N, [_|Tail], Element) :-
		M is N - 1,
		index_list_loop(M, Tail, Element).

(Sometimes I wonder whether Prolog is a high-level language, I really do.)

> This works fine for finding the element when the list and the Index are known
> (instantiated), but I also want to use the same predicate to find the index
> (that is the first one) when the list and the element are known.

As soon as you say "the index (that is the first one)" you are departing
from pure logic.  It would be better to have

	index_list(Index, List, Element)
	is true when Element is the Indexth element of List

with behaviour as close as possible to the logical specification, and
a separate predicate

	first_index_list(Index, List, Element) :-
		index_list(Index, List, Element),
		!.

> My predicate
> doesn't work because of the 'is'-operator. Of course, I can use two different
> predicates, but I have a feeling that it is possible with only one predicate
> and some fine Prolog-code. Any suggestions anyone? Thanks in advance.

If you use 0-origin, it _is_ possible with only one predicate and some
"cute" Prolog code.  ("Cute" is actually a pejorative in my idiolect.)

	nth0(Index, List, Element) :-
		length(Prefix, Index),
		append(Prefix, [Element|_], List).

To get 1-origin, we have to subtract one from the Prefix:

	nth1(Index, List, Element) :-
		length([_|Prefix], Index),
		append(Prefix, [Element|_], List).

Now, I really don't want to advocate these definitions.  (The predicates
in the Quintus library have the same _interface_ but different implementation.)
What I do want to point out is that it is often a very good idea to use lists
as counters.  In many cases you _have_ a suitable list.  If you represent
the natural number N by a list with N elements (just which elements doesn't
matter), you can write

	list_nth1([_|N], List, Element) :-
		list_nth0(N, List, Element).

	list_nth0(N, List, Element) :-
		same_length(N, Prefix),
		append(Prefix, [Element|_], List).

We can take the last specification and unfold it, getting

	list_nth0([], [Element|_], Element).
	list_nth0([_|N], [_|List], Element) :-
		list_nth0(N, List, Element).

It would be nice if we could attach some sort of meaning to
first_list_nth1/3; if it only finds the first occurrence of Element
when it is solving for Count, it should only succeed for the first
occurrence of any Element.  So we'll explicitly check that.

	%   first_list_nth0(Count, List, Element)
	%   is true when list_nth0(Count, List, Element) and this
	%   is the first occurrence of Element in List.

	first_list_nth0(Count, List, Element) :-
		list_nth0(Count, List, Element),
		notbefore(Count, List, Element),
		!.

	notbefore([], _, _).
	notbefore([_|N], [Head|Tail], Element) :-
		Head \= Element,	% should be ~=
		notbefore(N, Tail, Element).




So here is my actual recommendation if you want really pretty well-behaved
list indexing:

	list_nth0([], [Element|_], Element).
	list_nth0([_|N], [_|List], Element) :-
		list_nth0(N, List, Element).


	list_nth1([_|N], List, Element) :-
		list_nth(N, List, Element).

	first_list_nth0(N, List, Element) :-
		list_nth0(N, List, Element),
		notbefore(N, List, Element),
		!.

	first_list_nth1([_|N], List, Element) :-
		list_nth0(N, List, Element),
		notbefore(N, List, Element),
		!.

	notbefore([], _, _).
	notbefore([_|N], [Head|Tail], Element) :-
		Head \= Element,	% should be ~=
		notbefore(N, Tail, Element).

If you haven't got a list of a suitable length, you could use some other
data structure that you happen to have, such as s(s(s(0))) to represent 3.
If you really do have/need integers, things get messy.  The basic problem
is that we can't use pattern matching to construct/decompose integers.  A
smart compiler could of course do something about that (hint hint).

Basically, your code will look like

	index_list(Index, List, Element) :-
	    (	var(Index) ->
		index_list_loop(Element, List, 1, Index)
	    ;   integer(Index) ->
		Index >= 1,
		index_list_loop(Index, List, Element)
	    ;/* report a "type failure" in argument 1 of index_list/3
	    ).

This can be space- and time- efficient, but it certainly isn't pretty.
It's ok to have ugly code inside something as long as it has a clean
interface.
-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au