about returning min and max in an integer list
Author Message
about returning min and max in an integer list

Hi,

I am a beginner of Prolog.

Do you know how to write a function fn/3 such that fn(L,max,min) where L
is an integer list, min is the minimum value in L and max is the maximum
value in L?

Thanks! I have tried many times but failed.

Fri, 30 May 2003 17:14:49 GMT
about returning min and max in an integer list

Quote:

> Hi,

> I am a beginner of Prolog.

> Do you know how to write a function fn/3 such that fn(L,max,min) where L
> is an integer list, min is the minimum value in L and max is the maximum
> value in L?

> Thanks! I have tried many times but failed.

fori(I, I, I) :- !.
fori(A, A, _).
fori(I, A, B) :-
A < B,
A1 = A + 1,
fori(I, A1, B).

--
-- http://www.kaspy.z.pl ------
-- AGH - EAIiE - robotics -----

Fri, 30 May 2003 18:18:07 GMT
about returning min and max in an integer list

Quote:

> Hi,

> I am a beginner of Prolog.

> Do you know how to write a function fn/3 such that fn(L,max,min)
where L
> is an integer list, min is the minimum value in L and max is the
maximum
> value in L?

> Thanks! I have tried many times but failed.

There are three cases.

If the list is empty (Failure) since this fails we need not write a
clause for it.

If the List has one element then the min/ max is simpluy that element.

fn([X],X,X).

If the list has more than one element.

/* find the min/max of the Tail */
/* set the value of Min depending on Tail's min and

/* set the Value of Max depending on Tail's max and

the following 2 predicates may ve useful

min(X,Y,X) :- X < Y.
min(X,Y,Y) :- X >= Y.

max(X,Y,Z) :- min(Y,X,Z).

Sent via Deja.com http://www.deja.com/

Fri, 30 May 2003 18:20:14 GMT
about returning min and max in an integer list

Quote:

> Hi,

> I am a beginner of Prolog.

> Do you know how to write a function fn/3 such that fn(L,max,min) where L
> is an integer list, min is the minimum value in L and max is the maximum
> value in L?

fn([K|R],Min,Max) :-
fn1(R,K,K,Min,Max).

fn1([],Min,Max,Min,Max).
fn1([K|R],MinAkku,MaxAkku,Min,Max) :-
K > MaxAkku, !, fn1(R,MinAkku,K,Min,Max).
fn1([K|R],MinAkku,MaxAkku,Min,Max) :-
K < MinAkku, !, fn1(R,K,MaxAkku,Min,Max).
fn1([_|R],MinAkku,MaxAkku,Min,Max) :-
fn1(R,MinAkku,MaxAkku,Min,Max).

Regards,
Rainer

Fri, 30 May 2003 21:48:22 GMT
about returning min and max in an integer list

Quote:

> > Hi,

> > I am a beginner of Prolog.

> > Do you know how to write a function fn/3 such that fn(L,max,min) where L
> > is an integer list, min is the minimum value in L and max is the maximum
> > value in L?

> fn([K|R],Min,Max) :-
>   fn1(R,K,K,Min,Max).

> fn1([],Min,Max,Min,Max).
> fn1([K|R],MinAkku,MaxAkku,Min,Max) :-
>   K > MaxAkku, !, fn1(R,MinAkku,K,Min,Max).
> fn1([K|R],MinAkku,MaxAkku,Min,Max) :-
>   K < MinAkku, !, fn1(R,K,MaxAkku,Min,Max).
> fn1([_|R],MinAkku,MaxAkku,Min,Max) :-
>   fn1(R,MinAkku,MaxAkku,Min,Max).

> Regards,
> Rainer

That looks complicated!
I'll have to take your word for it that it actually works,
because I really can't tell by reading it.
Remember that the poor chap who asked the question is a beginner!

I'll try to find an answer that looks simpler.

Here's the question I want to prolog to be able to answer :

?- fn( [1,4,2,6,34,63,4], Max, Min ).
Max = 63
Min = 1
Yes

fn( List, Max, Min ) :-
findmax( List, 0, Max ),      % Find max.
findmin( List, 0, Min ).        % Find min.

findmax( [ ], M, M ).    % Let New_max = Max_so_far.

findmax( [H|R], Max_so_far, New_max ) :-
H =< Max_so_far,
% Find the max in the remainder of the list, R  :
findmax( R, Max_so_far, Max_in_remainder ),
New_max = Max_in_remainder.

findmax( [H|R], Max_so_far, New_max ) :-
H > Max_so_far,       % Redundant.
% Find the max in the remainder of the list :
findmax( R, H, Max_in_remainder ),
New_max = Max_in_remainder.

I haven't tested it,
but I think it will work.

How it works :
findmax goes through the list, one element at a time.
Max_so_far starts at 0, which is what it starts at
when called from "fn/3".
If the latest element it has reached, H, is greater
than Max_so_far then it searches the remainder of the list,
but using H as the number Max_so_far.
If H is not greater than Max_so_far,
then it searches the remainder of the list

When it reaches the end of the list,
the remaining list is "[ ]",
and it runs "findmax( [ ], M, M ).".
This makes it take the maximum number found so far,
the second parameter, and puts it in the third parameter.
It then returns to the command which called it,
which is normally "findmax".

I leave it to you to define "findmin",
which is just the same except that it uses ">=" and "<"

--
Martin Sondergaard,
London.

Tue, 03 Jun 2003 10:45:19 GMT
about returning min and max in an integer list

Quote:
>Hi,

>I am a beginner of Prolog.

>Do you know how to write a function fn/3 such that fn(L,max,min) where L
>is an integer list, min is the minimum value in L and max is the maximum
>value in L?

>Thanks! I have tried many times but failed.

Try the following, which is tail recursive and only traverses the list once:

% min_max_list(List, Min, Max) is true if Min is the minimum value in the
%   List, and Max is the maximum value.
min_max_list([X|Xs], Min, Max):-min_max_list_1(Xs, X, X, Min, Max).

min_max_list_1([], Min, Max, Min, Max).
min_max_list_1([X|Xs], OldMin, OldMax, Min, Max):-
min_max(X, OldMin, OldMax, NewMin, NewMax),
min_max_list_1(Xs, NewMin, NewMax, Min, Max).

min_max(X, Min, Max, X, Max):-X < Min, !.
min_max(X, Min, Max, Min, X):-X > Max, !.
min_max(_, Min, Max, Min, Max).

--
Colin

Tue, 03 Jun 2003 16:46:48 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages