Lập trình Prolog_chương 4-5
Chương này trình bày khái niệm về danh sách, một trong những cấu trúc đơn giản nhất và thông dụng nhất, cùng với những chương trình tiêu biểu minh họa cách vận dụng danh sách trong prolog. Cấu trúc danh sách tạo nên một môi trường lập trình thuận tiện củ ngôn ngữ Prolog.
CHÆÅNG 4
Cáú u truï c danh saï c h
Chæång naìy trçnh baìy khaïi niãûm vãö danh saïch, mäüt trong nhæîng cáúu truïc
âån giaín nháút vaì thäng duûng nháút, cuìng våïi nhæîng chæång trçnh tiãu biãøu
minh hoaû caïch váûn duûng danh saïch trong Prolog. Cáúu truïc danh saïch taûo
nãn mäüt mäi træåìng láûp trçnh thuáûn tiãûn cuía ngän ngæî Prolog.
I. Biãøu diãùn cáúu truïc danh saïch
Danh saïch laì kiãøu cáúu truïc dæî liãûu âæåüc sæí duûng räüng raîi trong caïc ngän
ngæî láûp trçnh phi säú. Mäüt danh saïch laì mäüt daîy báút kyì caïc âäúi tæåüng. Khaïc våïi
kiãøu dæî liãûu táûp håüp, caïc âäúi tæåüng cuía danh saïch coï thãø truìng nhau (xuáút
hiãûn nhiãöu láön) vaì mäùi vë trê xuáút hiãûn cuía âäúi tæåüng âãöu coï yï nghéa.
Danh saïch laì caïch diãùn âaût ngàõn goün cuía kiãøu dæî liãûu haûng phæïc håüp
trong Prolog. Haìm tæí cuía danh saïch laì dáúu cháúm “.”. Do viãûc biãøu diãùn danh
saïch båíi haìm tæí naìy coï thãø taûo ra nhæîng biãøu thæïc máûp måì, nháút laì khi xæí lyï
caïc danh saïch gäöm nhiãöu pháön tæí läöng nhau, cho nãn Prolog quy æåïc âàût daîy
caïc pháön tæí cuía danh saïch giæîa caïc càûp moïc vuäng.
Chàóng haûn .(a,.(b,[ ])). Laì danh saïch [ a, b ].
Danh saïch caïc pháön tæí anne, tennis, tom, skier (tãn ngæåìi) âæåüc viãút :
[ anne, tennis, tom, skier ]
chênh laì haìm tæí :
. ( anne, .( tennis, .( tom, .( skier, [ ] ) ) ) )
Caïch viãút daûng càûp moïc vuäng chè laì xuáút hiãûn bãn ngoaìi cuía mäüt danh
saïch. Nhæ âaî tháúy åí muûc træåïc, moüi âäúi tæåüng cáúu truïc cuía Prolog âãöu coï
biãøu diãùn cáy. Danh saïch cuîng khäng nàòm ngoaûi lãû, cuîng coï cáúu truïc cáy.
95
96 Láûp trçnh lägich trong Prolog
Laìm caïch naìo âãø biãøu diãùn danh saïch båíi mäüt âäúi tæåüng Prolog chuáøn ?
Coï hai khaí nàng xaíy ra laì danh saïch coï thãø räùng hoàûc khäng. Nãúu danh saïch
räùng, noï âæåüc viãút dæåïi daûng mäüt nguyãn tæí :
[]
Nãúu danh saïch khaïc räùng, coï thãø xem noï âæåüc cáúu truïc tæì hai thaình pháön
(pair syntax) :
1. Thaình pháön thæï nháút, âæåüc goüi laì âáöu (head) cuía danh saïch.
2. Thaình pháön thæï hai, pháön coìn laûi cuía danh saïch (træì ra pháön âáöu),
âæåüc goüi laì âuäi (tail) cuía danh saïch, cuîng laì mäüt danh saïch.
Trong vê duû trãn thç âáöu laì anne, coìn âuäi laì danh saïch :
[ tennis, tom, skier ]
Noïi chung, âáöu cuía danh saïch coï thãø laì mäüt âäúi tæåüng báút kyì cuía Prolog,
coï thãø laì cáy hoàûc biãún, nhæng âuäi phaíi laì mäüt danh saïch. Hçnh I.1. Biãøu diãùn
daûng cáy cuía danh saïch mä taí cáúu truïc cáy cuía danh saïch âaî cho :
.
anne . âuäi cuîng laì danh saïch
âáöu tennis .
tom .
skier []
Hçnh I.1. Biãøu diãùn daûng cáy cuía danh saïch
Vç âuäi tail laì mäüt danh saïch, nãn tail coï thãø räùng, hoàûc laûi coï thãø âæåüc taûo
thaình tæì mäüt âáöu head vaì mäüt âuäi tail khaïc.
Chuï yï ràòng danh saïch räùng xuáút hiãûn trong säú caïc haûng, vç ràòng pháön tæí
cuäúi cuìng coï thãø xem laì danh saïch chè gäöm mäüt pháön tæí duy nháút coï pháön
âuäi laì mäüt danh saïch räùng:
[ skier ]
Vê duû trãn âáy minh hoaû nguyãn lyï cáúu truïc dæî liãûu täøng quaït trong
Prolog aïp duûng cho caïc danh saïch coï âäü daìi tuyì yï.
?- L1 = [ a, b, c ].
?- L2 = [ a, a, a ].
Cáúu truïc danh saïch 97
L1 = [ a, b, c ]
L2 = [ a, a, a ]
?- Leisure1 = [ tennis, music, [ ] ].
?- Leisure2 = [ sky, eating ],
?- L = [ anne, Leisure1, tom, Leisure2 ].
Leisure1 = [ tennis, music ]
Leisure2 = [ sky, eating ]
L = [ anne, [ tennis, music ], tom, [ sky, eating ] ]
Nhæ váûy, caïc pháön tæí cuía mäüt danh saïch coï thãø laì caïc âäúi tæåüng coï kiãøu
báút kyì, kãø caí kiãøu danh saïch. Thäng thæåìng, ngæåìi ta xæí lyï âuäi cuía danh
saïch nhæ laì mäüt danh saïch. Chàóng haûn, danh saïch :
L = [ a, b, c ]
coï thãø viãút :
tail = [ b, c ] vaì L = .(a, tail)
Âãø biãøu diãùn mäüt danh saïch âæåüc taûo thaình tæì âáöu (Head) vaì âuäi (Tail),
Prolog sæí duûng kyï hiãûu | (split) âãø phán caïch pháön âáöu vaì pháön âuäi nhæ
sau :
L = [ a | Tail ]
Kyï hiãûu | âæåüc duìng mäüt caïch ráút täøng quaït bàòng caïch viãút mäüt säú pháön
tæí tuyì yï cuía danh saïch træåïc | räöi danh saïch caïc pháön tæí coìn laûi. Danh saïch
báy giåì âæåüc viãút laûi nhæ sau :
[ a, b, c ] = [ a | [ b, c ] ] = [ a, b | [ c ] ] = [ a, b, c | [ ] ]
Sau âáy laì mäüt säú caïch viãút danh saïch :
Kiãøu hai thaình pháön Kiãøu liãût kã pháön tæí
[] []
[a|[]] [a]
[a|b|[]] [ a, b ]
[a|X] [a|X]
[a|b|X] [ a, b | X ]
[ X1 | [ ... [ Xn | [ ] ]... ] ] [ X1, ... , Xn ]
Ta coï thãø âënh nghéa danh saïchtheo kiãøu âãû quy nhæ sau :
List Æ [ ]
List Æ [ Element | List ]
98 Láûp trçnh lägich trong Prolog
II. Mäüt säú vë tæì xæí lyï danh saïch cuía Prolog
SWI-Prolog coï sàôn mäüt säú vë tæì xæí lyï danh saïch nhæ sau :
Vë tæì YÏ nghéa
append(List1, List2, List3) Gheïp hai danh saïch List1 vaì List2 thaình List3.
Kiãøm tra Elem coï laì pháön tæí cuía danh saïch List hay
member(Elem, List) khäng, nghéa laì Elem håüp nháút âæåüc våïi mäüt trong
caïc pháön tæí cuía List.
Kiãøm tra nãúu pháön tæí Y coï âæïng ngay sau pháön tæí X
nextto(X, Y, List)
trong danh saïch List hay khäng.
Xoaï khoíi danh saïch List1 nhæîng pháön tæí håüp nháút
delete(List1, Elem, List2)
âæåüc våïi Elem âãø traí vãö kãút quaí List2.
Láúy pháön tæí Elem ra khoíi danh saïch List âãø traí vãö
select(Elem, List, Rest) nhæîng pháön tæí coìn laûi trong Rest, coï thãø duìng âãø
cheìn mäüt pháön tæí vaìo danh saïch.
Kiãøm tra pháön tæí thæï Index (tênh tæì 0) cuía danh
nth0(Index, List, Elem)
saïch List coï phaíi laì Elem hay khäng.
Kiãøm tra pháön tæí thæï Index (tênh tæì 1) cuía danh saïch
nth1(Index, List, Elem)
List coï phaíi laì Elem hay khäng.
Kiãøm tra pháön tæí âæïng cuäúi cuìng trong danh saïch
last(List, Elem)
List coï phaíi laì Elem hay khäng.
Nghëch âaío thæï tæû caïc pháön tæí cuía danh saïch List1
reverse(List1, List2)
âãø traí vãö kãút quaí List2.
permutation(List1, List2) Hoaïn vë danh saïch List1 thaình danh saïch List2.
Chuyãøn danh saïch List1 chæïa caïc pháön tæí báút kyì
thaình danh saïch phàóng List2.
flatten(List1, List2)
Vê duû : flatten([a, [b, [c, d], e]], X).
cho kãút quaí X = [a, b, c, d, e].
sumlist(List, Sum) Tênh täøng caïc pháön tæí cuía danh saïch List chæïa toaìn
säú âãø traí vãö kãút quaí Sum.
Nãúu Low vaì High laì caïc säú sao cho Low =< High, thç
numlist(Low, High, List)
traí vãö danh saïch List = [Low, Low+1, ..., High].
Chuï yï mäüt säú vë tæì xæí lyï danh saïch coï thãø sæí duûng cho moüi raìng buäüc, kãø
caí khi caïc tham âäúi âãöu laì biãún.
Trong Prolog, táûp håüp âæåüc biãøu diãùn båíi danh saïch, tuy nhiãn, thæï tæû caïc
pháön tæí trong mäüt táûp håüp laì khäng quan troüng, caïc âäúi tæåüng duì xuáút hiãûn
Cáúu truïc danh saïch 99
nhiãöu láön chè âæåüc xem laì mäüt pháön tæí cuía táûp håüp. Caïc pheïp toaïn vãö danh
saïch coï thãø aïp duûng cho caïc táûp håüp. Âoï laì :
• Kiãøm tra mäüt pháön tæí coï màût trong mäüt danh saïch tæång tæû viãûc kiãøm tra
mäüt pháön tæí coï thuäüc vãö mäüt táûp håüp khäng ?
• Gheïp hai danh saïch âãø nháûn âæåüc mäüt danh saïch thæï ba tæång æïng våïi
pheïp håüp cuía hai táûp håüp.
• Thãm mäüt pháön tæí måïi, hay loaûi boí mäüt pháön tæí.
Prolog coï sàôn mäüt säú vë tæì xæí lyï táûp håüp nhæ sau :
Vë tæì YÏ nghéa
is_set(Set) Kiãøm tra Set coï phaíi laì mäüt táûp håüp hay khäng
Chuyãøn danh saïch List thaình táûp håüp Set giæî
nguyãn thæï tæû caïc pháön tæí cuía List (nãúu List coï caïc
list_to_set(List, Set) pháön tæí truìng nhau thç chè láúy pháön tæí gàûp âáöu
tiãn). Vê duû : list_to_set([a,b,a], X) cho kãút quaí
X = [a,b].
intersection(Set1, Set2, Set3) Pheïp giao cuía hai táûp håüp Set1 vaì Set2 laì Set3.
Traí vãö kãút quaí pheïp hiãûu cuía hai táûp håüp Set vaì
subtract(Set, Delete, Result) Delete laì Result (laì táûp Set sau khi âaî xoaï hãút caïc
pháön tæí cuía Delete coï màût trong âoï).
Traí vãö kãút quaí pheïp håüp cuía hai táûp håüp Set1 vaì
union(Set1, Set2, Set3)
Set2 laì Set3.
Kiãøm tra táûp håüp Subset coï laì táûp håüp con cuía Set
subset(Subset, Set)
hay khäng.
III. Caïc thao taïc cå baín trãn danh saïch
III.1. Xáy dæûng laûi mäüt säú vë tæì coï sàôn
Sau âáy ta seî trçnh baìy mäüt säú thao taïc cå baín trãn danh saïch bàòng caïch
xáy dæûng laûi mäüt säú vë tæì coï sàôn cuía Prolog.
III.1.1. Kiãøm tra mäüt pháön tæí coï màût trong danh saïch
Prolog kiãøm tra mäüt pháön tæí coï màût trong mäüt danh saïch nhæ sau :
member(X, L)
100 Láûp trçnh lägich trong Prolog
trong âoï, X laì mäüt pháön tæí vaì L laì mäüt danh saïch. Âêch member(X, L) âæåüc
thoaí maîn nãúu X xuáút hiãûn trong L. Vê duû :
?- member( b, [ a, b, c ] )
Yes
?- member( b, [ a, [ b, c ] ] )
No
?- member( [ b, c], [ a, [ b, c ] ] )
Yes
Tæì caïc kãút quaí trãn, ta coï thãø giaíi thêch quan hãû member(X, L) nhæ sau :
Pháön tæí X thuäüc danh saïch L nãúu :
1. X laì âáöu cuía L, hoàûc nãúu
2. X laì mäüt pháön tæí cuía âuäi cuía L.
Ta coï thãø viãút hai âiãöu kiãûn trãn thaình hai mãûnh âãö, mãûnh âãö thæï nháút laì
mäüt sæû kiãûn âån giaín, mãûnh âãö thæï hai laì mäüt luáût :
member( X, [ X | Tail ] ).
member( X, [ Head | Tail ] ) :- member( X, Tail ).
hoàûc :
member(X, [X|T]).
member(X, [_|T]) :- member(X, T).
III.1.2. Gheïp hai danh saïch
Âãø gheïp hai danh saïch, Prolog coï haìm :
append( L1, L2, L3).
trong âoï, L1 vaì L2 laì hai danh saïch, L3 laì kãút quaí cuía pheïp gheïp L1 vaì L2. Vê
duû :
?- append( [ a, b ], [ c, d ], [ a, b, c, d ] ).
Yes
?- append( [ a, b ], [ c, d ], [ a, b, a, c ] ).
No
Haìm append hoaût âäüng phuû thuäüc tham âäúi âáöu tiãn L1 theo caïch nhæ
sau :
1. Nãúu tham âäúi âáöu tiãn laì danh saïch räùng, thç tham âäúi thæï hai vaì thæï
ba phaíi laì mäüt danh saïch duy nháút, goüi laì L. Ta viãút trong Prolog nhæ
sau :
append( [ ], L, L).
Cáúu truïc danh saïch 101
2. Nãúu tham âäúi âáöu tiãn cuía append laì danh saïch khaïc räùng, thç noï gäöm
mäüt âáöu vaì mäüt âuäi nhæ sau
[ X | L1 ]
Kãút quaí pheïp gheïp danh saïch laì danh saïch [ X | L3 ], våïi L3 laì pheïp
gheïp cuía L1 vaì L2. Ta viãút trong Prolog nhæ sau :
append( [ X | L1 ], L2, [ X | L3 ] ) :- append( L1, L2, L3 ).
Hçnh 4.2 dæåïi âáy minh hoaû pheïp gheïp hai danh saïch [ X | L1 ] vaì L2.
[ X | L1 ]
X L1 L2
L3
X L3
[ X | L3 ]
Hçnh III.1. Gheïp hai danh saïch [ X | L1 ] vaì L2 thaình [ X | L3 ].
Ta coï caïc vê duû sau :
?- append( [ a, b, c ], [ 1, 2, 3 ], L ).
L = [ a, b, c, 1, 2, 3 ]
?- append( [ a, [ b, c ], d ], [ a, [ ], b ], L ] ).
L = [ a, [ b, c ], d, a, [ ], b ]
Thuí tuûc append âæåüc sæí duûng ráút mãöm deío theo nhiãöu caïch khaïc nhau.
Chàóng haûn Prolog âæa ra bäún phæång aïn âãø phán taïch mäüt danh saïch âaî
cho thaình hai danh saïch måïi nhæ sau :
?- append( L1, L2, [ a, b, c ] ).
L1 = [ ]
L2 = [ a, b, c ];
L1 = [ a ]
L2 = [ b, c ];
L1 = [ a, b ]
L2 = [ c ];
L1 = [ a, b, c ]
L2 = [ ];
Yes
102 Láûp trçnh lägich trong Prolog
Sæí duûng append, ta cuîng coï thãø tçm kiãúm mäüt säú pháön tæí trong mäüt danh
saïch. Chàóng haûn, tæì danh saïch caïc thaïng trong nàm, ta coï thãø tçm nhæîng
thaïng âæïng træåïc mäüt thaïng âaî cho, giaí sæí thaïng nàm (May) :
?- append( Before, [ May | After ] ,
[ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, nov, dec ] ).
Before = [ jan, fev, mar, avr ]
After = [ jun, jul, aut, sep, oct, nov, dec ]
Yes
Thaïng âæïng ngay træåïc vaì thaïng âæïng ngay sau thaïng nàm nháûn âæåüc nhæ
sau :
?- append( _, [ Month1, may, Month2 | _ ] ,
[ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, nov, dec ] ).
Month1 = avr
Month2 = jun
Yes
Báy giåì cho træåïc danh saïch :
L1 = [ a, b, z, z, c, z, z, z, d, e ]
Ta cáön xoïa caïc pháön tæí âæïng sau ba chæî z liãn tiãúp, kãø caí ba chæî z :
?- L1 = [ a, b, z, z, c, z, z, z, d, e ],
append( L2, [ z, z, z | _ ], L1 ).
L1 = [ a, b, z, z, c, z, z, z, d, e ]
L2 = [ a, b, z, z, c ]
Træåïc âáy ta âaî âënh nghéa quan hãû member( X, L ) âãø kiãøm tra mäüt pháön
tæí X coï màût trong mäüt danh saïch L khäng. Báy giåì bàòng caïch sæí duûng
append, ta coï thãø âënh nghéa laûi member nhæ sau :
member1( X, L ) :- append( L1, [ X | L2], L).
Mãûnh âãö naìy coï nghéa : nãúu X coï màût trong danh saïch L thç L coï thãø âæåüc
phán taïch thaình hai danh saïch, våïi X laì âáöu cuía danh saïch thæï hai. Âënh
nghéa member1 hoaìn toaìn tæång âæång våïi âënh nghéa member.
ÅÍ âáy ta sæí duûng hai tãn khaïc nhau âãø phán biãût hai caïch caìi âàût Prolog.
Ta cuîng coï thãø âënh nghéa laûi member1 bàòng caïch sæí duûng biãún nàûc danh
(anonymous variable) :
member1( X, L ) :- append( _ , [ X | _ ], L).
Cáúu truïc danh saïch 103
member1( b, [ a, b, c ] )
append( L1, [ b | L2 ], [ a, b, c ] )
Mãûnh âãö 1 cuía append Mãûnh âãö 2 cuía append
So khåïp : So khåïp :
L1 = [ ] L1 = [ X | L1’ ]
[ b | L2 ] = [ a, b, c ] [ b | L2 ] = L2’
[ a, b, c ] = [ X | L3’ ]
Tháút baûi vç b ≠ a
Tæì âoï keïo theo :
X = a, L3’ = [ b, c ]
append( L1’, [ b | L2 ], [ b, c ] )
Mãûnh âãö 1 cuía append
So khåïp :
L1’ = [ ]
[ b | L2 ] = [ b, c ]
Tæì âoï keïo theo :
L2 = [ c ]
thaình cäng
Hçnh III.2. Thuí tuûc member1 tçm tuáön tæû mäüt âäúi tæåüng trong danh saïch âaî cho.
So saïnh hai caïch caìi âàût khaïc nhau vãö quan hãû thaình viãn, ta nháûn tháúy
nghéa thuí tuûc trong âënh nghéa member âæåüc thãø hiãûn ráút roî :
Trong member, âãø kiãøm tra pháön tæí X coï màût trong mäüt danh saïch L
khäng,
1. Træåïc tiãn kiãøm tra pháön tæí âáöu cuía L laì âäöng nháút våïi X, nãúu khäng,
2. Kiãøm tra ràòng X coï màût trong pháön âuäi cuía L.
Nhæng trong træåìng håüp âënh nghéa member1, ta tháúy hoaìn toaìn nghéa
khai baïo maì khäng coï nghéa thuí tuûc.
Âãø hiãøu âæåüc caïch member1hoaût âäüng nhæ thãú naìo, ta haîy xem xeït quaï
trçnh Prolog thæûc hiãûn cáu hoíi :
?- member1( b, [ a, b, c ] ).
104 Láûp trçnh lägich trong Prolog
Caïch tçm cuía thuí tuûc member1 trãn âáy tæång tæû member, bàòng caïch
duyãût tæìng pháön tæí, cho âãún khi tçm tháúy âäúi tæåüng cáön tçm, hoàûc danh saïch
âaî caûn.
III.1.3. Bäø sung mäüt pháön tæí vaìo danh saïch
Phæång phaïp âån giaín nháút âãø bäø sung mäüt pháön tæí vaìo danh saïch laì âàût
noï åí vë trê âáöu tiãn, âãø noï tråí thaình âáöu. Nãúu X laì mäüt âäúi tæåüng måïi, coìn L
laì danh saïch cáön bäø sung thãm, thç danh saïch kãút quaí seî laì :
[X|L]
Ngæåìi ta khäng cáön viãút thuí tuûc âãø bäø sung mäüt pháön tæí vaìo danh saïch.
Båíi vç viãûc bäø sung coï thãø âæåüc biãøu diãùn dæåïi daûng mäüt sæû kiãûn nãúu cáön :
insert( X, L, [ X | L ] ).
III.1.4. Loaûi boí mäüt pháön tæí khoíi danh saïch
Âãø loaûi boí mäüt pháön tæí X khoíi danh saïch L, ngæåìi ta xáy dæûng quan hãû :
remove( X, L, L1 )
trong âoï, L1 âäöng nháút våïi L, sau khi X bë loaûi boí khoíi L. Thuí tuûc remove coï
cáúu truïc tæång tæû member. Ta coï thãø láûp luáûn nhæ sau
1. Nãúu pháön tæí X laì âáöu cuía danh saïch, thç kãút quaí laì âuäi cuía danh
saïch.
2. Nãúu khäng, tçm caïch loaûi boí X khoíi pháön âuäi cuía danh saïch.
remove( X, [ X | Tail ], Tail ).
remove( X, [ Y | Tail ], [ Y | Tail1 ] ) :-
remove( X, Tail, Tail1 ).
Tæång tæû thuí tuûc member, thuí tuûc remove mang tênh khäng xaïc âënh.
Nãúu coï nhiãöu pháön tæí laì X coï màût trong danh saïch, thç remove coï thãø xoaï báút
kyì pháön tæí naìo, do quaï trçnh quay lui. Tuy nhiãn, mäùi láön thæûc hiãûn, remove
chè xoaï mäüt pháön tæí laì X maì khäng âuûng âãún nhæîng pháön tæí khaïc. Vê duû :
?- remove( a, [ a, b, a, a ], L ).
L = [ b, a, a ];
L = [ a, b, a ];
L = [ a, b, a ]
No
Cáúu truïc danh saïch 105
Thuí tuûc remove tháút baûi nãúu danh saïch khäng chæïa pháön tæí cáön xoaï.
Ngæåìi ta coï thãø sæí duûng remove trong mäüt khêa caûnh khaïc, muûc âêch âãø bäø
sung mäüt pháön tæí måïi vaìo báút cæï âáu trong danh saïch.
Vê duû, nãúu ta muäún âàût pháön tæí a vaìo taûi moüi vë trê báút kyì trong danh
saïch [ 1, 2, 3 ], chè cáön âàût cáu hoíi : Cho biãút danh saïch L nãúu sau khi xoaï a,
ta nháûn âæåüc danh saïch [ 1, 2, 3 ] ?
?- remove( a, L, [ 1, 2, 3 ] ).
L = [ a, 1, 2, 3 ];
L = [ 1, a, 2, 3 ];
L = [ 1, 2, a, 3 ];
L = [ 1, 2, 3, a ]
No
Mäüt caïch täøng quaït, pheïp toaïn cheìn insert mäüt pháön tæí X vaìo mäüt danh
saïch List âæåüc âënh nghéa båíi thuí tuûc remove bàòng caïch sæí duûng mäüt danh
saïch låïn hån LargerList laìm tham âäúi thæï hai :
insert( X, List, LargerList ) :-
remove( X, LargerList, List ).
Ta âaî âënh nghéa quan hãû thuäüc vãö trong thuí tuûc member1 bàòng caïch sæí
duûng thuí tuûc append. Tuy nhiãn, ta cuîng coï thãø âënh nghéa laûi quan hãû
thuäüc vãö trong thuí tuûc måïi member2 båíi thuí tuûc remove bàòng caïch xem mäüt
pháön tæí X thuäüc vãö mäüt danh saïch List nãúu X bë xoaï khoíi List :
member2( X, List ) :-
remove( X, List, _ ).
III.1.5. Nghëch âaío danh saïch
Sæí duûng append, ta coï thãø viãút thuí tuûc nghëch âaío mäüt danh saïch nhæ
sau :
reverse ( [ ], [ ] ).
reverse ( [ X | Tail ], R ) :-
reverse (Tail, R1 ),
append(R1, [X], R).
?- reverse( [ a, b, c , d, e, f ] , L).
L = [f, e, d, c, b, a]
Yes
106 Láûp trçnh lägich trong Prolog
Sau âáy laì mäüt thuí tuûc khaïc âãø nghëch âaío mäüt danh saïch nhæng coï sæí
duûng haìm bäø tråü trong thán thuí tuûc :
revert(List, RevList) :-
rev(List, [ ], RevList).
rev([ ], R, R).
rev([H|T], S, R) :-
rev(T, [H|S], R).
?- revert( [ a, b, c , d, e, f ] , R).
R = [f, e, d, c, b, a]
Yes
Sæí duûng reverse, ta coï thãø kiãøm tra mäüt danh saïch coï laì âäúi xæïng
(palindrome) kay khäng :
palindrome(L) :-
reverse( L, L ).
?- palindrome([ a, b, c , d, c, b, a ]).
Yes
III.1.6. Danh saïch con
Ta xáy dæûng thuí tuûc sublist nháûn hai tham âäúi laì hai danh saïch L vaì S
sao cho S laì danh saïch con cuía L nhæ sau :
?- sublist( [ c, d, e ], [ a, b, c , d, e, f ] )
Yes
?- sublist( [ c, e ], [ a, b, c , d, e, f ] )
No
Nguyãn lyï âãø xáy dæûng thuí tuûc sublist tæång tæû thuí tuûc member1, màûc duì
åí âáy quan hãû danh saïch con täøng quaït hån.
L
L1 X L2 member( X, L )
L [ X | L2 ]
L1 S L3 sublist( S, L )
L2
Hçnh III.3. Caïc quan hãû member vaì sublist.
Cáúu truïc danh saïch 107
Quan hãû danh saïch con âæåüc mä taí nhæ sau :
S laì mäüt danh saïch con cuía L nãúu :
1. Danh saïch L coï thãø âæåüc phán taïch thaình hai danh saïch L1 vaì L2, vaì
nãúu
2. Danh saïch L2 coï thãø âæåüc phán taïch thaình hai danh saïch S vaì L3.
Nhæ âaî tháúy, viãûc phán taïch caïc danh saïch coï thãø âæåüc mä taí båíi quan hãû
gheïp append.
Do âoï ta viãút laûi trong Prolog nhæ sau :
sublist( S, L ) :-
append( L1, L2, L ), append( S, L3, L2 ).
Ta tháúy thuí tuûc sublist ráút mãöm deío vaì do váûy coï thãø sæí duûng theo nhiãöu
caïch khaïc nhau. Chàóng haûn ta coï thãø liãût kã moüi danh saïch con cuía mäüt
danh saïch âaî cho nhæ sau :
?- sublist( S, [ a, b, c ] ).
S = [ ];
S = [ a ];
S = [ a, b ];
S = [ a, b, c ];
S = [ b ];
...
III.2. Hoaïn vë
Âäi khi, ta cáön taûo ra caïc hoaïn vë cuía mäüt danh saïch. Ta xáy dæûng quan
hãû permutation coï hai tham biãún laì hai danh saïch, maì mäüt danh saïch laì hoaïn
vë cuía danh saïch kia. Ta seî táûn duûng pheïp quay lui nhæ sau :
?- permutation( [ a, b, c ], P ).
P = [ a, b, c ];
P = [ a, c, b ];
P = [ b, a, c ];
...
Nguyãn lyï hoaût âäüng cuía thuí tuûc swap dæûa trãn hai træåìng håüp phán
biãût, tuyì theo danh saïch thæï nháút :
1. Nãúu danh saïch thæï nháút räùng, thç danh saïch thæï hai cuîng phaíi räùng.
108 Láûp trçnh lägich trong Prolog
2. Nãúu danh saïch thæï nháút khaïc räùng, thç noï seî coï daûng [ X | L ] vaì âæåüc
tiãún haình hoaïn vë nhæ sau : træåïc tiãn hoaïn vë L âãø nháûn âæåüc L1, sau
âoï cheìn X vaìo táút caí caïc vë trê trong L1.
X L
hoaïn vë L
L1 L1 laì mäüt hoaïn vë cuía L
Cheìn X taûi mäüt vë trê âãø nháûn âæåüc mäüt hoaïn vë cuía [ X | L ]
Hçnh III.4. Mäüt caïch xáy dæûng hoaïn vë permutation cuía danh saïch [ X | L ].
Ta nháûn âæåüc hai mãûnh âãö tæång æïng våïi thuí tuûc nhæ sau :
permutation( [ ], [ ] ).
permutation( [ X | L ], P ) :-
permutation( L, L1 ), insert( X, L1, P ).
Mäüt phæång phaïp khaïc laì loaûi boí pháön tæí X khoíi danh saïch âáöu tiãn,
hoaïn vë pháön coìn laûi cuía danh saïch naìy âãø nháûn âæåüc danh saïch P, sau âoï
thãm X vaìo pháön âáöu cuía P. Ta coï chæång trçnh khaïc permutation2 nhæ sau :
permutation2( [ ], [ ] ).
permutation2( L, [ X | P ] ) :-
remove( X, L, L1 ), permutation2( L1, P ).
Tæì âáy, ta coï thãø khai thaïc thuí tuûc hoaïn vë, chàóng haûn (chuï yï khi chaûy
Arity Prolog cáön goî vaìo mäüt dáúu cháúm pháøy ; sau ->) :
?- permutation( [ red, blue, green ], P ).
P = [ red, blue, green ];
P = [ red, green, blue ];
P = [ blue, red, green ];
P = [ blue, green, red ];
P = [ green, red, blue ];
P = [ green, blue, red ];
Yes
Hoàûc nãúu sæí duûng permutation theo caïch khaïc nhæ sau :
?- permutation( L, [ a, b, c ] ).
Prolog seî raìng buäüc liãn tiãúp cho L âãø âæa ra 6 hoaïn vë khaïc nhau coï thãø.
Tuy nhiãn, nãúu NSD yãu cáöu mäüt giaíi phaïp khaïc, Prolog seî khäng bao giåì
Cáúu truïc danh saïch 109
traí låìi “No”, maì råi vaìo mäüt voìng làûp vä haûn do phaíi tçm kiãúm mäüt hoaïn vë
måïi maì thæûc ra khäng täön taûi. Trong træåìng håüp naìy, thuí tuûc permutation2
chè tçm tháúy mäüt hoaïn vë thæï nháút, sau âoï ngay láûp tæïc råi vaìo mäüt voìng làûp
vä haûn. Vç váûy, cáön chuï yï khi sæí duûng caïc quan hãû hoaïn vë naìy.
III.3. Mäüt säú vê duû vãö danh saïch
III.3.1. Sàõp xãúp caïc pháön tæí cuía danh saïch
Xáy dæûng thuí tuûc sàõp xãúp caïc pháön tæí coï cuía mäüt danh saïch bàòng phæång
phaïp cheìn nhæ sau :
ins(X, [ ], [ X ]).
ins(X, [H|T], [ X,H|T ]) :-
X @=< H.
ins(X, [ H|T ], [ H|L ]) :-
X @> H, ins( X, T, L ).
?- ins(8, [ 1, 2, 3, 4, 5 ], L).
L = [1, 2, 3, 4, 5, 8]
Yes
?- ins(1, L, [ 1, 2, 3, 4, 5 ]).
L = [2, 3, 4, 5]
Yes
ins_sort([ ], [ ]).
ins_sort([H|T], L) :-
ins_sort(T, L1),
ins(H, L1, L).
?- ins_sort([3, 2, 6, 4, 7, 1], L).
L = [1, 2, 3, 4, 6, 7]
Yes
III.3.2. Tênh âäü daìi cuía mäüt danh saïch
Xáy dæûng thuí tuûc tênh âäü daìi hay âãúm säú læåüng caïc pháön tæí coï màût trong
mäüt danh saïch âaî cho nhæ sau :
length( L, N ).
Xaíy ra hai træåìng håüp :
1. Nãúu danh saïch räùng, thç âäü daìi N = 0.
110 Láûp trçnh lägich trong Prolog
2. Nãúu danh saïch khaïc räùng, thç noï âæåüc taûo thaình tæì danh saïch coï
daûng :
[ head | queue ]
vaì coï âäü daìi bàòng 1 cäüng våïi âäü daìi cuía queue.
Ta coï chæång trçnh Prolog nhæ sau :
length( [ ], 0 ).
length( [ _ | Queue ], N ) :-
length(Queue, N1 ),
N is 1 + N1.
Kãút quaí chaûy Prolog nhæ sau :
?- length( [ a, b, c, d, e ], N ).
N=5
Yes
?- length( [ a, [ b, c ], d, e ], N ).
N=4
Yes
Ta tháúy ràòng trong mãûnh âãö thæï hai, hai âêch cuía pháön thán laì khäng
thãø hoaïn âäøi cho nhau, vç ràòng N1 phaíi âæåüc raìng buäüc træåïc khi thæûc hiãûn
âêch :
N is 1 + N1
Chàóng haûn, nãúu goüi trace, quaï trçnh thæûc hiãûn length( [ 1, 2, 3 ], N ) nhæ
sau :
(0) goüi length([1, 2, 3], N) ->
(1) goüi length([2, 3], N’) ->
(2) goüi length([3], N’’) ->
(3) goüi length([ ], N’’’) -> N’’’ = 0
(4) goüi N’’ is 1 + 0 -> N’’ = 1
(5) goüi N’ is 1 + 1 -> N’ = 2
(6) goüi N is 1 + 2 -> N=3
Våïi is, ta âaî âæa vaìo mäüt quan hãû nhaûy caím våïi thæï tæû thæûc hiãûn caïc âêch,
vaì do váûy khäng thãø boí qua yãúu täú thuí tuûc trong chæång trçnh.
Âiãöu gç seî xaíy ra nãúu ta khäng sæí duûng is trong chæång trçnh. Chàóng
haûn :
length1( [ ], 0 ).
Cáúu truïc danh saïch 111
length1( [ _ | Queue ], N ) :-
length1( Queue, N1 ),
N = 1 + N1.
Luïc naìy, nãúu goüi :
?- length1( [ a, [ b, c ], d, e ], N ).
Prolog traí låìi :
N = 1 + (1 + (1 + (1 + 0)))
Yes
Pheïp cäüng do khäng âæåüc khåíi âäüng mäüt caïch tæåìng minh nãn seî khäng
bao giåì âæåüc thæûc hiãûn. Tuy nhiãn, ta coï thãø hoaïn âäøi hai âêch cuía mãûnh âãö
thæï hai trong length1 :
length1( [ ], 0 ).
length1( [ _ | Queue ], N ) :-
N = 1 + N1,
length1( Queue, N1 ).
Kãút quaí chaûy chæång trçnh sau khi hoaïn âäøi váùn y hãût nhæ cuî. Báy giåì, ta
laûi coï thãø ruït goün mãûnh âãö vãö chè coìn mäüt âêch :
length1( [ ], 0 ).
length2( [ _ | Queue ], 1 + N ) :-
length2( Queue, N ).
Kãút quaí chaûy chæång trçnh láön naìy váùn y hãût nhæ cuî. Prolog khäng âæa
ra traí låìi nhæ mong muäún, maì laì :
?- length1([ a, b, c, d], N).
N = 1+ (1+ (1+ (1+0)))
Yes
III.3.3. Taûo sinh caïc säú tæû nhiãn
Chæång trçnh sau âáy taûo sinh vaì liãût kã caïc säú tæû nhiãn :
% Natural Numbers
nat(0).
nat(N) :- nat(M), N is M + 1.
Khi thæûc hiãûn caïc âêch con trong cáu hoíi :
?- nat(N), write(N), nl, fail.
112 Láûp trçnh lägich trong Prolog
caïc säú tæû nhiãn âæåüc taûo sinh liãn tiãúp nhåì kyî thuáût quay lui. Sau khi säú tæû
nhiãn âáöu tiãn nat(N) âæåüc in ra nhåì write(N), hàòng fail bàõt buäüc thæûc hiãûn
quay lui. Khi âoï, luáût thæï hai âæåüc váûn duûng âãø taûo sinh säú tæû nhiãn tiãúp
theo vaì cæï thãú tiãúp tuûc cho âãún khi NSD quyãút âënh dæìng chæång trçnh (^C).
Toïm tàõt chæång 4
• Danh saïch laì mäüt cáúu truïc hoàûc räùng, hoàûc gäöm hai pháön : pháön âáöu laì
mäüt pháön tæí vaì pháön coìn laûi laì mäüt danh saïch.
• Prolog quaín lyï caïc danh saïch theo cáúu truïc cáy nhë phán. Prolog cho
pheïp sæí duûng nhiãöu caïch khaïc nhau âãø biãøu diãùn danh saïch.
[ Object1, Object2, ... ]
hoàûc [ Head | Tail ]
hoàûc [ Object1, Object2, ... | Others ]
Våïi Tail vaì Others laì caïc danh saïch.
• Caïc thao taïc cäø âiãøn trãn danh saïch coï thãø láûp trçnh âæåüc laì : kiãøm tra
mäüt pháön tæí coï thuäüc vãö mäüt danh saïch cho træåïc khäng, pheïp gheïp
hai danh saïch, bäø sung hoàûc loaûi boí mäüt pháön tæí åí âáöu hoàûc cuäúi danh
saïch, trêch ra mäüt danh saïch con...
Baìi táûp chæång 4
1. Viãút mäüt thuí tuûc sæí duûng append âãø xoïa ba pháön tæí cuäúi cuìng cuía danh
saïch L, taûo ra danh saïch L1. Hæåïng dáùn : L laì pheïp gheïp cuía L1 våïi mäüt
danh saïch cuía ba pháön tæí (âaî bë xoïa khoíi L).
2. Viãút mäüt daîy caïc âêch âãø xoïa ba pháön tæí âáöu tiãn vaì ba pháön tæí cuäúi cuìng
cuía mäüt danh saïch L, âãø traí vãö danh saïch L2.
3. Âënh nghéa quan hãû :
last_element( Object, List )
sao cho Object phaíi laì pháön tæí cuäúi cuìng cuía danh saïch List. Haîy viãút
thaình hai mãûnh âãö, trong âoï coï mäüt mãûnh âãö sæí duûng append, mãûnh âãö
kia khäng sæí duûng append.
4. Âënh nghéa hai vë tæì :
Cáúu truïc danh saïch 113
even_length( List ) vaì odd_length( List )
âæåüc thoîa maîn khi säú caïc phán tæí cuía danh saïch List laì chàôn hay leí tæång
æïng. Vê duû danh saïch :
[ a, b, c, d ] coï âäü daìi chàôn,
[ a, b, c ] coï âäü daìi leî.
5. Cho biãút kãút quaí Prolog traí låìi caïc cáu hoíi sau :
?- [1,2,3] = [1|X].
?- [1,2,3] = [1,2|X].
?- [1 | [2,3]] = [1,2,X].
?- [1 | [2,3,4]] = [1,2,X].
?- [1 | [2,3,4]] = [1,2|X].
?- b(o,n,j,o,u,r) =.. L.
?- bon(Y) =.. [X,jour].
?- X(Y) =.. [bon,jour].
6. Viãút chæång trçnh Prolog kiãøm tra mäüt danh saïch coï phaíi laì mäüt táûp håüp
con cuía mäüt danh saïch khaïc khäng ? Chæång trçnh hoaût âäüng nhæ sau :
?- subset2([4,3],[2,3,5,4]).
Yes
7. Viãút chæång trçnh Prolog âãø láúy ra caïc pháön tæí tæì mäüt danh saïch. Chæång
trçnh cuîng coï thãø cheìn caïc pháön tæí vaìo mäüt danh saïch hoaût âäüng nhæ
sau :
?- takeout(3,[1,2,3],[1,2]).
Yes
?- takeout(X,[1,2,3],L).
X=1
L = [2, 3] ;
X=2
L = [1, 3] ;
X=3
L = [1, 2] ;
No
?- takeout(4,L,[1,2,3]).
4
L = [4, 1, 2, 3] ;
L = [1, 4, 2, 3] ;
L = [1, 2, 4, 3] ;
114 Láûp trçnh lägich trong Prolog
L = [1, 2, 3, 4] ;
No
8. Viãút vë tæì Prolog getEltFromList(L,N,E) cho pheïp láúy ra pháön tæí thæï N
trong mäüt danh saïch. Tháút baûi nãúu danh saïch khäng coï âuí N pháön tæí.
Chæång trçnh hoaût âäüng nhæ sau :
?- getEltFromList([a,b,c],0,X).
No
?- getEltFromList([a,b,c],2,X).
X=b
?- getEltFromList([a,b,c],4,X).
No
9. Viãút chæång trçnh Prolog tçm pháön tæí låïn nháút vaì pháön tæí nhoí nháút trong
mäüt danh saïch caïc säú. Chæång trçnh hoaût âäüng nhæ sau :
?- maxmin([3,1,5,2,7,3],Max,Min).
Max = 7
Min = 1
Yes
?- maxmin([2],Max,Min).
Max = 2
Min = 2
Yes
10. Viãút chæång trçnh Prolog chuyãøn mäüt danh saïch phæïc håüp, laì danh saïch
maì mäùi pháön tæí coï thãø laì mäüt danh saïch con chæïa caïc danh saïch con
phæïc håüp khaïc, thaình mäüt danh saïch phàóng laì danh saïch chè chæïa caïc
pháön tæí trong táút caí caïc danh saïch con coï thãø, giæî nguyãn thæï tæû luïc
âáöu. Chæång trçnh hoaût âäüng nhæ sau :
flatten([[1,2,3],[4,5,6]], Flatlist).
Flatlist = [1,2,3,4,5,6]
Yes
flatten([[1,[hallo,[[aloha]]],2,[],3],[4,[],5,6]], Flatlist)
Flatlist = [1, hallo, aloha, 2, 3, 4, 5, 6]
Yes
11. Viãút caïc chæång trçnh Prolog thæûc hiãûn caïc vë tæì xæí lyï táûp håüp cho åí pháön
lyï thuyãút (muûc II).