Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 6

Chia sẻ: Dwefershrdth Vrthrtj | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

417
lượt xem 125
download

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

Chương 1: Mở đầu về ngôn ngữ Prolog Chương 2: Ngữ nghĩa của chương trình Prolog Chương3: Các phép toàn và số học Chương 4: Cấu trúc danh sách Chương 5: Kỹ thuật lập trình Prolog Phụ lục A: Một số chương trình Prolog Phụ lục B: Hướng dẫn sử dụng SWI-Prolog

Chủ đề:

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

Lưu

Nội dung Text: Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 6

88 L p trình lôgic trong Prolog ?- 1 =:= 2-1 ?- X =:= Y. 2. Cho bi t k t qu c a các câu h i sau ây : ?- op(X) is op(1). ?- op(X) = op(1). ?- op(op(Z), Y) = op(X, op(1)). ?- op(X, Y) = op(op(Y), op(X)). 3. T các nh nghĩa s t nhiên (nat) và phép c ng (addi) cho trong ví d 1 m c nh nghĩa hàm, hãy vi t ti p các hàm tr (subt), nhân (multi), chia (divi), lu th a (power), giai th a (fact), so sánh nh hơn (less) và tìm ư c s chung l n nh t (pdg) s d ng các hàm ã có (ch ng h n less, subt...). 4. Vi t hàm Prolog ki m tra m t s nguyên tuỳ ý N : a. N là s ch n (even number) s d ng quy tr c ti p Hư ng d n : N ch n thì N±2 cũng là s ch n b. N là s l (odd number) s d ng quy tr c ti p Hư ng d n : N l thì N±2 cũng là s l c. N ch n s d ng hàm ki m tra s l câu d (N ch n thì N±1 là s l ) d. N là s l s d ng hàm ki m tra s ch n câu c (N l thì N±1 ch n). 5. Vi t hàm Prolog làm duy t (tracking/traverse) trên cây nh phân theo các th t trư c (reorder), sau (post-order) và gi a (in-order). Gi s cây nh phân tương ng v i bi u th c s h c (5+6)*(3-(2/2)) là các m nh Prolog như sau : tree(’*’, tree(’+’, leaf(5), leaf(6)), tree(’-’, leaf(3), tree(’/’, leaf(2), leaf(2))) K t qu duy t cây như sau : theo th t trư c : [*, +, 5, 6, -, 3, /, 2, 2] th t gi a : [5, +, 6, *, 3, -, 2, /, 2] th t sau : [5, 6, +, 3, 2, 2, /, -, *] 6. Vi t l i hàm t o 10 s t nhiên ch n u tiên ( ã cho trong ph n quy) sao cho k t qu tr v là dãy s tăng d n. 7. L p b ng nhân table(R, N) có s b nhân (multiplicator) t 1 tr i v i s nhân N (multiplier) và d ng l i khi g p s b nhân R (k t qu R * N).
89 Các phép toán và s h c chính xác e = 10-5 : 8. Vi t các hàm tính g n úng giá tr các hàm sau v i 111 1 π cho n khi = 1 − + − +...
90 L p trình lôgic trong Prolog subst(B, E, X, V2), reduce(E, V). Câu h i : a. Cho bi t cách trao i tham bi n h p l trong ngôn ng mô t trên ây ? Cách trao i tham bi n nào thì không th th c hi n ư c ? b. Tìm cách thay i trình Prolog trên ây có th th c hi n ư c các phương pháp trao i tham bi n khác nhau. c. Cho bi t t m v c (scope) c a các bi n là tĩnh hay ng ? 10. Cho ví d m t th không nh hư ng dư i ây : arc(a,b). arc(d,f). arc(b,c). arc(f,a). arc(c,d). arc(a,b). arc(c,e). arc(h,i). arc(c,g). arc(i,j). arc(g,f). Hãy vi t hàm tìm ư ng i gi a hai nh c a th .
CHƯƠNG 4 C u trúc danh sách 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 ho 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 a ngôn ng Prolog. I. Bi u di n c u trúc danh sách Danh sách là ki u c u trúc d li u ư c s d ng r ng rãi trong các ngôn ng l p trình phi s . M t danh sách là m t dãy b t kỳ các i tư ng. Khác v i ki u d li u t p h p, các i tư ng c a danh sách có th trùng nhau (xu t hi n nhi u l n) và m i v trí xu t hi n c a i tư ng u có ý nghĩa. Danh sách là cách di n t ng n g n c a ki u d li u h ng ph c h p trong Prolog. Hàm t c a danh sách là d u ch m “.”. Do vi c bi u di n danh sách b i hàm t này có th t o ra nh ng bi u th c m p m , nh t là khi x lý các danh sách g m nhi u ph n t l ng nhau, cho nên Prolog quy ư c t dãy các ph n t c a danh sách gi a các c p móc vuông. Ch ng h n .(a,.(b,[ ])). Là danh sách [ a, b ]. Danh sách các ph n t anne, tennis, tom, skier (tên ngư i) ư c vi t : [ anne, tennis, tom, skier ] chính là hàm t : . ( anne, .( tennis, .( tom, .( skier, [ ] ) ) ) ) Cách vi t d ng c p móc vuông ch là xu t hi n bên ngoài c a m t danh sách. Như ã th y m c trư c, m i i tư ng c u trúc c a Prolog u có bi u di n cây. Danh sách cũng không n m ngo i l , cũng có c u trúc cây. Làm cách nào bi u di n danh sách b i m t i tư ng Prolog chu n ? Có hai kh năng x y ra là danh sách có th r ng ho c không. N u danh sách r ng, nó ư c vi t dư i d ng m t nguyên t : [] 95
96 L p trình lôgic trong Prolog N u danh sách khác r ng, có th xem nó ư c c u trúc t hai thành ph n (pair syntax) : 1. Thành ph n th nh t, ư c g i là u (head) c a danh sách. 2. Thành ph n th hai, ph n còn l i c a danh sách (tr ra ph n u), ư c g i là uôi (tail) c a danh sách, cũng là m t danh sách. Trong ví d trên thì u là anne, còn uôi là danh sách : [ tennis, tom, skier ] Nói chung, u c a danh sách có th là m t i tư ng b t kỳ c a Prolog, có th là cây ho c bi n, nhưng uôi ph i là m t danh sách. Hình I.1. Bi u di n d ng cây c a danh sách mô t c u trúc cây c a danh sách ã cho : . anne uôi cũng là danh sách . tennis u . tom . skier [] Hình I.1. Bi u di n d ng cây c a danh sách Vì uôi tail là m t danh sách, nên tail có th r ng, ho c l i có th ư c t o thành t m t u head và m t uôi tail khác. Chú ý r ng danh sách r ng xu t hi n trong s các h ng, vì r ng ph n t cu i cùng có th xem là danh sách ch g m m t ph n t duy nh t có ph n uôi là m t danh sách r ng: [ skier ] Ví d trên ây minh ho nguyên lý c u trúc d li u t ng quát trong Prolog áp d ng cho các danh sách có dài tuỳ ý. L1 = [ a, b, c ]. ?- L2 = [ a, a, a ]. ?- 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 ] ]
97 C u trúc danh sách Như v y, các ph n t c a m t danh sách có th là các i tư ng có ki u b t kỳ, k c ki u danh sách. Thông thư ng, ngư i ta x lý uôi c a danh sách như là m t danh sách. Ch ng h n, danh sách : L = [ a, b, c ] có th vi t : tail = [ b, c ] và L = .(a, tail) bi u di n m t danh sách ư c t o thành t u (Head) và uôi (Tail), Prolog s d ng ký hi u | (split) phân cách ph n u và ph n uôi như sau : L = [ a | Tail ] Ký hi u | ư c dùng m t cách r t t ng quát b ng cách vi t m t s ph n t tuỳ ý c a danh sách trư c | r i danh sách các ph n t còn l i. Danh sách bây gi ư c vi t l i như sau : [ a, b, c ] = [ a | [ b, c ] ] = [ a, b | [ c ] ] = [ a, b, c | [ ] ] Sau ây là m t s cách vi t danh sách : Ki u hai thà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 có th nh nghĩa danh sáchtheo ki u quy như sau : List [] List [ Element | List ] II. M t s v t x lý danh sách c a Prolog SWI-Prolog có s n m t s v t x lý danh sách như sau : Vt Ý nghĩa Ghép hai danh sách List1 và List2 thành List3. append(List1, List2, List3) Ki m tra Elem có là ph n t c a danh sách List hay không, nghĩa là Elem h p nh t ư c v i m t trong các member(Elem, List) ph n t c a List. Ki m tra n u ph n t Y có ng ngay sau ph n t X nextto(X, Y, List) trong danh sách List hay không.
98 L p trình lôgic trong Prolog Xoá kh i danh sách List1 nh ng ph n t h p nh t delete(List1, Elem, ư c v i Elem tr v k t qu List2. List2) L y ph n t Elem ra kh i danh sách List tr v select(Elem, List, nh ng ph n t còn l i trong Rest, có th dùng chèn Rest) m t ph n t vào danh sách. Ki m tra ph n t th Index (tính t 0) c a danh sách nth0(Index, List, List có ph i là Elem hay không. Elem) Ki m tra ph n t th Index (tính t 1) c a danh sách nth1(Index, List, List có ph i là Elem hay không. Elem) Ki m tra ph n t ng cu i cùng trong danh sách last(List, Elem) List có ph i là Elem hay không. Ngh ch o th t các ph n t c a danh sách List1 reverse(List1, tr v k t qu List2. List2) Hoán v danh sách List1 thành danh sách List2. permutation(List1, List2) Chuy n danh sách List1 ch a các ph n t b t kỳ thành danh sách ph ng List2. flatten(List1, Ví d : flatten([a, [b, [c, d], e]], X). List2) cho k t qu X = [a, b, c, d, e]. Tính t ng các ph n t c a danh sách List ch a toàn sumlist(List, Sum) s tr v k t qu Sum. N u Low và High là các s sao cho Low =< High, thì numlist(Low, High, tr v danh sách List = [Low, Low+1, ..., List) High]. Chú ý m t s v t x lý danh sách có th s d ng cho m i ràng bu c, k c khi các tham i u là bi n. Trong Prolog, t p h p ư c bi u di n b i danh sách, tuy nhiên, th t các ph n t trong m t t p h p là không quan tr ng, các i tư ng dù xu t hi n nhi u l n ch ư c xem là m t ph n t c a t p h p. Các phép toán v danh sách có th áp d ng cho các t p h p. ó là : Ki m tra m t ph n t có m t trong m t danh sách tương t vi c ki m tra m t • ph n t có thu c v m t t p h p không ? Ghép hai danh sách nh n ư c m t danh sách th ba tương ng v i phép • h p c a hai t p h p. Thêm m t ph n t m i, hay lo i b m t ph n t . •
99 C u trúc danh sách Prolog có s n m t s v t x lý t p h p như sau : Vt Ý nghĩa Ki m tra Set có ph i là m t t p h p hay không is_set(Set) Chuy n danh sách List thành t p h p Set gi nguyên th t các ph n t c a List (n u List có các list_to_set(List, Set) ph n t trùng nhau thì ch l y ph n t g p u tiên). Ví d : list_to_set([a,b,a], X) cho k t qu X = [a,b]. Phép giao c a hai t p h p Set1 và Set2 là Set3. intersection(Set1, Set2, Set3) Tr v k t qu phép hi u c a hai t p h p Set và subtract(Set, Delete, Delete là Result (là t p Set sau khi ã xoá h t các Result) ph n t c a Delete có m t trong ó). Tr v k t qu phép h p c a hai t p h p Set1 và union(Set1, Set2, Set3) Set2 là Set3. Ki m tra t p h p Subset có là t p h p con c a Set subset(Subset, Set) hay không. III. Các thao tác cơ b n trên danh sách III.1. Xây d ng l i m t s v t có s n Sau ây ta s trình bày m t s thao tác cơ b n trên danh sách b ng cách xây d ng l i m t s v t có s n c a Prolog. III.1.1. Ki m tra m t ph n t có m t trong danh sách Prolog ki m tra m t ph n t có m t trong m t danh sách như sau : member(X, L) trong ó, X là m t ph n t và L là m t danh sách. ích member(X, L) ư c tho mãn n u X xu t hi n trong L. Ví d : ?- member( b, [ a, b, c ] ) Yes ?- member( b, [ a, [ b, c ] ] ) No ?- member( [ b, c], [ a, [ b, c ] ] ) Yes T các k t qu trên, ta có th gi i thích quan h member(X, L) như sau :
100 L p trình lôgic trong Prolog Ph n t X thu c danh sách L n u : 1. X là u c a L, ho c n u 2. X là m t ph n t c a uôi c a L. Ta có th vi t hai i u ki n trên thành hai m nh , m nh th nh t là m t s ki n ơn gi n, m nh th hai là 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. Ghép hai danh sách ghép hai danh sách, Prolog có hàm : append( L1, L2, L3). trong ó, L1 và L2 là hai danh sách, L3 là danh sách k t qu c a phép ghép L1 và L2. Ví d : ?- append( [ a, b ], [ c, d ], [ a, b, c, d ] ). Yes ?- append( [ a, b ], [ c, d ], [ a, b, a, c ] ). No [ X | L1 ] X L1 L2 L3 X L3 [ X | L3 ] Hình III.1. Ghép hai danh sách [ X | L1 ] và L2 thành [ X | L3 ]. Hàm append ho t ng ph thu c tham i u tiên L1 theo cách như sau : 1. N u tham i u tiên là danh sách r ng, thì tham i th hai và th ba ph i là m t danh sách duy nh t, g i là L. Ta vi t trong Prolog như sau : append( [ ], L, L). 2. N u tham i u tiên c a append là danh sách khác r ng, thì nó g m m t u và m t uôi như sau [ X | L1 ]
101 C u trúc danh sách K t qu phép ghép danh sách là danh sách [ X | L3 ], v i L3 là phép ghép c a L1 và L2. Ta vi t trong Prolog như sau : append( [ X | L1 ], L2, [ X | L3 ] ) :- append( L1, L2, L3 ). Hình 4.2 minh ho phép ghép hai danh sách [ X | L1 ] và L2. Ta có các ví d 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 ] Th t c append ư c s d ng r t m m d o theo nhi u cách khác nhau. Ch ng h n Prolog ưa ra b n phương án phân tách m t danh sách ã cho thành hai danh sá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 S d ng append, ta cũng có th tìm ki m m t s ph n t trong m t danh sách. Ch ng h n, t danh sách các tháng trong năm, ta có th tìm nh ng tháng ng trư c m t tháng ã cho, gi s thá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 Tháng ng ngay trư c và tháng ng ngay sau tháng năm nh n ư c như sau : ?- append( _, [ Month1, may, Month2 | _ ] , [ jan, fev, mar, avr, may, jun, jul, aut, sep, oct, nov, dec ] ).
102 L p trình lôgic trong Prolog Month1 = avr Month2 = jun Yes Bây gi cho trư c danh sách : L1 = [ a, b, z, z, c, z, z, z, d, e ] Ta c n xóa các ph n t ng sau ba ch z liên ti p, k c 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 ] member1( b, [ a, b, c ] ) append( L1, [ b | L2 ], [ a, b, c ] ) M nh 1 c a append M nh 2 c 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 b i vì b ≠ a T ó kéo theo : X = a, L3’ = [ b, c ] append( L1’, [ b | L2 ], [ b, c ] ) M nh 1 c a append So kh p : L1’ = [ ] [ b | L2 ] = [ b, c ] T ó kéo theo : L2 = [ c ] thành công Hình III.2. Th t c member1 tìm tu n t m t i tư ng trong danh sách ã cho. Trư c ây ta ã nh nghĩa quan h member( X, L ) ki m tra m t ph n t X có m t trong m t danh sách L không. Bây gi b ng cách s d ng append, ta có th nh nghĩa l i member như sau : member1( X, L ) :- append( L1, [ X | L2], L).
103 C u trúc danh sách M nh này có nghĩa : n u X có m t trong danh sách L thì L có th ư c phân tách thành hai danh sách, v i X là u c a danh sách th hai. nh nghĩa member1 hoàn toàn tương ương v i nh nghĩa member. ây ta s d ng hai tên khác nhau phân bi t hai cách cài t Prolog. Ta cũng có th nh nghĩa l i member1 b ng cách s d ng bi n n c danh (anonymous variable) : member1( X, L ) :- append( _ , [ X | _ ], L). So sánh hai cách cài t khác nhau v quan h thành viên, ta nh n th y nghĩa th t c trong nh nghĩa member ư c th hi n r t rõ : Trong member, ki m tra ph n t X có m t trong m t danh sách L không, 1. Trư c tiên ki m tra ph n t u c a L là ng nh t v i X, n u không, 2. Ki m tra r ng X có m t trong ph n uôi c a L. Nhưng trong trư ng h p nh nghĩa member1, ta th y hoàn toàn nghĩa khai báo mà không có nghĩa th t c. hi u ư c cách member1ho t ng như th nào, ta hãy xem xét quá trình Prolog th c hi n câu h i : ?- member1( b, [ a, b, c ] ). Cách tìm c a th t c member1 trên ây tương t member, b ng cá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 sách ã c n. III.1.3. B sung m t ph n t vào danh sách Phương pháp ơn gi n nh t b sung m t ph n t vào danh sách là t nó v trí u tiên, nó tr thành u. N u X là m t i tư ng m i, còn L là danh sách c n b sung thêm, thì danh sách k t qu s là : [X|L] Ngư i ta không c n vi t th t c b sung m t ph n t vào danh sách. B i vì vi c b sung có th ư c bi u di n dư i d ng m t s ki n n u c n : insert( X, L, [ X | L ] ). III.1.4. Lo i b m t ph n t kh i danh sách lo i b m t ph n t X kh i danh sách L, ngư i ta xây d ng quan h : remove( X, L, L1 ) trong ó, L1 ng nh t v i L, sau khi X b lo i b kh i L. Th t c remove có c u trúc tương t member. Ta có th l p lu n như sau 1. N u ph n t X là u c a danh sách, thì k t qu là uôi c a danh sách.
104 L p trình lôgic trong Prolog 2. N u không, tìm cách lo i b X kh i ph n uôi c a danh sách. remove( X, [ X | Tail ], Tail ). remove( X, [ Y | Tail ], [ Y | Tail1 ] ) :- remove( X, Tail, Tail1 ). Tương t th t c member, th t c remove mang tính không xác nh. N u có nhi u ph n t là X có m t trong danh sách, thì remove có th xoá b t kỳ ph n t nào, do quá trình quay lui. Tuy nhiên, m i l n th c hi n, remove ch xoá m t ph n t là X mà không ng n nh ng ph n t khác. Ví d : [ a, b, a, a ], L ). ?- remove( a, L = [ b, a, a ]; L = [ a, b, a ]; L = [ a, b, a ] No Th t c remove th t b i n u danh sách không ch a ph n t c n xoá. Ngư i ta có th s d ng remove trong m t khía c nh khác, m c ích b sung m t ph n t m i vào b t c âu trong danh sách. Ví d , n u ta mu n t ph n t a vào t i m i v trí b t kỳ trong danh sách [ 1, 2, 3 ], ch c n t câu h i : Cho bi t danh sách L n u sau khi xoá a, ta nh n ư c danh sách [ 1, 2, 3 ] ? [ 1, 2, 3 ] ). ?- remove( a, L, L = [ a, 1, 2, 3 ]; L = [ 1, a, 2, 3 ]; L = [ 1, 2, a, 3 ]; L = [ 1, 2, 3, a ] No M t cách t ng quát, phép toán chèn insert m t ph n t X vào m t danh sách List ư c nh nghĩa b i th t c remove b ng cách s d ng m t danh sách l n hơn LargerList làm tham i th hai : insert( X, List, LargerList ) :- remove( X, LargerList, List ). Ta ã nh nghĩa quan h thu c v trong th t c member1 b ng cách s d ng th t c append. Tuy nhiên, ta cũng có th nh nghĩa l i quan h thu c v trong th t c m i member2 b i th t c remove b ng cách xem m t ph n t X thu c v m t danh sách List n u X b xoá kh i List : member2( X, List ) :- remove( X, List, _ ).
105 C u trúc danh sách III.1.5. Ngh ch o danh sách S d ng append, ta có th vi t th t c ngh ch o m t danh sá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 Sau ây là m t th t c khác ngh ch o m t danh sách nhưng có s d ng hàm b tr trong thân th t 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 d ng reverse, ta có th ki m tra m t danh sách có là i x ng (palindrome) hay không : palindrome(L) :- reverse( L, L ). ?- palindrome([ a, b, c , d, c, b, a ]). Yes III.1.6. Danh sách con Ta xây d ng th t c sublist nh n hai tham i là hai danh sách L và S sao cho S là danh sách con c 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 lý xây d ng th t c sublist tương t th t c member1, m c dù ây quan h danh sách con t ng quát hơn.
106 L p trình lôgic trong Prolog L member( X, L ) L1 X L2 L [ X | L2 ] sublist( S, L ) L1 S L3 L2 Hình III.3. Các quan h member và sublist. Quan h danh sách con ư c mô t như sau : S là m t danh sách con c a L n u : 1. Danh sách L có th ư c phân tách thành hai danh sách L1 và L2, và n u 2. Danh sách L2 có th ư c phân tách thành hai danh sách S và L3. Như ã th y, vi c phân tách các danh sách có th ư c mô t b i quan h ghép append. Do ó ta vi t l i trong Prolog như sau : sublist( S, L ) :- append( L1, L2, L ), append( S, L3, L2 ). Ta th y th t c sublist r t m m d o và do v y có th s d ng theo nhi u cách khác nhau. Ch ng h n ta có th li t kê m i danh sách con c a m t danh sách ã cho như sau : ?- sublist( S, [ a, b, c ] ). S = [ ]; S = [ a ]; S = [ a, b ]; S = [ a, b, c ]; S = [ b ]; ... III.2. Hoán v ôi khi, ta c n t o ra các hoán v c a m t danh sách. Ta xây d ng quan h permutation có hai tham bi n là hai danh sách, mà m t danh sách là hoán v c a danh sách kia. Ta s t n d ng phép quay lui như sau : ?- permutation( [ a, b, c ], P ). P = [ a, b, c ]; P = [ a, c, b ];
107 C u trúc danh sách P = [ b, a, c ]; ... Nguyên lý ho t ng c a th t c swap d a trên hai trư ng h p phân bi t, tuỳ theo danh sách th nh t : 1. N u danh sách th nh t r ng, thì danh sách th hai cũng ph i r ng. 2. N u danh sách th nh t khác r ng, thì nó s có d ng [ X | L ] và ư c ti n hành hoán v như sau : trư c tiên hoán v L nh n ư c L1, sau ó chèn X vào t t c các v trí trong L1. X L hoán v L L1 L1 là m t hoán v c a L Chèn X t i m t v trí nh n ư c m t hoán v c a [ X | L ] Hình III.4. M t cách xây d ng hoán v permutation c a danh sách [ X | L ]. Ta nh n ư c hai m nh tương ng v i th t c như sau : permutation( [ ], [ ] ). permutation( [ X | L ], P ) :- permutation( L, L1 ), insert( X, L1, P ). M t phương pháp khác là lo i b ph n t X kh i danh sách u tiên, hoán v ph n còn l i c a danh sách này nh n ư c danh sách P, sau ó thêm X vào ph n u c a P. Ta có chương trình khác permutation2 như sau : permutation2( [ ], [ ] ). permutation2( L, [ X | P ] ) :- remove( X, L, L1 ), permutation2( L1, P ). T ây, ta có th khai thác th t c hoán v , ch ng h n (chú ý khi ch y Arity Prolog c n gõ và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 d ng permutation theo cách khác như sau :
108 L p trình lôgic trong Prolog ?- permutation( L, [ a, b, c ] ). Prolog s ràng bu c liên ti p cho L ưa ra 6 hoán v khác nhau có th . Tuy nhiên, n u NSD yêu c u m t gi i pháp khác, Prolog s không bao gi tr l i “No”, mà rơi vào m t vòng l p vô h n do ph i tìm ki m m t hoán v m i mà th c ra không t n t i. Trong trư ng h p này, th t c permutation2 ch tìm th y m t hoán v th nh t, sau ó ngay l p t c rơi vào m t vòng l p vô h n. Vì v y, c n chú ý khi s d ng các quan h hoán v này. III.3. M t s ví d v danh sách III.3.1. S p x p các ph n t c a danh sách Xây d ng th t c s p x p các ph n t có c a m t danh sách b ng phương pháp chè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 dài c a m t danh sách Xây d ng th t c tính dài hay m s lư ng các ph n t có m t trong m t danh sách ã cho như sau : length( L, N ). X y ra hai trư ng h p :
109 C u trúc danh sách 1. N u danh sách r ng, thì dài N = 0. 2. N u danh sách khác r ng, thì nó ư c t o thành t danh sách có d ng : [ head | queue ] và có dài b ng 1 c ng v i dài c a queue. Ta có chương trình Prolog như sau : length( [ ], 0 ). length( [ _ | Queue ], N ) :- length(Queue, N1 ), N is 1 + N1. K t qu ch 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 c a ph n thân là không th hoán i cho nhau, vì r ng N1 ph i ư c ràng bu c trư c khi th c hi n ích : N is 1 + N1 Ch ng h n, n u g i trace, quá trình th c hi n length( [ 1, 2, 3 ], N ) như sau : g i (0) length([1, 2, 3], N) -> g i (1) length([2, 3], N’) -> g i (2) length([3], N’’) -> g i (3) length([ ], N’’’) -> N’’’ = 0 g i (4) N’’ is 1 + 0 -> N’’ = 1 g i (5) N’ is 1 + 1 -> N’ = 2 (6) gi N is 1 + 2 -> N=3 V i is, ta ã ưa vào m t quan h nh y c m v i th t th c hi n các ích, và do v y không th b qua y u t th t c trong chương trình. i u gì s x y ra n u ta không s d ng is trong chương trình. Ch ng h n : length1( [ ], 0 ). length1( [ _ | Queue ], N ) :- length1( Queue, N1 ), N = 1 + N1. Lúc này, n u g i : ?- length1( [ a, [ b, c ], d, e ], N ).