Binary Trees
When using lists of data, which are sets of objects, it is inefficient to scan a list for a specific element if the list is very long. What Prolog efficiently does is uses tree structures to show relations. If we look at the structure of a binary tree structure. This type of structure is either empty or it holds a root, a left subtree, and a right subtree. A root is permitted to be anything but the subtrees must be binary trees. For example, lets look at a list of data {a,b,c,d}.The basic way to represent this binary tree, we can use a specific symbol to be the empty tree, and a functor will construct a non-empty tree from the three elements, the root, the left subtree, and the right subtree. (a functor is the name of the relation and its arguments).
The functor will be t, where the root of the tree is X, the left subtree is L, and the right subtree is R. The functor is represented by the term t(L,X,R). An atom, nil, represents the empty tree. The example of the list of data {a,b,c,d} is represented by the term:
t( t(nil,b,nil), a t( t(nil,d,nil), c, nil))
Now if we look at the members in the set of letters, the relation is named by the word in. The term in(X,T) is true if X is a node in a tree T where the root of T is X, or X is the left or right subtree of T. The list of letters is represented by the tree figure T. The term in(X,T) searches through the list of letters through a method called backtracking where X = a, X = b, X = c, and X = d. If we look at the goal, in(a, T), it will succeed because of the first clause of the procedure in. There will be multiple recursive calls though for finding the object d in in(d,T). Something that is made a goal such as in(e,T) will be searched for by the entire tree but then fails because of the recursive searches through the subtrees.
A higher efficiency of this method can be reached by setting an order from left to right. For example: t(Left, X,Right). This means that the nodes on the left subtree are smaller than X, the nodes on the right subtree are greater than X, and both of the subtrees are ordered from biggest to smallest value.
bagof, setof, and findall
Just by looking at previous blogs you can see that you are able to produce all the objects that satisfy one goal. Although this is true, you can only produce an object one by one, and each time a new object is produced, the previous one disappears. These unique features to Prolog allow you to generate all of the objects at once so that the user is able to see them all together. An example of this would be trying to see all of the objects that are part of a list. Prolog has “built-in predicates,” bagof, setof, and findall, that allow the user to complete such requests.
Let’s take the example: bagof(X,P,L)
This will produce the List L of all the objects X, where the goal P is satisfied. X and P though have to have variables in common. A real life example can go something like this with facts within a program.
gender(george,male).
gender(karen,female).
gender(frank,male).
gender(suzy,female).
To retrieve the list of all the people who are female you would write this goal:
?-bagof(Child, gender(Child,female),List).
List = [karen,suzy]
Let’s say we did not specify a specific gender to the goal request. Through the process of backtracking, we would receive two lists of those who are female and those who are male. An unspecified version would go like this:
?- bagof(Child, gender(Child, Gender), List).
The results here would be:
Gender = male
List = [george,frank];
Gender = female
List = [karen, suzy];
no
What if want all of the children in one list no matter their gender. We are strictly looking for if the value exists in the list.
?- bagof( Child, Gender ^ gender(Child, Gender), List).
List = [george, karen, frank, suzy]
The ^ is known as a predifined infix operator. Also, let’s say there is no solution for the goal P, this leads to simply the goal to fail. If an object occurs multiple times, them the all the times it occurs will appear in the list of L objects (there will be duplicates of the items).
Now, let’s look at the predicate setof. It is very similar to bagof:
setof( X, P, L)
The predicate setof is different than bagof because it does two things differently. One, the objects in list L will be ordered, and two, if there are any duplicated items, they will be eliminated and produced once. The ordering of the objects is based on an alphabetical ordering system or to the relation “<,” where the objects in the list are numbers. Let’s think about if the objects are structures. This means that the principal functors are compared for ordering. If the functors are equal, then the left-most, top-most functors take precedence.
Let’s use the same gender example as bagof.
?- setof( Child, Gender ^ gender(Child, Gender), ChildList),
setof( Gender, Child ^ gender(Child, Gender), GenderList).
ChildList = [frank, george, karen, suzy]
GenderList = [female, male]
You can see above how each object in the list is ordered based upon the alphabetical system.
Any object with setof can be used. You can collect the data based upon pairings, such as Gender/Child, which would give the result, for example, [female/karen].
The final predicate, findall is very similar to bagof as well.
findall(X, P, L)
This produces a list of objects in L that will satisfy P. The difference here is that all of the objects X within the list L will be collected not matter the possible difference in solutions for variables in P that are not shared with X. Let’s continue to use the gender example.
?- findall( Child, gender( Child, Gender), List).
List = [ george, karen, frank, suzy]
The reason findall works so well is because if there is an object X that does not satisfy P, the findall will still pass with L = [].
There is a tricky part to this though if findall is not a built-in predicate through implementation, then the programmed must be programmed in a certain way. as always backtracking is used to find all of the solutions for P. As the solution is produced, it is put into the database so that it will not be lost when the user tries to find the next solution. After the solutions have been produced, they must be put into a list and drawn back from the database. All the solutions produced form a “queue,” or a list of data items. After each of the solutions are produced, the list of data items “dissolve.” The end of the queue must be marked by the atom “bottom.” This term is different from the expected solution.
The source used for this blog post is the book: Prolog: Programming Artificial Intellegence by Ivan Bratko pgs 182-184