CODEWITHSUNDEEP
prolog
MOSCODE
MOSCODE

Reputation: 292

Find the minimum in a mixed list in Prolog

I am new to prolog, I am just learning about lists and I came across this question. The answer works perfect for a list of integers. 

minimo([X], X) :- !.
minimo([X,Y|Tail], N):-
    ( X > Y ->
        minimo([Y|Tail], N)
    ;
        minimo([X|Tail], N)
    ).

How can I change this code to get the smallest int from a mixed list?

This 

sint([a,b,3,2,1],S)

should give an answer:

S=1

Upvotes: 1

Views: 124

Answers (3)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477854

First of all, I don't think the proposed implementation is very elegant: here they pass the minimum found element thus far by constructing a new list each time. Using an additional parameter (we call an accumulator) is usually the way to go (and is probably more efficient as well).

In order to solve the problem, we first have to find an integer. We can do this like:

sint([H|T],R) :-
    integer(H),
    !,
    sint(T,H,R).
sint([_|T],R) :-
    sint(T,R).

So here we check if the head H is an integer/1. If that is the case, we call a predicate sint/3 (not to be confused with sint/2). Otherwise we call recursively sint/2 with the tail T of the list.

Now we still need to define sint/3. In case we have reached the end of the list [], we simply return the minum found thus far:

sint([],R,R).

Otherwise there are two cases:

  • the head H is an integer and smaller than the element found thus far, in that case we perform recursion with the head as new current minimum:

    sint([H|T],M,R):
    integer(H),
    H < M,
    !,
    sint(T,H,R).

  • otherwise, we simply ignore the head, and perform recursion with the tail T.

    sint([_|T],M,R) :-
    sint(T,M,R).

We can put the recursive clauses in an if-then-else structure. Together with the earlier defined predicate, the full program then is:

sint([H|T],R) :-
    integer(H),
    !,
    sint(T,H,R).
sint([_|T],R) :-
    sint(T,R).

sint([],R,R).
sint([H|T],M,R):
    (
     (integer(H),H < M)
     -> sint(T,H,R)
     ;  sint(T,M,R)
    ).

The advantage of this approach is that filtering and comparing (to obtain the minimum) is done at the same time, so we only iterate once over the list. This will usually result in a performance boost since the "control structures" are only executed once: more is done in an iteration, but we only iterate once.

We can generalize the approach by making the filter generic:

filter_minimum(Filter,[H|T],R) :-
    Goal =.. [Filter,H],
    call(Goal),
    !,
    filter_minimum(Filter,T,H,R).
filter_minimum(Filter,[_|T],R) :-
    filter_minimum(Filter,T,R).

filter_minimum(_,[],R,R).
filter_minimum(Filter,[H|T],M,R) :-
    Goal =.. [Filter,H],
    (
     (call(Goal),H < M)
     -> filter_minimum(Filter,T,H,R)
     ;  filter_minimum(Filter,T,M,R)
    ).

You can then call it with:

filter_minimum(integer,[a,b,3,2,1],R).

to filter with integer/1 and calculate the minimum.

Upvotes: 1

coder
coder

Reputation: 12992

You could just write a predicate that returns a list with the numbers and the use the above minimo/2 predicate:

only_numbers([],[]).
only_numbers([H|T],[H|T1]):-integer(H),only_numbers(T,T1).
only_numbers([H|T],L):- \+integer(H),only_numbers(T,L).

sint(L,S):-only_numbers(L,L1),minimo(L1,S).

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

you could just ignore the problem, changing the comparison operator (>)/2 (a binary builtin predicate, actually) to the more general (@>)/2:

minimo([X], X) :- !.
minimo([X,Y|Tail], N):-
    ( X @> Y ->
        minimo([Y|Tail], N)
    ;
        minimo([X|Tail], N)
    ).

?- minimo([a,b,3,2,1],S).
S = 1.

Upvotes: 2

Related Questions