không tầm thường Prolog tìm và thay thế

Question

Vì vậy, chúng ta có thể dễ dàng tìm và thay thế một nguyên tử với một nguyên tử trong Prolog bằng cách làm một cái gì đó như:

replace([],A,B,[]). 
replace([H|T],A,B,[B|Result]) :- 
    H=A, 
    replace(T,A,B,Result),!. 
replace([H|T],A,B,[H|Result]) :- 
    replace(T,A,B,Result). 

Tôi chắc rằng có nhiều cách khác để làm điều này quá.

Tuy nhiên, tôi muốn làm điều gì đó phức tạp hơn trong logic trong tính toán. Làm thế nào bạn sẽ làm một cái gì đó như thay thế các liên từ như conj(x,y) trong một tuyên bố hợp lý chỉ với (x, y)? Vì vậy, nó giống như cuối cùng và thay thế nhưng không phải với các nguyên tử. Vì vậy, chúng tôi có thể có một cái gì đó như reduce(conj(conj(x,y),z)). mà tôi muốn giảm xuống ((x,y),z).

Đây là ví dụ đơn giản chỉ với các liên từ nhưng đây là những gì tôi muốn xảy ra trong trường hợp liên kết. Nếu ai đó quan tâm, đây là tất cả về logic mô tả và phương pháp hoạt cảnh.

Những gì tôi đang bối rối về nó như thế nào bạn đi về làm một tìm và thay thế khi đầu vào không thực sự là một danh sách; đó là một cấu trúc. Tôi không thấy làm thế nào bạn có thể giải quyết điều này mà không cần sử dụng thủ thuật tiêu chuẩn [H|T] với đệ quy và danh sách. Có ai có ý tưởng nào?

Rất cám ơn.

Answer 1

này được thực hiện một cách đơn giản bằng cách viết một meta-phiên dịch, chẳng hạn như sau:

replace(V, V) :- 
    % pass vars through 
    var(V), !.  
replace(A, A) :- 
    % pass atoms through 
    atomic(A), !. 
replace([], []) :- 
    % pass empty lists through 
    !. 
replace([X|Xs], [Y|Ys]) :- 
    % recursively enter non-empty lists 
    !, 
    replace(X, Y), 
    replace(Xs, Ys). 
replace(conj(X,Y), (NX,NY)) :- 
    % CUSTOM replacement clause for conj/2 
    !, 
    replace(X, NX), 
    replace(Y, NY). 
replace(T, NT) :- 
    % finally, recursively enter any as yet unmatched compound term 
    T =.. [F|AL], 
    replace(AL, NAL), 
    NT =.. [F|NAL]. 

Lưu ý các điều khoản cuối cùng thứ hai, phục vụ để thực hiện một sự thay thế của trường hợp cụ thể của bạn thay thế conj/2 với kết hợp, ,/2. Bạn có thể thêm nhiều mệnh đề khác theo cách tương tự như thế này để thực hiện thay thế thuật ngữ nói chung, vì phần còn lại của định nghĩa (tất cả các mệnh đề khác của replace/2) ở đây sẽ phân tích đệ quy bất kỳ thuật ngữ nào của PROLOG. các loại; vars, nguyên tử và các thuật ngữ phức hợp (kể cả các danh sách một cách rõ ràng).

Thực thi này trong trường hợp bạn mang đến cho chúng ta:

?- replace(conj(conj(x,y),z), NewTerm). 
NewTerm = ((x, y), z). 

Lưu ý rằng định nghĩa này sẽ thực hiện việc thay thế đúng của bất kỳ điều khoản lồng nhau đến độ sâu tùy ý trong thời hạn khác.

Answer 2

Bạn có thể chuyển cụm từ chung thành danh sách bằng cách sử dụng =.., ví dụ:

?- conj(conj(x,y),z) =.. List. 
List = [conj, conj(x, y), z]. 

Làm điều này đệ quy, bạn có thể làm phẳng toàn bộ thời hạn.

Một vị nói chung rằng những thay đổi nút nào đó trong tương lai đầu vào sẽ giống như thế này:

change_term(NodeChanger, Term1, Term3) :- 
    call(NodeChanger, Term1, Term2), 
    change_term(NodeChanger, Term2, Term3), 
    !. 

change_term(NodeChanger, Term1, Term2) :- 
    Term1 =.. [Functor | SubTerms1], 
    change_termlist(NodeChanger, SubTerms1, SubTerms2), 
    Term2 =.. [Functor | SubTerms2]. 


change_termlist(_, [], []). 

change_termlist(NodeChanger, [Term1 | Terms1], [Term2 | Terms2]) :- 
    change_term(NodeChanger, Term1, Term2), 
    change_termlist(NodeChanger, Terms1, Terms2). 

Nếu bây giờ bạn định nghĩa:

conj_changer(conj(X, Y), (X, Y)). 

sau đó bạn có thể xác định bạn giảm-ngữ theo:

reduce(Term1, Term2) :- 
    change_term(conj_changer, Term1, Term2). 

Cách sử dụng:

?- reduce(conj(conj(x,y),z), ReducedTerm). 
ReducedTerm = ((x, y), z). 

Bạn phải cẩn thận dù cách bạn xác định NodeChanger, một số định nghĩa nhất định có thể thực hiện vòng lặp change_term/3. Có lẽ ai đó có thể cải thiện điều đó.

Answer 3

Hãy nhớ lại rằng danh sách chỉ là một loại cấu trúc nhất định, vì vậy bạn có thể dễ dàng dịch mã của mình để khớp với bất kỳ cấu trúc nào khác. Nó có thể giúp bạn sử dụng một đại diện sạch hơn cho dữ liệu của bạn: Cũng giống như bạn sử dụng conj/2 để biểu thị liên từ, bạn có thể giới thiệu một var functor/1 để biểu thị biến:

reduce(conj(X0,Y0), (X,Y)) :- 
     reduce(X0, X), 
     reduce(Y0, Y). 
reduce(var(X), X). 

Ví dụ:

?- reduce(conj(conj(var(x),var(y)), var(z)), R). 
R = ((x, y), z).