Prolog: calculate index for a list of list

Question

I'm new to prolog. I want to implement a predict called high/3. This predict supports two scenarios: One is to return the index of one character in a list of list, for example:

high([[a,b,c],[d,e,f], [g,h]], b, X) returns X = 1
high([[a,b,c],[d,e,f], [g,h]], f, X) returns X = 2

The second scenario is if you provide an index, it should also return all characters at that index position.
e.g.

high([[a,b,c],[d,e,f], [g,h]], X, 1) returns X = b; X= e; X= h
high([[a,b,c],[d,e,f], [g,h]], X, 2) returns X = c; X= f.

I wrote the following predirect:

high([[X|_]|L], X, 0).
high([[Head|Tail]|L], X, H):- member(X, Tail), high([Tail|L], X, H1),H is H1 + 1.
high([[Head|Tail]|L], X, H):- not(member(X, Tail)), high(L, X, H).

This predict only works for the first scenario, but it doesn't work properly for the second scenario.

If I run high([[a,b,c],[d,e,f], [g,h]], X, 1), it only returns X = b, but I expect it returns b, e, h there one by one.

Why does it return only b and fail?

Answer 1

It's a bit unclear what it should do in cases where there are identical elements in different lists. Nevertheless, here's my solution using library(clpfd):

:- use_module(library(clpfd)).

high([H|_], X, I) :-
    high_(H, X, I, 0).
high([_|T], X, I) :-
    high(T, X, I).

high_([X|_], X, I, I).
high_([_|T], X, I, J) :-
    J #>= 0,
    J #=< I,
    J1 #= J + 1,
    high_(T, X, I, J1).

This has the following behaviour:

?- high([[a,b,c],[d,e,f],[g,h]], b, I).
I = 1 ;
false.

?- high([[a,b,c],[d,e,f],[g,h]], f, I).
I = 2 ;
false.

?- high([[a,b,c],[d,e,f],[g,h]], X, 1).
X = b ;
X = e ;
X = h ;
false.

?- high([[a,b,c],[d,e,f],[g,h]], X, 2).
X = c ;
X = f ;
false.

But also works when there are duplicates:

?- high([[a,a],[b,a]], a, X).
X = 0 ;
X = 1 ;
X = 1 ;
false.

With unknown sublists:

?- high([A,B], X, 2).
A = [_4552, _4558, X|_4566] ;
B = [_4552, _4558, X|_4566] ;
false.

With an unknown list of lists:

?- high(L, X, 2).
L = [[_4518, _4524, X|_4532]|_4514] ;
L = [_4512, [_4524, _4530, X|_4538]|_4520] ;
L = [_4512, _4518, [_4530, _4536, X|_4544]|_4526] ;
…

Answer 2

It only returns one result because not(member(X, Tail)) will never be true as long as X hasn't been unified with anything (and Tail is not empty). In other words, since the second clause succeeds, the third one cannot and the recursion does not continue to handle the following lists.

However, I'd say you're going about this the wrong way. Your current code will also give wrong output if an element is present in multiple sublists.

You can break down your problem into smaller parts: you need to be able to relate and element to its index inside a single, simple list; and you need to be able to evaluate this for all sublists in your total list.

First things first: relate and element to its index:

index([X|_], X, 0).
index([_|T], X, I) :- index(T, X, I2), I is I2 + 1.

Very simple and easy to understand, right?

Now to recurse through all lists and match all elements/indices in them:

high([H|_], X, I) :- index(H, X, I).
high([_|T], X, I) :- high(T, X, I).

This will give all the expected outputs:

?- high([[a,b,c],[d,e,f], [g,h]], b, X)
X = 1;
false.

?- high([[a,b,c],[d,e,f], [g,h]], f, X)
X = 2;
false.

high([[a,b,c],[d,e,f], [g,h]], X, 1).
X = b;
X = e;
X = h;
false.

high([[a,b,c],[d,e,f], [g,h]], X, 2).
X = c;
X = f;
false.