Tính công việc được thực hiện bởi f x = (x, x)

Question

Hãy nói rằng tôi có chức năng này: (Haskell cú pháp)

f x = (x,x) 

công việc là gì (số lượng tính toán) được thực hiện bởi các chức năng?

Lúc đầu, tôi nghĩ rằng nó rõ ràng là không đổi, nhưng nếu loại x không phải là hữu hạn, có nghĩa là, x có thể mất một số lượng tùy ý của bộ nhớ? Một trong những sẽ phải đưa vào tài khoản công việc thực hiện bằng cách sao chép x là tốt, phải không?

Điều này khiến tôi tin rằng công việc được thực hiện bởi hàm thực sự tuyến tính với kích thước của đầu vào.

Đây không phải là bài tập về nhà cho chính nó, nhưng đã đưa ra khi tôi đã có để xác định việc thực hiện bởi các chức năng:

f x = [x] 

Trong đó có một vấn đề tương tự, tôi tin.

Answer 1

Rất không chính thức, công việc đã hoàn thành phụ thuộc vào ngữ nghĩa hoạt động của ngôn ngữ của bạn. Haskell, tốt, đó là lười biếng, vì vậy bạn phải trả yếu tố duy nhất liên tục để:

• con trỏ push to x trên stack
• phân bổ một tế bào đống cho (,)
• áp dụng (,) để đối số của nó
• trở lại một con trỏ tới ô heap

Xong. O (1) hoạt động, được thực hiện khi người gọi xem kết quả của f.

Bây giờ, bạn sẽ kích hoạt đánh giá thêm nếu bạn nhìn vào bên trong (,) - và công việc đó phụ thuộc vào công việc để tự đánh giá x. Vì trong Haskell, các tham chiếu đến x được chia sẻ, bạn chỉ đánh giá nó một lần.

Vì vậy, công việc trong Haskell là O (công việc của x) nếu bạn đánh giá đầy đủ kết quả. Chức năng của bạn f chỉ thêm các yếu tố không đổi.

Answer 2

Chris Okasaki có một phương pháp tuyệt vời để xác định công việc tính phí cho cuộc gọi chức năng khi một số (hoặc tổng số) laziness được giới thiệu. Tôi tin rằng đó là trong bài báo của ông về các cấu trúc dữ liệu hoàn toàn chức năng. Tôi biết nó có trong phiên bản sách - tôi đọc phần đó của cuốn sách tháng trước. Về cơ bản bạn tính một yếu tố không đổi cho lời hứa/thunk tạo ra, không có gì để đánh giá bất kỳ thông qua trong lời hứa/thunks (giả sử họ đã bị buộc/đang ở dạng bình thường [không chỉ WHNF]). Đó là một đánh giá thấp. Nếu bạn muốn một khoản phí quá cao cũng là chi phí của việc buộc/chuyển đổi thành dạng bình thường mỗi lời hứa/thunk được tạo ra bởi hàm. Ít nhất, đó là cách tôi nhớ nó trong trạng thái cực kỳ mệt mỏi của tôi.

Tra cứu nó ở Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis - Tôi thề rằng luận án được sử dụng có thể tải xuống được.