CODEWITHSUNDEEP
prolog
Jacek
Jacek

Reputation: 1088

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

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

Upvotes: 0

Views: 478

Answers (1)

lurker
lurker

Reputation: 58254

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).

As @false indicates in the comments, this in fact can be more clearly written using 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 ?-

Upvotes: 2

Related Questions