CODEWITHSUNDEEP
prologlogicartificial-intelligence
Eryk Hubert Siejka
Eryk Hubert Siejka

Reputation: 43

extracting algorithm for building prolog rules

I have to create some "list of predicates" in prolog. But I don't fully understand the way of thinking that I have to learn if I want to create some working predicates.

I've seen some popular tutorials (maybe I've not been searching precisely enough), but I can not find any tutorial that teaches how to plan an algorithm using REALLY elementary steps.

For example...

Task:

Write a concat(X,Y,Z). predicate that is taking elements from the lists X and Y and concatenates them in the list Z.

My analysing algorithm:

Firstly I define a domain of the number of elements I'll be concatenating (the lengths of the lists X and Y) as non-negative integers (XCount >= 0 and YCount >= 0). Then I create a predicate for the first case, which is XCount = 0 and YCount = 0:

concat([],[],[]).

... then test it and find that it is working for the first case.

Then, I create a predicate for the second case, where XCount = 1 and YCount = 0, as:

concat(X,[],X).

... and again test it and find that it is working with some unexpected positive result.

Results:

I can see that this algorithm is working not only for XCount = 1 but also for XCount = 0. So I can delete concat([],[],[]). and have only concat(X,[],X)., because X = [] inside predicate concat(X,[],X). is the same as concat([],[],[])..

The second unexpected result is that the algorithm is working not only for XCount in 0,1 but for all XCount >= 0.

Then I analyse the domain and search for elements that weren't handled yet, and find that the simplest way is to create a second predicate for YCount > 0.

Remembering that using just X as the first argument can cover all XCount >= 0, I create a case for YCount = 1 and all Xes, which is:

concat(X,[Y|_],[Y|X]).

And this is the place where my algorithm gets a brain-buffer overflow.

Respecting stackoverflow rules, I'm asking precisely.

Questions:

  1. Is there any way to find the answer by myself? By which I mean - not an answer for the problem, but for the algorithm I've shown to solve it. In the other words, the algorithm of my algorithm.

  2. If you can answer question 1, how can I find this type of hint in future? Is there a specific name for my problem?

  3. How precise do I have to be - how many cases and in what language can I try to implement my algorithm that is not just "doing" things, but is "thinking" how to plan and create other algorithms.

Upvotes: 1

Views: 112

Answers (1)

Will Ness
Will Ness

Reputation: 71065

Lists are not defined as counts of elements in them. lists are defined recursively, as empty, or a pair of an element and the rest of elements:

list([]).
list([_A|B]) :- list(B).

Lists can be the same:

same_lists([], []).
same_lists([A|B], [A|C]) :- same_lists(B, C).

Or one can be shorter than the other, i.e. its prefix:

list_prefix([], L):- list(L).
list_prefix([A|B], [A|C]):- list_prefix(B, C).

Where the prefix ends, the suffix begins:

list_split([], L, L):- list(L).
list_split([A|B], Sfx, [A|C]):- list_split(B, Sfx, C).

So, general advice is: follow the types, how they are constructed, and analyze the situation according to all possible cases. With lists, it is either empty, or non-empty lists.

Upvotes: 2

Related Questions