Tổng số phần tử trong danh sách trong Prolog

Question

list_sum([], 0). 
list_sum([Head | Tail], TotalSum) :- 
    list_sum(Tail, Sum1), 
    Total = Head + Sum1. 

Mã này trả về true. Nếu tôi thay thế Total = Head + Sum1 bằng Total is Head + Sum1, thì nó sẽ trả về giá trị. Nhưng những gì tôi nên thay thế nó để có được kết quả như thế này:

?- list_sum([1,2,0,3], Sum). 
Sum = 1+2+0+3 ; % not to return value 6!!! 

Answer 1

Lưu ý rằng trong điều khoản thứ hai của thủ tục của bạn TotalSum không bao giờ được khởi tạo. Bạn sẽ nhận được cảnh báo của người phiên dịch khi tham khảo mã của bạn.

Dưới đây là gợi ý của tôi:

list_sum([Item], Item). 
list_sum([Item1,Item2 | Tail], Total) :- 
    list_sum([Item1+Item2|Tail], Total). 

Các thỏa thuận điều khoản đầu tiên với trường hợp cơ sở, khi chỉ có một yếu tố còn lại trong danh sách, đó là kết quả của bạn.

Điều khoản thứ hai đề cập đến bước đệ quy. Nó lấy hai mục đầu tiên của danh sách và thực hiện một cuộc gọi đệ quy thay thế hai mục đó bằng một thuật ngữ mới Item1 + Item2.

Answer 2

Nếu bạn muốn chuyển đổi một danh sách các số vào một biểu thức phụ gia, từ

[1,2,3] 

để

1 + 2 + 3

bạn có thể làm một cái gì đó như thế này, sử dụng một cái gì đó như a danh sách chênh lệch:

list_to_additive_expr([] , 0). 
list_to_additive_expr([X|Xs] , X + RHS) :- 
    sum_of(Xs , RHS). 

Ngoài ra, bạn có thể sử dụng một ắc:

list_to_additive_expr(Xs , Expr) :- 
    list_to_additive_expr(Xs , 0 , Expr) 
    . 

list_to_additive_expr([]  , Expr , Expr) . 
list_to_additive_expr([X|Xs] , RHS , Expr) :- 
    sum_of(Xs , X + RHS , Expr) 
    . 

Tôi tin rằng bạn sẽ tìm thấy phong cách đầu tiên là không đúng đuôi đệ quy và như vậy sẽ không được tối ưu hóa thành một vòng qua đuôi đệ quy tối ưu hóa (TRO) — và vì vậy, nếu danh sách đủ dài, sẽ bị tràn ngăn xếp. Cách tiếp cận thứ hai nên có TRO được áp dụng và nên làm việc cho các danh sách có độ dài bất kỳ.

TRO là gì, bạn có thể hỏi? Dưới đây là Wikipedia with an answer for you:

Trong khoa học máy tính, một cuộc gọi đuôi là lời kêu gọi chương trình con điều đó xảy ra bên trong một thủ tục và tạo ra một giá trị trả về, sau đó được ngay lập tức quay trở lại bởi các thủ tục gọi . Trang web cuộc gọi sau đó được cho là ở vị trí đuôi, tức là vào cuối quy trình gọi điện. Nếu một chương trình con thực hiện một cuộc gọi đuôi cho chính nó, nó được gọi là đuôi đệ quy. Đây là trường hợp đặc biệt của đệ quy.

Cuộc gọi đuôi rất quan trọng vì chúng có thể được triển khai mà không cần thêm khung ngăn xếp mới vào ngăn xếp cuộc gọi. Hầu hết các khung của thủ tục hiện tại là không cần thiết bất kỳ nhiều hơn, và nó có thể được thay thế bằng khung của cuộc gọi đuôi, sửa đổi khi thích hợp (tương tự như lớp phủ cho quy trình, nhưng cho các cuộc gọi chức năng). Sau đó, chương trình có thể nhảy tới chương trình con được gọi.Tạo mã như vậy thay vì chuỗi cuộc gọi chuẩn được gọi là loại bỏ cuộc gọi đuôi hoặc tối ưu hóa cuộc gọi đuôi.

Answer 3

Câu trả lời rất đơn giản:

sum_list([], 0). 
sum_list([H|T], Sum) :- 
    sum_list(T, Rest), 
    Sum is H + Rest. 

Mã này hoạt động chỉ trong một hướng - điều này có nghĩa - nó không cho phép bạn tạo danh sách với số tiền xác định. Nhưng kể từ khi tập hợp các danh sách như vậy là vô hạn, điều đó sẽ không thực tế.

Answer 4

Trong Prolog (+)/2 là một toán tử nhị phân infix. Điều này cho phép chúng tôi viết A+B thay vì +(A,B).

 
?- current_op(_,yfx,+). % left-associative binary infix operator 
true. 

(+)/2 cộng sự sang trái, vì vậy 1+2+3 là viết tắt của (1+2)+3.

(.)/2 liên kết với số phải, vì vậy [1,2,3] viết tắt là .(1,.(2,.(3,[]))).

Để có được parenthesization đúng, chúng tôi sử dụng một vị phụ trợ với một thêm "cho ác" đối số: truy vấn

list_sum([X|Xs],S) :- 
    list_sum0_sum(Xs,X,S). 

list_sum0_sum([], S ,S). 
list_sum0_sum([X|Xs],S0,S) :- 
    list_sum0_sum(Xs,S0+X,S). 

mẫu:

?- list_sum([1,2,0,3],S). 
S = 1+2+0+3. 

Answer 5

Chương trình này là

list_sum([],0). 

list_sum([Head|Tail], TotalSum):- 
list_sum(Tail, Sum1), 
TotalSum is Head+Sum1. 

nay nếu truy vấn là

?- list_sum([1,2,3,4], Sum). 

Câu trả lời là

Sum = 10