Đánh giá lười biếng không tầm thường

Question

Tôi hiện đang tiêu hóa bản trình bày đẹp Tại sao nên tìm hiểu Haskell? bởi Keegan McAllister. Ở đó, ông sử dụng đoạn mã

minimum = head . sort 

như một minh chứng đánh giá lười biếng Haskell bằng cách tuyên bố rằng minimum có thời gian phức tạp O (n) trong Haskell. Tuy nhiên, tôi nghĩ rằng ví dụ là loại học thuật trong tự nhiên. Do đó, tôi yêu cầu một ví dụ thực tế hơn, trong đó không rõ ràng là hầu hết các tính toán trung gian đều bị loại bỏ.

Answer 1

• Bạn đã bao giờ viết AI chưa? Không phải là nó gây phiền nhiễu mà bạn phải cắt tỉa thông tin thread (ví dụ: chiều sâu tối đa, chi phí tối thiểu của một chi nhánh liền kề, hoặc các thông tin khác) thông qua chức năng duyệt cây? Điều này có nghĩa là bạn phải viết một cây chuyển động mới mỗi khi bạn muốn cải thiện AI của bạn. Đó là câm. Với việc đánh giá lười biếng, điều này không còn là vấn đề nữa: hãy viết chức năng duyệt cây của bạn một lần, để tạo ra một cây trò chơi khổng lồ (thậm chí vô hạn!), Và để người tiêu dùng của bạn quyết định mức tiêu thụ của nó.

• Viết GUI có hiển thị nhiều thông tin? Bạn muốn nó chạy nhanh? Trong các ngôn ngữ khác, bạn có thể phải viết mã chỉ hiển thị các cảnh hiển thị. Trong Haskell, bạn có thể viết mã để hiển thị toàn bộ cảnh và sau đó chọn các pixel cần quan sát. Tương tự, dựng hình một cảnh phức tạp? Tại sao không tính toán chuỗi cảnh vô tận ở các mức độ chi tiết khác nhau và chọn một cảnh phù hợp nhất khi chương trình chạy?

• Bạn viết hàm đắt tiền và quyết định ghi nhớ tốc độ. Trong các ngôn ngữ khác, điều này đòi hỏi phải xây dựng một cấu trúc dữ liệu theo dõi đầu vào nào cho hàm mà bạn biết câu trả lời và cập nhật cấu trúc khi bạn thấy các đầu vào mới. Hãy nhớ để làm cho nó thread an toàn - nếu chúng ta thực sự cần tốc độ, chúng ta cần song song, quá! Trong Haskell, bạn xây dựng một cấu trúc dữ liệu vô hạn, với một mục nhập cho mỗi đầu vào có thể, và đánh giá các phần của cấu trúc dữ liệu tương ứng với các đầu vào mà bạn quan tâm. Chủ đề an toàn đi kèm miễn phí với độ tinh khiết.

• Đây là một trong số đó có lẽ là một chút prosaic hơn những người trước đó. Bạn đã bao giờ tìm thấy thời điểm khi && và || không phải là thứ duy nhất bạn muốn bị đoản mạch? Tôi chắc chắn có! Ví dụ, tôi thích hàm <|> để kết hợp các giá trị Maybe: nó lấy giá trị đầu tiên của đối số thực sự có giá trị. Vì vậy, Just 3 <|> Nothing = Just 3; Nothing <|> Just 7 = Just 7; và Nothing <|> Nothing = Nothing. Hơn nữa, nó ngắn mạch: nếu nó chỉ ra rằng đối số đầu tiên của nó là một Just, nó sẽ không bận tâm làm việc tính toán cần thiết để tìm ra đối số thứ hai của nó là gì.

  Và <|> không được tích hợp sẵn trong ngôn ngữ; nó được thư viện giải quyết. Đó là: sự lười biếng cho phép bạn viết các hình thức mạch ngắn mới. (Trên thực tế, trong Haskell, ngay cả những hành vi ngắn mạch của (&&) và (||) không được xây dựng trong trình biên dịch ma thuật: họ nảy sinh một cách tự nhiên từ ngữ nghĩa của ngôn ngữ cộng với định nghĩa của chúng trong các thư viện chuẩn.)

Nói chung, chủ đề chung ở đây là bạn có thể tách riêng việc tạo ra các giá trị từ việc xác định giá trị nào là thú vị khi xem. Điều này làm cho mọi thứ trở nên phức tạp hơn, bởi vì việc lựa chọn những gì thú vị để xem xét không cần phải được nhà sản xuất biết đến.

Answer 2

Xem xét tạo và tiêu thụ các thành phần n đầu tiên của một chuỗi vô hạn. Nếu không có đánh giá lười biếng, mã hóa ngây thơ sẽ chạy mãi mãi trong bước thế hệ, và không bao giờ tiêu thụ bất cứ điều gì. Với việc đánh giá lười biếng, chỉ có nhiều phần tử được tạo ra khi mã cố gắng tiêu thụ.

Answer 3

Đây là một ví dụ nổi tiếng mà tôi đã đăng lên một chủ đề khác hôm qua. Số Hamming là các số không có bất kỳ số nguyên tố lớn hơn 5. I.e. họ có dạng 2^i * 3^j * 5^k. 20 đầu tiên trong số đó là:

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36] 

Một 500000 là:

1962938367679548095642112423564462631020433036610484123229980468750 

các chương trình in một 500000 (sau một thời gian ngắn tính toán) là:

merge xxs@(x:xs) yys@(y:ys) = 
    case (x`compare`y) of 
    LT -> x:merge xs yys 
    EQ -> x:merge xs ys 
    GT -> y:merge xxs ys 

hamming = 1 : m 2 `merge` m 3 `merge` m 5 
    where 
    m k = map (k *) hamming 

main = print (hamming !! 499999) 

Tính toán con số đó với tốc độ hợp lý trong một ngôn ngữ không lười biếng sẽ mất nhiều mã hơn một chút và đầu trầy xước. Có rất nhiều examples here