Intellektual tizimlar

1.1.8. Ispolzovaniye spiskov. Spiski – odna iz naiboleye chasto upotreblyayemыx struktur v PROLOGe. Spisok – eto nabor obyektov odnogo i togo je tipa. Pri zapisi spisok zaklyuchayut v kvadratnыye skobki, a elementы spiska razdelyayut zapyatыmi, naprimer:
[1,2,3]
[1.1,1.2,3.6]
[“vchera”,”segodnya”,”zavtra”]
Elementami spiska mogut bыt lyubыye termы PROLOGa, t.ye. atomы, chisla, peremennыye i sostavnыye termы.
Kajdыy nepustoy spisok mojet bыt razdelen na golovu – pervыy element spiska i xvost – ostalnыye elementы spiska. Eto pozvolyayet vsyakiy spisok predstavit v vide binarnogo dereva (ris 2).

Ris 2.
U spiska, sostoyaщyego tolko iz odnogo elementa, golovoy yavlyayetsya etot element, a xvostom – pustoy spisok.
Dlya ispolzovaniya spiska neobxodimo opisat predikat spiska.
Naprimer: num([1,2,3]).
Pust mы xotim opisat s pomoщyu spiska porodы sobak.
Programma 13
DOMAINS
dog_list= symbol* /* zdes «*» ukazыvayet na spisok*/
PREDICATES
dogs(dog_list).
CLAUSES
dogs([“layka”,”borzaya”,”dog”,”bolonka”]).
Posle zaprosa:
goal: dogs(X)
budut napechatanы vse porodы sobak, a posle zaprosa:
goal: dogs(_,_,_,X)
poluchim: X = bolonka.
Operasiya razdeleniya spiska na golovu i xvost oboznachayetsya s pomoщyu vertikalnoy chertы:
[Head|Tail]
S pomoщyu etoy operasii mojno realizovыvat rekursivnuyu obrabotku spiska. Naprimer, yesli mы xotim napechatat vse elementы spiska iz Programmы 13 postrochno, to eto mojno vыpolnit s pomoщyu rekursivnogo opredeleniya predikata:
print_list([ ]).
print_list([X|Y]) :- write(X),nl, print_list([Y]).
Dlya opisaniya etogo predikata v razdele goal programmы mojno ispolzovat konstruksiyu:
show :- dogs(X), print_list(X).
Yesli neobxodimo ustanovit nalichiye nekotorogo elementa v spiske, to primenyayetsya pravilo:
find_it( X,[X| _ ]).
find_it( X,[ _ |Y]):- find_it( X,[Y]).
V pervom opisanii proisxodit sravneniye obyekta poiska i golovы tekuщyego spiska. Yesli eto sravneniye neuspeshno, to proisxodit otkat i popыtka povtoreniya so vtorыm variantom.
Programma 14
DOMAINS
dog_list=symbol*
PREDICATES
dogs(dog_list).
find_it(symbol,dog_list).
GOAL
find_it(«bolonka»,[«layka», «dog» ]),write(“da”).
CLAUSES
find_it(X,[X,_]).
find_it(X,[_,Y]):-find_it(X,[Y]).
Pervoye pravilo opisыvayet situasiyu, kogda iskomыy element X sovpadayet s golovoy spiska.
Vtoroye pravilo ispolzuyetsya pri neuspexe pervogo pravila i opisыvayet novыy vыzov pervogo pravila, no uje s usechennыm spiskom, v kotorom net pervogo elementa i t.d. Yesli v spiske net elementov (pustoy spisok), to vtoroye pravilo okazыvayetsya neuspeshnыm.
Programma ne napechatayet Yes, poskolku bolonki net v spiske sobak.
Sleduyuщiy primer proizvodit podschet summы vsex elementov spiska chisel.
Programma 15
DOMAINS
spisok=integer*
PREDICATES
summa_sp(spisok,integer)
CLAUSES
summa_sp([],0).
summa_sp([H|T],S):-summa_sp(T,S1),S= H +S1.
Rassmotrim operasiyu sliyaniya dvux spiskov.
Pust L1 i L2 – dve peremennыye, predstavlyayuщiye vxodnыye spiski. L3 – vыxodnoy spisok, poluchayemыy sliyaniyem L1 i L2.
append([ ],L,L).
append( [N|L1], L2, [N|L3] ):- append(L1, L2, L3).
Pervыy variant etogo pravila vыpolnyayetsya kogda pervыy spisok pustoy, vtoroy rabotayet v ostalnыx sluchayax.
Rassmotrim ispolzovaniye etogo predikata pri sleduyuщyem vыzove:
append([1,2,3], [4,5],_).
Zdes pervыy variant pravila snachala ne rabotayet, tak kak pervыy spisok ne pustoy.
Nachinayet rabotat vtoroye pravilo, tak kak tretiy spisok pustoy, k nemu ne primenima operasiya deleniya na golovu i xvost. Chto kasayetsya pervogo spiska, to on v prosesse rekursivnыx vыzovov preterpevayet deleniya na golovu i xvost, i v konse konsov stanovitsya pustыm (yego elementы popadayut v stek)
append([ ],[4,5],_).
Posle etogo srabatыvayet pervыy variant pravila, i tretiy spisok inisializiruyetsya vtorыm:
append([ ],[4,5], [4,5]).
I, nakones, chtobы zavershit rekursivnыye vыzovы, PROLOG izvlekayet iz steka (v obratnom poryadke) elementы pervogo spiska i vozvraщayet ix, v sootvetstvii s opisaniyem vtorogo varianta pravila, v spiski 1 i 3:
append([1,2,3], [4,5],[1,2,3,4,5]).
Rassmotrim, kak ispolzuyutsya spiski i mexanizm rekursii pri reshenii izvestnoy zadachi o mujike, volke, koze i kapuste.
Programma 16
DOMAINS
LOC = east ; west /* opisaniye beregov */
STATE = state(LOC,LOC,LOC,LOC) /* opisaniye polojeniya obyektov */
PATH = STATE* /* spisok sostoyaniy */
PREDICATES
go(STATE,STATE) /* zapusk algoritma */
path(STATE,STATE,PATH,PATH) /* poisk puti k novomu sostoyaniyu */
move(STATE,STATE) /* perexod ot sostoyaniya k sostoyaniyu */
opposite(LOC,LOC) /* opisaniye protivopolojnыx storon */
unsafe(STATE) /* opisaniye opasnыx sostoyaniy */
member(STATE,PATH) /* bыlo li takoye sostoyaniye ? */
write_path(PATH) /* vыvod otveta */
write_move(STATE,STATE) /* raspechatka xoda */
GOAL
go(state(east,east,east,east),state(west,west,west,west)),
write(“solved press any key to continue”),
readchar(_),
exit.
CLAUSES
go(S,G):-
path(S,G,[S],L),
nl,write(“A solution is:”),nl,
write_path(L),
fail.
go(_,_).
path(S,G,L,L1):- move(S,S1), not( unsafe(S1) ), not( member(S1,L)), path( S1,G,[S1|L],L1),!.
path(G,G,T,T):- !. /* Konechnoye sostoyaniye naydeno, spisok L kopiruyetsya v L1*/
move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). /* mujik i volk */
move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). /* mujik i koza*/
move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). /* mujik i kapusta */
move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). /* odin mujik */
opposite(east,west).
opposite(west,east):-!. /* opisaniye protivopolojnыx storon */
unsafe( state(F,X,X,_) ):- opposite(F,X) /* volk syedayet kozu */
unsafe( state(F,_,X,X) ):- opposite(F,X). /* koza syedayet kapustu */
member(X,[X|_]).
member(X,[_|L]):-member(X,L) /* proverka sostoyaniy, kotorыye uje bыli */
write_path( [H1,H2|T] ) :- !,
readchar(_), write_move(H1,H2), write_path([H2|T]).
write_path( [ ] ).
write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!,
write(“ Mujik peresekayet reku s”,X,” na “,Y),nl.
write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!,
write(“ Mujik vezet volka s “,X,” berega na “,Y),nl.
write_move( state(X,W,X,C), state(Y,W,Y,C) ) :-!,
write(“ Mujik vezet kozu s”,X,” berega na “,Y),nl.
write_move( state(X,W,G,X), state(Y,W,G,Y) ) :-!,
write(“ Mujik vezet kapustu s “,X,” berega na “,Y),nl.