Part of INTERACTIVE
PROLOG GUIDE |
Prev |
TOC |
Next |

This lesson covers data structures in Prolog. The basic data structure
in Prolog is **term** which is expressed in form `name(arguments...)`.
If the number of arguments is zero then we speak about **atom**. A special
type of atom is **number**.

In this section, we introduce a data structure `date(Year,Month,Day)`
that represents date. First, we need a "constructor" of data structure
date that makes the data structure from year, month and day:` `

`make_date(Y,M,D,date(Y,M,D)).`

Second, we define functions to access components of data structure in a following way:

`get_year(date(Y,_,_),Y).``get_month(date(_,M,_),M).``get_day(date(_,_,D),D).`

`get_xxx` can be used to test or generate correspondent component
of data structure, but it can not be used to set the value of the component.
So, we have to define `set_xxx` to set values of components of data
structure date.

`set_year(Y,date(_,M,D),date(Y,M,D)).``set_month(M,date(Y,_,D),date(Y,M,D)).``set_day(D,date(Y,M,_),date(Y,M,D)).`

Now, it is easy to find the "same" day in next or previous year respectively using get and set functions.

`next_year(Today,NextYear):-``get_year(Today,Y), NY is Y+1, set_year(NY,Today,NextYear).`

`prev_year(Today,PrevYear):-``get_year(Today,Y), PY is Y-1, set_year(PY,Today,PrevYear).`

Note, that following definition of `prev_year` using `next_year`
is not correct. Do you know why?

`prev_year(Today,PrevYear):-next_year(PrevYear,Today). % incorrect`

Finding next year is relatively easy but what about finding next day,
i.e., tomorrow? Study following program to find where the possible problems
are hidden. The definition of test `correct_day`
follows the next section that covers working with lists.

`tomorrow(Today,Tomorrow):-``get_day(Today,D), ND is D+1, set_day(Today,ND,Tomorrow),``correct_date(Tomorrow).``% day inside month (i.e., not last day of month)`

`tomorrow(Today,Tomorrow):-``get_month(Today,M), NM is M+1,``set_month(Today,NM,Tmp), set_day(Tmp,1,Tomorrow),``correct_date(Tomorrow).``% last day of month`

`tomorrow(Today,Tomorrow):-``get_year(Today,Y), NY is Y+1, make_date(NY,1,1,Tomorrow).``% last day of year`

Note that it is also possible and probably more reasonable to encapsulate
the test `correct_date` to definitions of `make_date` and
`set_xxx`.

Lists

List is a widely used data structure which is build in Prolog. It is
still a term, e.g., `[1,2,3]` is equivalent to `'.'(1,'.'(2,'.'(3,nil)))`.
The following functions enable access to list elements.

`head(H,[H|_]).``tail(T,[_|T]). % T is list`

It is easy to access the first element of list as it corresponds to the head. However, finding the last element is a time consuming process as one has to go through the whole list to find it. Note that following "procedures" can be used to find the first/last element of list as well as to test whether given element is first/last element of list. It could even be used to generate list with given first/last element.

`first(F,[F|_]). % the same as head``last(L,[L]).``last(L,[H|T]):-last(L,T).`

The similar conclusion also holds for finding prefix and suffix respectively. Again, the same procedure can be used to test or generate prefix/suffix respectively as well as to generate list with given prefix/suffix. Try it.

`prefix([],_).``prefix([H|T1],[H|T2]):-prefix(T1,T2).``suffix(S,S).``suffix([H|T],L):-suffix(T,L).`

Testing membership is an important method for working with lists. Prolog
definiton of `member` can test membership relation as well as generate
successive members of list. A similar function, `nth_member`, can
also be used to test or to generate n-th member of list. However, it can
not be used to count a sequence number of given element (define the function
that counts a sequence number of given element as your homework).

`member(X,[X|_]).``member(X,[_|T]):-member(X,T).``nth_member(1,[M|_],M).``nth_member(N,[_|T],M):-N>1, N1 is N-1, nth_member(N1,T,M).`

Another popular function on lists is `append` which appends a
list to another list. It can be also used to disjoint list (see following
definition of `prefix` and `suffix`).

`append([],L,L).``append([H|T],L,[H|LT]):-append(T,L,LT).`

Now, prefix and suffix relations can be easily redefined using `append`:

`prefix(P,L):-append(P,_,L).``suffix(S,L):-append(_,S,L).`

`append` can be successfuly used in many other operations with
lists including testing (or generating) sublist. The following rule exploits
again the declarative character of Prolog.

`sublist(S,L):-append(_,S,P),append(P,_,L).`

There are (at least) two other ways how to define `sublist`, e.g.,
using prefix and suffix relations. All these definitions are equivalent.
However, the procedure `sublist3` is probably the closest to traditional
(non-declarative) programming style as it uses technique known as "floating
window".

`sublist2(S,L):-prefix(P,L),suffix(S,P).``sublist3(S,L):-prefix(S,L).``sublist3(S,[_|T]):-sublist3(S,T).`

Back to Dates example

Let us return to our example of data structure date.
Now, we can define the test `correct_date` using lists.

First, we add two facts to Prolog database with distribution of days:

`year(regular,[31,28,31,30,31,30,31,31,30,31,30,31]).``year(intercalary,[31,29,31,30,31,30,31,31,30,31,30,31]).`

Then, we prepare test of intercalary years:

`is_intercalary_year(Y):-``Z is Y mod 4, Z=0. % every fourth year is intercalary`

Finally, it is possible to test correctness of date:

`correct_date(date(Y,M,D)):-``correct_month(M),``correct_day(Y,M,D).`

`correct_month(M):- M>0, M<13.``correct_day(Y,2,D):-``is_intercalary_year(Y),``test_day_of_year(intercalary,M,D).`

`correct_day(Y,M,D):-``test_day_of_year(regular,M,D).`

`test_day_of_year(Type,M,D):-``year(Type,Days),``nth_member(M,Days,Max),``D>0, D<=Max.`

Note, that the above definition of `correct_day` assumes that
the only difference between regular and intercalary years is the number
of days in February which is higher in intercalary years.

Part of INTERACTIVE
PROLOG GUIDE |
Prev |
TOC |
Next |

Last update 7

Designed and maintained by Roman Bartak

© October 1997