CODEWITHSUNDEEP
listprolog
gestalt
gestalt

Reputation: 375

Prolog List Search

I'm trying to define a predicate where it searches a list of lists for an element and returns the level of that element. For example when searching for element:

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

So for every list it adds a level. I was thinking of a counter, but I don't know how to implement that for a list traversal.

Upvotes: 2

Views: 1366

Answers (4)

magus
magus

Reputation: 1357

I think this is most of the way there.. it doesn't return eg. -1 if the element isn't found, and will report incorrect results if the element appears twice (ie it doesn't stop when the element found). It just shows one basic mechanism.

% 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, _, _).

Upvotes: 0

Nicholas Carey
Nicholas Carey

Reputation: 74197

The first thing to note is that your "list of lists" is fundamentally a tree structure and you're basically doing a depth-first, left-to-right traversal of the tree.

So, you want a "public" predicate that can search the tree for an item and return its depth. Backtracking should returns all such matches:

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

Then you need the worker predicate:

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

That's about all there is to it.

NOTES

  • To change it to a breadth-first search, all you need to do, I think, is reverse the order of the last two clauses of the worker predicate.

  • if X is unbound or one of the elements in the "list of lists" is unbound, you are likely to encounter...interesting problems. For production code, you'd want to put guards in place to properly deal with those edge cases.

Cheers!

Upvotes: 0

Haresh Chaudhary
Haresh Chaudhary

Reputation: 4400

you can define a predicate like this for the counter implementation.. 

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

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

I am assuming that this is a homework assignment, so I would provide hints rather than the code. I hope this is sufficient to develop your own code, because the task at hand is only moderately complex.

You would need one fact and three rules.

The fact would ignore the element (i.e. use _), unify the list with an empty list, and say that the returned level is -1 (not found).

The first and the second rules would be the "textbook" list search, unifying the element with the head of the list, and returning the level 1; the other rule would ignore the head, and return the level of the element in the tail.

The final rule would unify the head of the list with a nested list of head and tail, make a recursive call, and check the returned value to see if it is more than zero. If it is, the return value is the nested return plus one; otherwise, recursively check the tail, and return the result of that check.

Upvotes: 1

Related Questions