Нахождение минимума массива в прологе

Question

Я пытался написать код, чтобы найти минимум массива (имеющий> 1 элемент) в Прологе.

min([H,T|[]], H) :- H < T.
min([H,T|[]], T) :- H >= T.
min([H|T], M) :- min(T, N), min([H|N], M).

Но когда я пытаюсь запустить его для:

min([1,2,3], K)

Переходит в рекурсию, где задействован один массив. Но мое первое утверждение - не допустить этого. Я предполагаю, что правила, определенные первыми, получат более высокий приоритет, когда пролог хочет их уменьшить.

Может ли кто-нибудь помочь мне с ошибкой?

Ссылка на код: https://swish.swi -prolog.org / p / min-array.pl

Answer 1

Легко увидеть ошибку, если идти шаг за шагом. Но вы, вероятно, уже пробовали это, поэтому я не буду пытаться повторить то, что вы уже сделали.

Но да, правила имеют приоритет, но нет, этот приоритет не таков, как вы думаете. Я очень стараюсь понять, что эти первые две строки делают в твоей голове, но это слишком сложно для меня. Но если вы просто запустите программу или отследите ее, вы сможете увидеть, что она делает на компьютере, и попытаться сравнить и сравнить с тем, что она делает в вашей голове.

Но для решения этой проблемы у вас должно быть два разных предиката, а не только один предикат.

Один предикат - получить минимум из двух вещей.

Второй предикат состоит в том, чтобы свести список к минимуму из множества вещей, применяя первый предикат к первому и второму, затем к минимуму мин первого и второго и третьего, вот так:

min([x0, x1, x2, ...) = min(min(min....(x0, x1), x2), ...)

Но первая минута не вторая минута. В Прологе первая минута - это арифметическая функция.

?- X is min(1, 2).
X = 1.

И min([1,2,3], X) будет успешным, если X is min(min(1, 2), 3). И, возможно, сбой, если нет.

Как написать min, чтобы сделать список в min(min(min(...)))? хороший вопрос Я нахожу в SWI очень хороший предикат foldl, поэтому я не уменьшаю себя, но вы можете написать сокращение, если не хотите уменьшать с помощью foldl.

min([H|T], Min) :- foldl(min, T, H, Min).
min(A, B, Min) :- Min is min(A, B).

Так много минут ... может быть, слишком много минут? Я не знаю. Вы должны лучше знать в своей голове, сколько минут слишком много минут. Может быть, слишком много в этом коде?