9
Tôi tự hỏi nếu oCaml tối ưu hóa mã này để được đệ quy đuôi và nếu như vậy F #?Chức năng này có sử dụng đệ quy đuôi không?
let rec sum xs =
match xs with
| [] -> 0
| x :: xs' -> x + sum xs'
A
Trả lời
13
Trong trường hợp đệ quy (tức là trường hợp xs không trống) thao tác được đánh giá lần cuối là phần bổ sung. Đối với hàm để đệ quy đuôi, thao tác được đánh giá lần cuối cần phải là lời gọi đệ quy để tính tổng.
Các chức năng như thế này thường được định nghĩa bằng cách sử dụng hàm trợ giúp với bộ tích lũy để làm cho chúng có tính đệ quy đuôi. Trong trường hợp này, đó sẽ là một hàm lấy danh sách được tổng hợp và giá trị hiện tại của tổng. Nếu danh sách trống, nó sẽ trả về giá trị hiện tại của tổng. Nếu danh sách không trống, nó sẽ tự gọi chính nó với đuôi của danh sách và giá trị hiện tại của tổng + đầu của danh sách dưới dạng đối số. Hàm tổng hợp sau đó sẽ chỉ gọi hàm trợ giúp với danh sách và 0 là giá trị hiện tại của tổng.
5
Không, mã này không phải là đệ quy đuôi và ocaml sẽ không biến đổi. Bạn phải làm điều đó cho chính bản thân mình.
Tôi không biết về F #, nhưng tôi nghi ngờ nó sẽ tối ưu hóa điều này.
Có, do đó, nó không âm thanh khó cho oCaml để tối ưu hóa. Chỉ cần thêm một param hiện tại và gọi tổng xs ', currentSum. Biết đơn giản của nó, tôi muốn biết nếu nó tối ưu hóa. Vì vậy, bạn nói nó doesnt hmm .. Tôi không có thùng oCaml trên máy này vì vậy tôi không thể kiểm tra và biết tại sao nó sẽ hoặc wouldnt. –
@ acidzombie24 Nó có thể tối ưu hóa trong trường hợp này, nhưng nếu bạn dựa vào nó, bạn sẽ gặp phải tràn bộ đệm trên các trường hợp phức tạp hơn một chút, nơi trình biên dịch không thể thực hiện phép chuyển đổi. Ví dụ, bạn có thể mong đợi sự chuyển đổi tương tự với một hàm thuần túy từ một mô-đun khác, và bạn sẽ có quyền mong đợi nó, nhưng trình biên dịch sẽ không thể thực hiện phép biến đổi do biên dịch riêng biệt và vì các giao diện không chỉ định các hàm nào nguyên chất. –