Prolog - Problem with code to find element in list

Author

Problem with code to find element in list - instantiation

none

2006-06-26, 7:04 pm

Hello, I'm trying to write a predicate that will allow to get a value a
given List position.

example:

value([a,b,c],3,R).

would say R = c.

This works properly with the following code:

value([], _, 'no element').
value([First|Rest], 0, First).
value([First|Rest, Position, Value) :-
First \== Value,
Position >= 0,
Position2 is Position -1,
value(Rest, Position2, Value).

However the code doesn't work the other way around. For example:

value([a,b,c],X,c).

doesn't give X = 3
and outputs an error saying that

! Instantiation error in argument 1 of >= /2
! goal: _81>=0

wich makes sense since the compiler doesn't know the value of Position
so it can calculate if it's >= 0.

Any ideias on howto solve this?

Thanks.

Jussi Piitulainen

2006-06-26, 7:04 pm

none writes:

> Hello, I'm trying to write a predicate that will allow to get a
> value a given List position.
>
> example:
>
> value([a,b,c],3,R).
>
> would say R = c.
>
> This works properly with the following code:

Not quite. This will find elements in an empty list, and will fail to
find duplicate elements at a position after their first occurrence.
Remove a clause and a call. (I don't think (\==)/2 is the right
predicate here, but since the whole call is to go, never mind now.)

> value([], _, 'no element').
> value([First|Rest], 0, First).
> value([First|Rest, Position, Value) :-
> First \== Value,
> Position >= 0,
> Position2 is Position -1,
> value(Rest, Position2, Value).
>
> However the code doesn't work the other way around. For example:

Good thinking.

> value([a,b,c],X,c).
>
> doesn't give X = 3
> and outputs an error saying that
>
> ! Instantiation error in argument 1 of >= /2
> ! goal: _81>=0
>
> wich makes sense since the compiler doesn't know the value of Position
> so it can calculate if it's >= 0.
>
> Any ideias on howto solve this?

Implement the other mode separately and branch on the instantiation
state of Position. Calling your present implementation find_value/3,
write find_position/3 and have value/3 only check which of them to
use:

value(List, Position, Value) :-
(
var(Position)
->
find_position(List, Value, Position)
;
find_value(List, Position, Value
).

Note that find_value/3 will succeed at most once, while
find_position/3 should be able to succeed any number of times,
assuming that value(L,P,V) means that L has V at position P.

Peter Van Weert

2006-06-26, 7:04 pm

The following code does the trick (more or less):

value([First|_], 0, First).
value([_|Rest], Pos, Value) :-
value(Rest, Pos1, Value),
Pos is Pos1+1.

Not exactly what you wrote though, as it does not bind the third
argument to 'no element' if given an incorrect position, but fails
instead. Seemed like a better solution to me, shouldn't be to hard to
adapt...

Btw, there should be a built-in predicate that does this. E.g. in
Sicstus Prolog this is nth/3, in SWI Prolog nth0/3 or nth1/3, etc

Greets,
Peter

none schreef:
> Hello, I'm trying to write a predicate that will allow to get a value a
> given List position.
>
> example:
>
> value([a,b,c],3,R).
>
> would say R = c.
>
> This works properly with the following code:
>
> value([], _, 'no element').
> value([First|Rest], 0, First).
> value([First|Rest, Position, Value) :-
> First \== Value,
> Position >= 0,
> Position2 is Position -1,
> value(Rest, Position2, Value).
>
> However the code doesn't work the other way around. For example:
>
> value([a,b,c],X,c).
>
> doesn't give X = 3
> and outputs an error saying that
>
> ! Instantiation error in argument 1 of >= /2
> ! goal: _81>=0
>
> wich makes sense since the compiler doesn't know the value of Position
> so it can calculate if it's >= 0.
>
> Any ideias on howto solve this?
>
> Thanks.

Bill Spight

2006-06-26, 7:04 pm

Dear none,

> Hello, I'm trying to write a predicate that will allow to get a value a
> given List position.
>
> example:
>
> value([a,b,c],3,R).
>
> would say R = c.
>
> This works properly with the following code:
>
> value([], _, 'no element').

This is incorrect. The list is empty. You are saying that it has an
element, 'no element'.

> value([First|Rest], 0, First).

This is incorrect.

value([First|_], 1, First).

is correct.

> value([First|Rest, Position, Value) :-
> First \== Value,

Who cares?

> Position >= 0,

Position > 1,

> Position2 is Position -1,
> value(Rest, Position2, Value).
>
> However the code doesn't work the other way around. For example:
>
> value([a,b,c],X,c).
>
> doesn't give X = 3
> and outputs an error saying that
>
> ! Instantiation error in argument 1 of >= /2
> ! goal: _81>=0
>
> wich makes sense since the compiler doesn't know the value of Position
> so it can calculate if it's >= 0.
>
> Any ideias on howto solve this?
>

How about changing your representation of a natural number? For instance,
represent the natural number, N, as a list of length, N. Then we might get
something like this.

value([First|_], [_], First).
value([_|Rest], Position, Value) :-
Position = [_|Position2],
value(Rest, Position2, Value).

Another idea is to use an accumulator. E. g.,

value(List, Index, Element) :-
value(List, 1, Index, Element).

value([First|_], Index, Index, First).
value([_|Rest], I0, Index, Element) :-
I is I0 + 1,
value(Rest, I, Index, Element).

Best,

Bill

Sponsored Links