Chức năng foldl được viết lại của tôi có được tối ưu hóa không?

Question

Tôi mới bắt đầu Haskell 2 ngày trước vì vậy tôi chưa chắc chắn về cách tối ưu hóa mã của mình.

Như một bài tập, tôi đã viết lại foldl và foldr (Tôi sẽ cung cấp cho foldl đây nhưng foldr là như nhau, thay thế last với head và init với tail).

Mã này là:

module Main where 

    myFoldl :: (a -> (b -> a)) -> a -> ([b] -> a) 

    myFoldl func = (\x -> (\theList 
     -> if (length theList == 0) then 
      x 
     else 
      myFoldl func (func x (last theList)) (init theList) 
     )) 

mối quan tâm duy nhất của tôi là tôi nghi ngờ Haskell không thể áp dụng tối ưu hóa cuộc gọi đuôi ở đây vì cuộc gọi đệ quy không được thực hiện ở phần cuối của hàm.

Làm cách nào để thực hiện cuộc gọi đuôi này được tối ưu hóa? Việc triển khai thực hiện của Haskell có được thực hiện một cách khác nhau đối với tôi là foldl?

Answer 1

Việc sử dụng dấu ngoặc đơn trong mẫu mã của bạn và nhấn mạnh vào việc đệ quy đuôi cho thấy bạn sắp đến Haskell từ Lisp hoặc Đề án. Nếu bạn đang đến Haskell từ một ngôn ngữ háo hức như Scheme, được cảnh báo: các cuộc gọi đuôi không gần như dự đoán về hiệu năng trong Haskell vì chúng đang ở trong một ngôn ngữ háo hức. Bạn có thể có các hàm đệ quy đuôi thực thi trong không gian tuyến tính vì sự lười biếng, và bạn có thể có các hàm đệ quy không đuôi thực thi trong không gian cố định vì sự lười biếng. (Đã nhầm lẫn?)

Lỗi đầu tiên trong định nghĩa của bạn là sử dụng length theList == 0. Lực lượng này đánh giá toàn bộ cột sống của danh sách, và là thời gian O (n). Nó tốt hơn để sử dụng phù hợp với mô hình, như trong ngây thơ foldl định nghĩa này trong Haskell:

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f z [] = z 
foldl f z (x:xs) = foldl f (f z x) xs 

này, tuy nhiên, thực hiện ổi nặng trong Haskell, vì chúng ta không thực sự tính toán phần f z x cho đến khi người gọi của foldl đòi hỏi sự kết quả; do đó, foldl này tích lũy các khối không được đánh giá trong bộ nhớ cho từng phần tử danh sách và không có lợi ích nào từ việc đệ quy đuôi. Trong thực tế, mặc dù được đệ quy đuôi, foldl ngây thơ này trong một danh sách dài có thể dẫn đến tràn ngăn xếp! (Data.List module có chức năng foldl' không có vấn đề này.)

Như một trò chuyện, nhiều chức năng đệ quy không đuôi Haskell thực hiện rất tốt. Ví dụ, hãy định nghĩa này của find, dựa trên định nghĩa đệ quy phi đuôi đính kèm của foldr:

find :: (a -> Boolean) -> [a] -> Maybe a 
find pred xs = foldr find' Nothing xs 
    where find' elem rest = if pred elem then Just elem else rest 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (subfold xs) 
    where subfold = foldr f z 

Điều này thực sự thực hiện trong thời gian tuyến tính và không gian liên tục, nhờ vào sự lười biếng. Tại sao?

1. Khi bạn tìm thấy phần tử thỏa mãn vị từ, không cần phải đi qua phần còn lại của danh sách để tính giá trị rest.
2. Khi bạn xem xét một phần tử và quyết định rằng nó không khớp, không cần giữ lại bất kỳ dữ liệu nào về phần tử đó.

Bài học tôi muốn truyền đạt ngay bây giờ là: không đưa các giả định hiệu suất của bạn từ ngôn ngữ mong muốn vào Haskell. Bạn chỉ cần hai ngày; tập trung đầu tiên vào sự hiểu biết cú pháp và ngữ nghĩa của ngôn ngữ, và không mâu thuẫn với bản thân bạn bằng cách viết các phiên bản tối ưu hóa của các chức năng chỉ được nêu ra. Bạn sẽ bị ảnh hưởng bởi luồng tràn ngăn xếp theo kiểu foldl theo thời gian, nhưng trước tiên bạn sẽ thành thạo.

---

EDIT [2012/09/05]: cuộc biểu tình đơn giản mà lười biếng find chạy trong không gian liên tục mặc dù không phải là đệ quy đuôi. định nghĩa đầu tiên, đơn giản hóa:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (foldr f z xs) 

find :: (a -> Bool) -> [a] -> Maybe a 
find p xs = let step x rest = if p x then Just x else rest 
      in foldr step Nothing xs 

Bây giờ, sử dụng lập luận equational (ví dụ, thay thế bằng với bằng, dựa trên định nghĩa ở trên), và đánh giá theo một thứ tự lười biếng (ngoài cùng đầu tiên), chúng ta hãy tính toán find (==400) [1..]:

find (==400) [1..] 
    -- Definition of `find`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [1..] 

    -- `[x, y, ...]` is the same as `x:[y, ...]`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (1:[2..]) 

    -- Using the second equation in the definition of `foldr`: 
    => let step x rest = if x == 400 then Just x else rest 
     in step 1 (foldr step Nothing [2..]) 

    -- Applying `step`: 
    => let step x rest = if x == 400 then Just x else rest 
     in if 1 == 400 then Just 1 else foldr step Nothing [2..] 

    -- `1 == 400` is `False` 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 1 else foldr step Nothing [2..] 

    -- `if False then a else b` is the same as `b` 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [2..] 

    -- Repeat the same reasoning steps as above 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (2:[3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 2 (foldr step Nothing [3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 2 == 400 then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [3..] 
     . 
     . 
     . 

    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [400..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (400:[401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 400 (foldr step Nothing [401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 400 == 400 then Just 400 else foldr step Nothing [401..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if True then Just 400 else foldr step Nothing [401..] 

    -- `if True then a else b` is the same as `a` 
    => let step x rest = if x == 400 then Just x else rest 
     in Just 400 

    -- We can eliminate the `let ... in ...` here: 
    => Just 400 

Lưu ý rằng các biểu thức trong các bước đánh giá liên tiếp không nhận được dần dần phức tạp hơn hoặc lâu hơn khi chúng tôi tiến hành thông qua danh sách; chiều dài hoặc chiều sâu của biểu thức ở bước n không tỷ lệ thuận với n, về cơ bản nó đã được sửa. Điều này trong thực tế chứng tỏ làm thế nào find (==400) [1..] có thể được thực hiện lazily trong không gian liên tục.

Answer 2

Haskell thành ngữ có vẻ rất khác với điều này, tránh nếu-thì-người khác, lambdas lồng nhau, dấu ngoặc đơn và hàm hủy (đầu, đuôi). Thay vào đó, bạn muốn viết nội dung đó như sau:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = go z0 xs0 
    where 
     go z []  = z 
     go z (x:xs) = go (f z x) xs 

Thay vào đó, thay vào kết hợp mẫu, mệnh đề where, tail đệ quy, tuyên bố được bảo vệ.