(Prolog) the first solution from the list that satisfies the goal

Question

I need to find the first element on the list which satisfies a user provided goal. I mean something like maplist/2 but which succeeds when the goal can be applied to at least one element. include/3 would be an option but I'm after a more optimal solution that can stop after finding the first element.

I think the interface could look like:

first(:Goal, List, First)

and it should be semidet in the SWI-Prolog sense.

It's fairly easy to code it but I'd prefer an existing rule. Is there a relevant rule in the "standard" libraries; I'm using SWI-Prolog.

Cheers, Jacek

I don't think there's a standard predicate that does this. But as you say, it would be very easy to code. I would probably write something like include_item(:Goal, List, Item) which succeeds for each Item in List that allows :Goal to succeed, then use once/1 on the call to include_item/3. In effect, a version of include/3 could be written as include(Goal, List, Items) :- findall(X, include_item(Goal, List, X), Items).. — lurker

lurker lurker · Accepted Answer · 2018-06-28T16:00:52

I don't think there's a standard predicate that does this. But as you say, it would be very easy to code. I would probably write something like this, which has a pattern like the member/2 predicate:

includes_item(Goal, [X|_], X) :-
    call(Goal, X).
includes_item(Goal, [_|T], X) :-
    includes_item(Goal, T, X).

member/2

includes_item(Goal, List, Item) :-
    member(Item, List),
    call(Goal, Item).

includes_item(:Goal, List, Item) succeeds for each Item in List that satisfies :Goal. For example:

3 ?- includes_item('>'(3), [1,2,3,-2, 4, 5], X).
X = 1 ;
X = 2 ;
X = -2 ;
false.

You can then use once/1 to obtain only the first item without a choice point:

first(Goal, List, Item) :-
    once(includes_item(Goal, List, Item)).

And now you get:

4 ?- first('>'(3), [1,2,3,-2, 4, 5], X).
X = 1.

5 ?-

(Prolog) the first solution from the list that satisfies the goal

1 Answers