프롤로그 목록 검색

Question

필자는 요소 목록의 목록을 검색하고 해당 요소의 수준을 반환하는 조건자를 정의하려고합니다. 예를 들어 요소를 검색 할 때 :

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

그래서 모든 목록에 대해 레벨을 추가합니다. 나는 카운터를 생각하고 있었지만 목록 순회를 위해 구현하는 방법을 모른다.

Answer 1

저는 이것이 숙제임이 가정합니다. 그래서 나는 코드보다는 힌트를 제공 할 것입니다. 현재의 작업이 다소 복잡하기 때문에 이것이 자신의 코드를 개발하기에 충분하기를 바랍니다.

하나의 사실과 3 개의 규칙이 필요합니다.

사실은 요소를 무시하고 (즉, _ 사용) 빈 목록으로 목록을 통합하고 반환 된 수준은 -1 (찾을 수 없음)이라고합니다.

첫 번째 및 두 번째 규칙은 목록의 머리글과 요소를 통합하고 수준 1을 반환하는 "교과서"목록 검색입니다. 다른 규칙은 머리를 무시하고 꼬리에있는 요소의 수준을 반환합니다.

마지막 규칙은 머리와 꼬리의 중첩 된 목록으로 목록의 머리를 통합하고, 재귀 적 호출을 수행하고, 반환 된 값이 0보다 큰지 확인합니다. 일치하는 경우 반환 값은 중첩 반환 값에 1을 더한 값입니다. 그렇지 않으면 재귀 적으로 꼬리를 확인하고 그 검사의 결과를 반환합니다.

당신이 카운터 구현을 위해이 같은 조건을 정의 할 수 있습니다

Answer 2

..

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). 

Answer 3

주의해야 할 첫 번째 것은 당신의 "목록의 목록은"근본적으로 트리 구조이며 기본적으로 깊이를하고있는 것입니다 - 왼쪽에서 오른쪽으로 트리 탐색.

따라서, 트리를 검색하여 항목을 검색하고 깊이를 반환 할 수있는 "공용"술어가 필요합니다. 반환에게 이러한 모든 일치한다 역 추적 :에 대한 모든 거기에있다의

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 
    .         % 

:

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

그런 다음 당신은 노동자의 조건이 필요합니다.

참고

• 은 당신이 할 필요가, 생각, 작업자 술어의 마지막 두 조항의 순서를 반대로이며, 너비 우선 탐색으로 변경합니다.

• X이 바인딩되어 있지 않거나 "목록 목록"의 요소 중 하나가 바인딩되지 않은 경우 ... 재미있는 문제가 발생할 수 있습니다. 프로덕션 코드의 경우 이러한 경계 사례를 적절히 처리하기 위해 경비원을 배치해야합니다.

건배!

Answer 4

이것이 대부분의 방식이라고 생각합니다. 예를 들어 돌아 오지 않습니다. 요소가 없으면 -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, _, _).