Session 8: Meta predicates (findall/3)

Some things cannot be expressed in 'plain' Prolog because you need meta predicates. The most common case is when you want to find all solutions for a query at once (instead of retrieving them manually by typing ';'). We can solve this by using the build-in predicate findall/3. The first argument indicates which part of the query you want to store, the second argument is the query for which we need all results and the third argument is the name of the list in which we place the results. A few examples:

?- findall(Elem,member(Elem,[a,b,c]),List).
List = [a,b,c]
?- findall((Elem,Fib), (member(Elem,[5,10,15,20]),fibo(Elem,Fib)), Res). % uses fibo/2 from session2
Res = [ (5, 5), (10, 55), (15, 610), (20, 6765)]

Notice this last example: a query can be a conjunction, but make sure you use extra parenthesis to group the conjuncts into a single argument. The same holds for the result variables we want to see. In this case we want pairs (N,fib(N)), so we also use extra parenthesis.

Now try to solve the next problems using findall/3.

Graphs

Remember the representation of directed graphs given in Session 6: we represent a directed graph as a list of arcs. An arc going from a node a to a node b is represented as a/b. E.g. the list [a/c,c/d,c/e,b/d,d/e] represents a graph with 5 nodes and 5 arcs. Now write a predicate that finds all parents of a given node in a given graph (node X is a parent of node Y if there is an edge from X to Y).

Using this same representation for graphs, what does the following predicate p/2 do?

p(Graph,Node) :- member(Parent/Node,Graph), write(Parent), nl, fail.

p(_Graph,_Node) :- write('end').

Write a predicate shortest_path(X,Y,Graph,ShortestPath) that finds the shortest path between two nodes X and Y in Graph. To solve this exercise you can use the predicate find_path_2/2 that we defined in Session 6. Remember that the meaning of this predicate was the following: find_path_2(X,Y,Path,Graph) succeeds if Path is the path between X and Y in Graph.

Mixing chemical products (again)

Recall Exercise 9 of Session 3:

During a student initiation ritual some years ago, several students got injured when they came in contact with a mix of 'daily use' products such as vinegar, oil,... . To prevent such accidents from happening in the future, you are asked to develop a system so that you can test whether a certain mixture is dangerous or not. To help you, a chemical expert gives you a database of mixtures of 'daily products' and numbers indicating how dangerous the mixtures are. The database is written as prolog facts:

reacts(vinegar,salt,25).
reacts(salt,water,3).
reacts('brown soap',water,10).
reacts('pili pili', milk,7).
reacts(tonic,bailey,8).

Higher numbers are more dangerous. The order of the elements is not important: e.g. salt and vinegar react the same as vinegar and salt do. Now suppose that you can add the numbers: e.g. the number for a mixture of vinegar, salt and water is 25 (vinegar & salt) + 3 (salt & water) = 28. Also, suppose that a number less than 5 results in no irritation, between 6 and 12 results in minor irritation, between 13 and 20 results in minor burning wounds, between 21 and 30 results in severe burning wounds and higher values can be lethal.
Write a predicate advice/1 that given a mixture, writes to the screen what the result of using that mixture would be, e.g.

?- advice([vinegar,salt,water]).
Warning: this mixture causes severe burning wounds, never use this!
Yes

?- advice([jam, salt, pepper, water, 'red onions', 'brown soap']).
Warning: this mixture could result in minor burning wounds!
Yes

Try to find a shorter solution than the solution of Session 3 by using findall/3.

A Classification Problem

Suppose you have some bottles of wine from three different wine farmers in total. For most bottles you know from which wine farmer they are (call these bottles the train data). However, for some of the bottles you do not know from which farmer they are (call these bottles the test data). Now you want to develop a system that classifies the bottles of wine from the test data: given the results of a chemical analysis of the wine in the bottle, the system should specify if this bottle is from farmer 1, 2 or 3.

We will solve this problem with a technique called Nearest Neightbours. If we want to classify a bottle b1 from an unknown farmer (a bottle from the test data), we can look for the bottle b2 in the train data that is most similar to bottle b1. We will then assume that b1 is from the same farmer as b2. This technique is called 1-Nearest Neighbour. We could also look for the 5 bottles in the train data that are most similar to bottle b1, check from which farmer most of these 5 bottles are and then assume that bottle b1 is also from that farmer. This is called 5-Nearest Neighbours.

To be able to use this technique, we need to have a measure of distance dist(b1,b2) between two bottles of wine b1 and b2. The bottle b2 that is 'most similar' to bottle b1 is then the bottle for which dist(b1,b2) is the smallest. More precisely, we will look at the distance between the chemical analysis of bottle b1 and the chemical analysis of bottle b2. We will represent the chemical analysis of a bottle of wine as a list of 13 numbers, each number indicating 1 chemical property.

WineData.pl contains 125 traindata/2 facts. Each of these facts corresponds to 1 bottle for which we know the farmer. The first argument of such a fact is always a chemical analysis (a list of 13 numbers), the second argument is the farmer the bottle is from (1, 2 or 3).
WineData.pl also contains 39 testdata/2 facts. Each of these facts corresponds to 1 bottle for which we do not know the farmer. The first argument of such a fact is always a bottle-number (b1 to b39), the second argument is a chemical analysis.

Write a predicate that calculates a distance measure between two chemical analyses (e.g. Manhattan distance, Euclidean distance, ...). Note that this is a distance measure in the 13-dimensional space (since a chemical analysis is a list with 13 elements).
Write a predicate that, given a bottle in the test data, classifies this bottle (i.e. determines from which farmer it is). Use 5 Nearest Neighbour: first find the 5 most similar bottles in the train data and then determine from which farmer most of these 5 bottles are.

Note that WineData.pl contains 39 testdata_class/2 facts, one for each bottle in the test data. These facts tell us from which farmer the bottle really is. The first argument of such a fact is always the bottle-number, the second argument is the farmer. This knowledge now allows us to check how good the classifications are that we make with 5 Nearest Neighbour.

Write a predicate that classifies all bottles in the test data and, checks which classifications are correct (using the testdata_class/2 facts) and returns the accuracy of our classifications (accuracy is the number of correct classifications divided by the total number of classifications).

Extra exercises on lists

The following two exercises are regular exercises on lists and do not involve findall !

Suppose we represent a LOA-board as a list of lists, where each of the inner lists represents a row. We use the atom b to indicate a black disk at a certain board position, the atom w to indicate a white disk and the atom o to indicate an open board position.
A LOA-board is 'valid' if and only if the board is square with width 8 and each position is either open (o) or filled with a black disk (b) or a white disk (w).

Write a predicate squareboard/2 that is given as the first argument a list. The predicate should return (as the second argument) the width of the board if the list represents a square board (that is: every row contains the same number of elements, and this is equal to the number of rows) and should fail otherwise.
Write a predicate validboard/1 that succeeds if its argument is a valid LOA-board and fails otherwise.
Can you use validboard/1 also to create a valid LOA-board?