Trong Haskell, hiệu suất và nơi ràng buộc

Question

Tôi chỉ học Haskell và viết hai chương trình từ một trang web hướng dẫn, chẳng hạn rằng

maximumnowhere :: (Ord a) => [a] -> a 
maximumnowhere [] = error "empty" 
maximumnowhere [x] = x 
maximumnowhere (x:xs) = if x > maximumnowhere xs then x else maximumnowhere xs 

và

maximumwhere :: (Ord a) => [a] -> a 
maximumwhere [] = error "empty" 
maximumwhere [x] = x 
maximumwhere (x:xs) = if x > maximum' then x else maximum' where maximum' = maximumwhere xs 

Tôi nghĩ hai chương trình này là khá tương đương, bởi vì tôi nghĩ, nơi mà ràng buộc chỉ thay thế biến với nội dung của nó. nhưng khi tôi chạy nó trong ghci, cái đầu tiên chậm hơn cái thứ hai, đặc biệt là với một mảng có chiều dài trên 25. Có lẽ, nơi mà ràng buộc tạo ra sự khác biệt lớn về hiệu năng này, nhưng tôi không biết tại sao. Bất cứ ai có thể giải thích nó cho tôi?

Answer 1

Không, chúng không tương đương. let và where giới thiệu sharing, có nghĩa là giá trị chỉ được đánh giá một lần. Trình biên dịch nói chung sẽ không chia sẻ kết quả của hai biểu thức giống hệt nhau trừ khi bạn nói với nó, bởi vì nó không thể nói chung về việc liệu không gian-thời gian thương mại-off của việc này có mang lại lợi ích hay không.

Như vậy, chương trình đầu tiên của bạn sẽ thực hiện hai cuộc gọi đệ quy mỗi lần lặp, làm cho nó O (2^n), trong khi thứ hai chỉ làm một mỗi lần lặp, ví dụ: O (n). Sự khác biệt giữa chúng là rất lớn. Tại n = 25, kết quả chương trình đầu tiên trong hơn 33 triệu cuộc gọi đệ quy trong khi thứ hai chỉ thực hiện 25.

Vì vậy, đạo đức của câu chuyện là nếu bạn muốn chia sẻ, bạn cần phải yêu cầu nó bằng cách sử dụng let hoặc where.