Lập trình Prolog_chương 4-5

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

195
lượt xem 88
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập trình Prolog_chương 4-5

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).