[Закрыть]
 
popoff.donetsk.ua
То, что происходит, происходит по определённым правилам из того, что было до него.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Статьи - Программирование - Технологии программирования - Флаги и оператор GOTO - Рекурсия и накапливающие аргументы
Я это делаю
Персональное меню
Голосование
Деньги, либо любимое занятие? Постоянный адрес этого вопроса
Деньги, но неинтересная работа и невозможность уделить время семье
Интересная работа, возможность саморазвиваться, но нищенский заработок
Ваш возраст (не обязательно)
Почему? (не обязательно)

Голосование закрыто.

Поиск по сайту
Реклама
Обмен электронных валют
money.dn.ua
Статистика

Рекурсия и накапливающие аргументы

Постоянный адрес статьи

Поиск минимума в списке (на Прологе) - как эту задачу решают в процедурных языках при помощи циклов и почему такой подход принципиально не подходит при использовании рекурсии.

Допустим, есть некоторый массив и нам нужно найти в нем минимум. Вот как решение этой задачи выглядит на языке Си:

int min(int *a,int n)
{
  int i;
  int r=32767;
  for(i=0;i<n;i++)
    if(a[i]<r) r=a[i];
  return r;
}

Если эту задачу нужно решить на Прологе, то ее часто решают так, как если бы ее решали, например, на языке Си или на любом другом языке при помощи цикла:

domains
  v=integer
  l=v*
predicates
  min(l,v,v)
clauses
  min([],M,M).
  min([H|T],MT,MR):-H>=MT,min(T,MT,MR).
  min([H|T],MT,MR):-H<MT,min(T,H,MR).

Первый аргумент - это список значений, среди которых ищется минимум. Второй аргумент - это «текущий минимум», который соответствует переменной r в программе на языке Си. Третий аргумент - это результат.

Первое утверждение предиката:

  min([],M,M).

означает: если список пуст, то вернуть в качестве результата текущий минимум. В программе на языке Си это соответствует строке:

  return r;

Второе утверждение предиката:

  min([H|T],MT,MR):-H>=MT,min(T,MT,MR).

означает: если первый элемент списка (H) больше либо равен текущему минимуму, то текущий минимум не изменяется

Третье утверждение предиката:

  min([H|T],MT,MR):-H<MT,min(T,H,MR).

означает: если первый элемент списка (H) меньше текущего минимума, то он становится текущим минимумом.

Вызов этого предиката выглядит так:

?-min([3,1,2],32767,X)

Очевидный недостаток этого способа - в том, что при вызове этого предиката требуется указать текущий максимум, который равен самому большому возможному числу. Для пользователя это выглядит примерно так, как для Вас выглядело бы вычисление корня квадратного от числа 16 в языке Си, если бы его надо было писать так:

a=sqrt(16,13.3243);

Константа 13.3243 имеет какое-то отношение к внутренней реализации этой функции, о котором известно только программисту, который создавал эту функцию.

Константа 32767 при вызове нашего предиката имеет примерно такой же смысл, как и эта константа 13.3243.

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

Однако приведенный Выше пример является в корне неправильным. В языке Пролог Вы используете рекурсивный предикат и применять к нему те рассуждения, которые Вы применяли при поиске минимума с помощью цикла нельзя. В приведенном выше варианте решения не используются возможности, предоставляемые рекурсией. Предикат должен быть сразу написан с использованием только двух аргументов - исходного списка и результата. При использовании рекурсии дополнительный аргумент, в котором Вы накапливали бы текущее значение минимума, не требуется.

Те люди, которые говорят, что такой вариант решения им более понятен, что избавившись от дополнительного аргумента программа станет менее ясной, скорее всего, просто не хотят развивать свое мышление. Они уже знают как эту задачу можно решить при помощи цикла. Когда их поставили в условия, что цикл использовать не возможно, они выкрутились, но решили задачу так, как если бы решали ее при помощи цикла. Эти люди не хотят напрягаться и размышлять над тем, как эту задачу можно было бы решить по-другому. То, что «понятно только так и никак по-другому», является оправданием к тому, чтобы не напрягаться.

