Условие окончания поиска состоит в том, что кличка искомой лошади должна совпасть с Л. В этом случае поиск удачен и не требуется пробовать другие варианты. В противном случае мы должны использовать предикат меньше, определенный в гл. 3, чтобы определить, какую из «ветвей» дерева, М или Б, нужно рекурсивно просмотреть. Мы используем эти принципы при определении предиката искать, причем искать(Л,Т, Г) означает, что лошадь Л, если она найдена в таблице Т (которая организована в виде структуры формата в), выиграла Г гиней:
искать (Л, в(Л,Г,_,),Г):- !.
искать Л, в(Л1,_,До,_),Г):-меньше(Л,Л1),искать(Л,До,Г).
искать(Л, в(Л1,_,_,После),Г):- not (меньше(Л,Л1)), искать(Л,После,Г).
Если при поиске по упорядоченному дереву использовать этот предикат, то в общем случае проверок будет меньше, чем если бы их данные были организованы в виде простого списка и просматривались бы с начала до конца.
Предикат искать обладает одним интересным и удивительным свойством: когда вводим вопрос о лошади, клички которой нет в структуре, то любая информация, содержащаяся в вопросе, остается зафиксированной в этой структуре после окончания поиска. Иными словами, вопрос
?- искать(ruby_vintage,S,X).
имеет следующую интерпретацию: построить структуру в, в которой кличке ruby_vintageпоставлен в соответствие выигрыш X, и присвоить ее в качестве значения переменной S. Таким образом, искать осуществляет вставку новых компонент в частично заданную структуру. Поэтому многократно обратившись к искать, можно построить словарь. Например, вопрос
?- искать(abaris,X,582), искать(maloja,X,356).
привел бы к тому, что значение переменной X стало упорядоченным деревом из двух вхождений.
Понять то, каким образом искать одновременно выполняет и создание и выборку компонент, можно на основе тех знаний о Прологе, которыми вы уже располагаете; мы настоятельно рекомендуем разобраться в этом самостоятельно. Подсказка: если искать(Л,Т, Г) используется в конъюнкции целей, то «изменения» в структуре Т сохраняются только в области определения Т.
Упражнение 7.1. Поэкспериментируйте с предикатом искать, чтобы установить, какие различия будут в словаре, если элементы в него вставлять каждый раз в разном порядке. Например, как будет выглядеть дерево словаря, если вставлять его элементы в таком порядке: massinga, braemar nettleweed, panorama? А если в таком порядке: adela, braemar, nettleweed, massinga?
