Поймите простую рекурсию в прологе

Question

У меня есть следующий Пролог из книги, посвященной Прологу, и я пытаюсь узнать простую рекурсию.

mins_to_hours(In, H, M):- 
    In<60, 
    H = 0, 
    M is In. 
mins_to_hours(In, H, M):- 
    In>=60, 
    In1 is In-60, 
    H1 is H+1, 
    mins_to_hours(In1, H1, M). 

Я не совсем уверен, почему это не работает, и я часами занимаюсь этим. Любая помощь даже указать мне в правильном направлении очень ценится. Заранее спасибо.

Answer 1

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

 
?- mins_to_hours(In, H, M). 
ERROR: Arguments are not sufficiently instantiated 

Чтобы избавиться от этого недостатка, я первый заменить предикаты низкого уровня с CLP (FD) ограничения, которые доступны во всех основных системах Prolog и упрощают анализ вашего кода.

Для этого, я просто заменить (<)/2 на (#<)/2, (is)/2 по (#=)/2 и т.д. (в зависимости от системы Prolog, вы можете все равно придется импортировать библиотеку для этого):

 
mins_to_hours(In, H, M):- 
    In #< 60, 
    H = 0, 
    M #= In. 
mins_to_hours(In, H, M):- 
    In #>= 60, 
    In1 #= In-60, 
    H1 #= H+1, 
    mins_to_hours(In1, H1, M). 

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

 
?- mins_to_hours(In, H, M). 
In = M, 
H = 0, 
M in inf..59 ; 
H = -1, 
In in 60..119, 
M+60#=In, 
M in 0..59 ; 
H = -2, 
In in 120..179, 
_5238+60#=In, 
_5238 in 60..119, 
M+60#=_5238, 
M in 0..59 . 

Здесь, мне кажется очень странным, что H может принять отрицательный значения!

Попытаемся несколько конкретных случаев:

 
?- mins_to_hours(30, H, M). 
H = 0, 
M = 30 ; 
false. 

Это все еще кажется вполне нормально!

 
?- mins_to_hours(60, H, M). 
H = -1, 
M = 0 ; 
false. 

Это уже, кажется, гораздо меньше OK!

С некоторой практикой легко понять причину: во втором предложении вы непреднамеренно запутываете роли H и H1! Предположим, что мы пишем второе предложение следующим образом:

 
mins_to_hours(In, H, M):- 
    In #>= 60, 
    In1 #= In-60, 
    H #= H1+1, 
    mins_to_hours(In1, H1, M). 

Тогда мы получим:

 
?- mins_to_hours(60, H, M). 
H = 1, 
M = 0 ; 
false. 

и для более двух случаев:

 
?- mins_to_hours(500, H, M). 
H = 8, 
M = 20 ; 
false. 

?- mins_to_hours(1000, H, M). 
H = 16, 
M = 40 ; 
false. 

Кажется довольно хорошо!

Обратите внимание, что если вы будете придерживаться более низкого уровня арифметики, вы не можете это легко исправить ошибку: Использование предиката как (<)/2 и (is)/2 требует, чтобы вы также принимать во внимание фактического порядка исполнения Пролога, и это слишком трудно для почти всех новичков.Я настоятельно рекомендую вам использовать ограничения CLP (FD), так как они позволяют вам легко попробовать эффект разных целевых ордеров, сохраняя при этом правильное отношение и общий.