А другое решение состоит в том, что при использовании рекурсии мы идем от общего к частному. Общее - это весь список. Частное - это текущий элемент и «все остальное» (хвост списка). Хвост списка - это список. У нас есть предикат, который ищет минимум в списке - это, собственно, тот предикат, который мы создаем. Зная минимум в хвосте и значение текущего элемента, мы можем найти минимум среди двух значений - это и будет результат.

domains
  v=integer
  l=v*
predicates
  min(l,v)
clauses
  min([H],H).
  min([H|T],M):-min(T,MT),MT<=H,M=MT.
  min([H|T],M):-min(T,MT),MT>H,M=H.

Первое утверждение нашего предиката:

  min([H],H).

означает, что если в списке один элемент, то этот элемент и является минимумом. Второе утверждение:

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

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

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

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

Вызов записывается так:

?-min([3,1,2],X)

В этом месте мне могут возразить, мол «Ну и что мы выиграли? Да, Вы избавились от лишнего аргумента, но теперь для каждого элемента списка минимум в хвосте вызывается два раза, когда в первом варианте он вычислялся только один раз. Ваш предикат не только менее понятный, но он еще и работает куда менее эффективно!»

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

Если бы мы программировали не на Прологе, а на каком-нибудь другом языке, то избавиться от этого недостатка нам помогла бы дополнительная функция, которая вычисляет минимум среди двух значений.

Избавиться от повторных вычислений в языке Пролог можно, применив механизм отсечений. Для упрощения я опущу раздел доменов и предикатов и запишу только раздел утверждений.

Если мы просто возьмем наш предикат, введем в него отсечение и удалим все лишнее, то получим следующее:

min([H],H).
min([H|T],M):-min(T,MT),MT<=H,!,M=MT.
min([H|_],M):-M=H.

В этом предикате, правда, теперь содержится маленькая неточность, которая приведет к тому, что на некоторых списках (думаю, Вам не составит труда найти, каких) этот предикат будет выдавать ответ два раза. Я не буду вдаваться в подробности, в связи с чем возникает этот эффект - Вы и сами можете это понять. Я лишь обращу Ваше внимание на несколько мест, в которых этот предикат можно было бы улучшить. Улучшив его, мы избавимся заодно и от этого эффекта.

А улучшить этот предикат можно было бы в двух местах.

Во-первых, в языке пролог оператор сравнения:

A=B

означает, что слева - такое же значение, как и справа. Использование переменных в языке Пролог:

min([H],H).

Означает то же самое: в первом месте - такое же значение, как и во всех остальных местах, в которых эта переменная используется.

Используя это свойство переменных и оператора сравнения, мы могли бы внести наше первое улучшение:

min([H],H).
min([H|T],MT):-min(T,MT),MT<=H,!.
min([H|_],H).

Второе улучшение мы можем найти, если внимательно посмотрим на первое и на третье утверждение нашего предиката. В частности, первый аргумент первого утверждения означает, что «список содержит в себе один элемент. Этот элемент равен H». Если рассмотреть список как такой, который разбивается на голову и хвост, то можно сказать, что голова этого списка - H, а хвост - это пустой список. Тогда первое утверждение предиката можно было бы записать так:

min([H|[]],H).

Теперь это утверждение похоже на третье. Отличие состоит в том, что в третьем утверждении хвост - это любой список, а в первом хвост - это пустой список. Понятно, что «пустой» - это частный случай «любой», именно поэтому первое утверждение можно просто удалить.

Окончательный вид нашего предиката для поиска минимума в списке будет таким:

min([H|T],MT):-min(T,MT),MT<=H,!.
min([H|_],H).

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


Юрий Попов, popoff.donetsk.ua

Смотрите также

Генерация перестановок в антилексикографическом порядке (на Си и на Прологе)
Количество отличий между циклами и рекурсией такое, что циклы вообще никак нельзя сравнивать с рекурсией. Это принципиально разные, не сравнимые между собой вещи.

Функциональное и логическое программирование Программирование в функциях и логическое программирование. Язык Лисп и язык Пролог. Черновики лекций и ссылки на ресурсы.

Последняя модификация: 25.12.06 15:14

Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>