Пролог Список Поиск

Question

Я пытаюсь определить предикат, где он ищет в списке списков элемент и возвращает уровень этого элемента. Например, при поиске элемента:

?- elementLevel(element,[a,b,c,[d,e],[element,f]],Level).
Level = 2 .

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

Answer 1

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

Вам понадобится один факт и три правила.

Факт игнорирует элемент (то есть использует _), объединяет список с пустым списком и говорит, что возвращаемый уровень равен -1 (не найден).

Первым и вторым правилом будет поиск по списку «учебник», объединяющий элемент с заголовком списка и возвращающий уровень 1; другое правило игнорирует голову и возвращает уровень элемента в хвосте.

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

Answer 2

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

% Base recursion / element found
elementLevel(element, element, 0).

% Any list with head and tail
elementLevel(element, [H|T], NestLevel) :-

    % Increment counter if H is a list/process possible sublists
    (is_list(H) ->
      elementLevel(element, H, NewLevel),
      elementLevel(element, T, NewLevel),
      NestLevel is NewLevel + 1  
    ;

    % No increments, just recurse through items
    elementLevel(element, H, NestLevel),
    elementLevel(element, T, NestLevel)
    ).

% Prevent empty sublists from causing a fail
elementLevel(element, _, _).

Answer 3

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

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

tree_walk( X , Tree , Depth ) :-
  tree_walk( X , Tree , 0 , Depth ) % seed the accumulator with an initial depth
  .

Тогда вам нужен предикат работника:

tree_walk( X , [ X |  _ ] , D , D )    % success! if the desired item is found
  .                                    %
tree_walk( X , [ Y | Ys ] , T , D ) :- % otherwise...
  T1 is T+1 ,                          % - increment the depth
  tree_walk( X , Y , T1 , D )          % - and recurse down on the head of the list
  .                                    %
tree_walk( X , [ _ | Ys ] , T , D ) :- % if that failed, then
  tree_walk( X , Ys , T , D )          % - recursively search the tail of the list 
  .                                    %

Вот и все, что нужно.

ПРИМЕЧАНИЯ

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

• , если X не связан или один из элементов в «списке списков» не связан, вы, вероятно, столкнетесь ... с интересными проблемами. Что касается производственного кода, вы бы хотели установить защитные устройства для правильной работы с этими крайними случаями.

Ура!

Answer 4

вы можете определить такой предикат для реализации счетчика.

go:-  
ListLevel=0,  
NumberTobeFound=5,
go(List,NumberTobeFound,ItsLevel),  
write("Level",ItsLevel).

go([Head|Tail],NumberTobeFound,ItsLevel):-  
Head>NumberTobeFound,  
NewItsLevel=ItsLevel+1,  
go(Tail,NumberTobeFound,NewItsLevel).


go([Head|Tail],NumberTobeFound,ItsLevel):-  
Head<NumberTobeFound,  
NewItsLevel=ItsLevel+1,  
go(Tail,NumberTobeFound,NewItsLevel).

go([Head|Tail],NumberTobeFound,ItsLevel):-  
write("Number Found.."),  
write("Its Level is : ",ItsLevel).