Получение минимального значения списка - PullRequest
Новая
       17

Получение минимального значения списка

1 голос
/ 08 ноября 2011

Я пытаюсь найти минимальное значение списка (как опыт обучения, поэтому без min).

Мой подход следующий: 

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

Это дает мне следующую ошибку:

Синтаксическая ошибка: ожидается оператор

Итак, мои вопросы:

  • Что вызывает синтаксическую ошибку?
  • Я попробую сам, как только исправлю, если он действительно вернет правильное значение, но будет ли это действительно правильным подходом?

Заранее спасибо.

Ответы [ 4 ]

4 голосов
/ 11 ноября 2011

В дополнение к другим опубликованным версиям рассмотрим также версию без if-then-else и с использованием более описательного имени для отношения (которое связывает список с его минимумом): 

list_min([L|Ls], Min) :- list_min(Ls, L, Min).

list_min([], Min, Min).
list_min([L|Ls], Min0, Min) :-
    Min1 is min(L, Min0),
    list_min(Ls, Min1, Min).

Такой шаблон называется fold (слева), и мы можем написать его эквивалентно, используя `foldl / 4: 

list_min([L|Ls], Min) :- foldl(min_, Ls, L, Min).

min_(A, B, Min) :- Min is min(A, B).

Пример запроса: 

?- list_min([1,0,2], Min).
Min = 0.

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

?- list_min([X,Y], 3).
<b>ERROR: is/2</b>: Arguments are not sufficiently instantiated

Чтобы сделать его истинным решением, используйте ограничений подобно и.Например, для решения свыше целых чисел : 

:- use_module(library(clpfd)).

list_min([L|Ls], Min) :- foldl(min_, Ls, L, Min).

min_(A, B, Min) :- Min #= min(A, B).

Это работает во всех направлениях: 

?- list_min([X,Y], 3).
X in 3..sup,
3#=min(Y, X),
Y in 3..sup.
4 голосов
/ 08 ноября 2011

В вашей программе есть несколько ошибок:

  1. , как указал Джо Леманн, '<='/2 нет.Это должно быть '=<'/2.

  2. , когда вы вызываете minimo/2 рекурсивно, вы строите списки неправильно.Вместо [Y,Tail] используйте [Y|Tail].В противном случае вы получите список со списком в качестве второго элемента.

  3. вы связываете второй аргумент рекурсивного вызова minimo/2 с Y или X.Вместо этого он должен быть связан с N.В противном случае ваш N никогда не будет создан.

Вы можете улучшить свою программу, добавив сокращения или используя if-then-else ('->' + ;): 

minimo([X], X) :- !.
minimo([X,Y|Tail], N):-
    ( X > Y ->
        minimo([Y|Tail], N)
    ;
        minimo([X|Tail], N)
    ).
3 голосов
/ 08 ноября 2011

Синтаксическая ошибка в том, что в Прологе меньше или равно = =, а не <=. </p>

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

Также я думаю, что вы хотите сделать что-то вроде [X | Tail] в рекурсии, а не [X, Tail]

2 голосов
/ 11 ноября 2011 
min([H|T], Min) :- min(T, H, Min).

min([], Min, Min).
min([H|T], Min, Min1) :-
  (   H < Min
  ->  min(T, H, Min1)
  ;   min(T, Min, Min1) ).
...