Hiệu quả của unfoldr so với zipWith

Question

Over on Code Review, tôi đã trả lời một câu hỏi về naive Haskell fizzbuzz solution bằng cách đề xuất thực hiện iterates forward, tránh chi phí bậc hai của số nguyên tố ngày càng tăng và loại bỏ phân chia modulo (gần như) hoàn toàn. Đây là mã:

fizz :: Int -> String 
fizz = const "fizz" 

buzz :: Int -> String 
buzz = const "buzz" 

fizzbuzz :: Int -> String 
fizzbuzz = const "fizzbuzz" 

fizzbuzzFuncs = cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz] 

toFizzBuzz :: Int -> Int -> [String] 
toFizzBuzz start count = 
    let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs 
    in take count $ zipWith ($) offsetFuncs [start..] 

Như một lời nhắc khác, tôi đề nghị viết lại bằng cách sử dụng Data.List.unfoldr. Phiên bản unfoldr là một sửa đổi đơn giản, rõ ràng đối với mã này vì vậy tôi sẽ không gõ nó ở đây trừ khi mọi người tìm cách trả lời câu hỏi của tôi nhấn mạnh rằng điều đó quan trọng (không có kẻ phá hoại cho OP trên Code Review). Nhưng tôi có một câu hỏi về hiệu quả tương đối của giải pháp unfoldr so với zipWith. Trong khi tôi không còn là một nhà khoa học Haskell nữa, tôi không có chuyên gia về nội bộ Haskell.

Giải pháp unfoldr không yêu cầu danh sách vô hạn [start..] vì nó chỉ có thể mở ra từ start. Suy nghĩ của tôi là

1. Giải pháp zipWith không ghi nhớ từng yếu tố liên tiếp của [start..] khi được yêu cầu. Mỗi phần tử được sử dụng và loại bỏ vì không có tham chiếu đến phần đầu của [start ..] được giữ lại. Vì vậy, không có nhiều bộ nhớ được tiêu thụ ở đó hơn với unfoldr.
2. Mối quan tâm về hiệu suất của unfoldr và các bản vá lỗi gần đây để làm cho nó luôn luôn được gạch chân được thực hiện ở cấp độ mà tôi chưa đạt được.

Vì vậy, tôi nghĩ hai điều này tương đương với mức tiêu thụ bộ nhớ nhưng không có ý tưởng về hiệu suất tương đối. Hy vọng thêm thông tin Haskellers có thể hướng dẫn tôi hướng tới một sự hiểu biết về điều này.

unfoldr có vẻ là một điều tự nhiên để sử dụng để tạo chuỗi, ngay cả khi các giải pháp khác mang tính biểu cảm hơn. Tôi chỉ biết tôi cần hiểu thêm về hiệu suất thực tế của nó. (Đối với một số lý do tôi tìm foldr dễ dàng hơn để hiểu ở mức độ đó)

Note: unfoldr 's sử dụng Maybe là tiềm năng vấn đề biểu diễn đầu tiên đã xảy ra với tôi, trước khi tôi thậm chí bắt đầu điều tra vấn đề này (và các chỉ một chút về các cuộc thảo luận tối ưu hóa/nội tuyến mà tôi đã hiểu đầy đủ). Vì vậy, tôi đã có thể ngừng lo lắng về Maybe ngay lập tức (được cung cấp một phiên bản gần đây của Haskell).

Answer 1

Là người chịu trách nhiệm cho những thay đổi gần đây trong việc triển khai zipWith và unfoldr, tôi đã đoán tôi có lẽ nên thực hiện việc này. Tôi thực sự không thể so sánh chúng một cách dễ dàng như vậy, bởi vì chúng là những chức năng rất khác nhau, nhưng tôi có thể cố gắng giải thích một số đặc tính của chúng và ý nghĩa của những thay đổi.

unfoldr

nội tuyến

Các phiên bản cũ của unfoldr (trước base-4.8/GHC 7.10) là đệ quy ở cấp cao nhất (nó được gọi là bản thân trực tiếp). GHC không bao giờ nhấn mạnh các hàm đệ quy, do đó, unfoldr không bao giờ được gạch chân. Kết quả là, GHC không thể thấy nó tương tác như thế nào với chức năng nó đã được thông qua.Tác động đáng lo ngại nhất của việc này là hàm được truyền vào, thuộc loại (b -> Maybe (a, b)), thực sự sẽ tạo ra các giá trị Maybe (a, b), cấp phát bộ nhớ để giữ các hàm tạo Just và (,). Bằng cách tái cơ cấu unfoldr như là một "công nhân" và "trình bao", mã mới cho phép GHC in nội tuyến và (trong nhiều trường hợp) kết hợp nó với hàm được truyền vào, vì vậy các hàm tạo thêm bị loại bỏ bởi các tối ưu hóa trình biên dịch.

Ví dụ, dưới GHC 7.10, mã

module Blob where 
import Data.List 

bloob :: Int -> [Int] 
bloob k = unfoldr go 0 where 
    go n | n == k = Nothing 
     | otherwise = Just (n * 2, n+1) 

biên soạn với ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures dẫn đến lõi

$wbloob :: Int# -> [Int] 
$wbloob = 
    \ (ww_sYv :: Int#) -> 
    letrec { 
     $wgo_sYr :: Int# -> [Int] 
     $wgo_sYr = 
     \ (ww1_sYp :: Int#) -> 
      case tagToEnum# (==# ww1_sYp ww_sYv) of _ { 
      False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1)); 
      True -> [] 
      }; } in 
    $wgo_sYr 0 

bloob :: Int -> [Int] 
bloob = 
    \ (w_sYs :: Int) -> 
    case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv } 

Fusion

Sự thay đổi khác để unfoldr được viết lại nó để tham gia vào "kết hợp gấp/xây dựng", một khung tối ưu hóa được sử dụng trong các thư viện danh sách của GHC. Ý tưởng về phản ứng tổng hợp "gấp/xây dựng" và "hợp nhất dòng" mới hơn, cân bằng khác nhau (được sử dụng trong thư viện vector) là nếu danh sách được sản xuất bởi "nhà sản xuất tốt", được chuyển đổi bởi "máy biến áp tốt" và tiêu thụ bởi một "người tiêu dùng tốt", sau đó danh sách conses không bao giờ thực sự cần phải được phân bổ ở tất cả. unfoldr cũ là không phải là nhà sản xuất tốt, vì vậy nếu bạn tạo một danh sách với unfoldr và tiêu thụ nó, ví dụ: foldr, các phần của danh sách sẽ được phân bổ (và ngay lập tức trở thành rác). Bây giờ, unfoldr là nhà sản xuất tốt, vì vậy bạn có thể viết vòng lặp bằng cách sử dụng, ví dụ: unfoldr, filter và foldr và không nhất thiết phải cấp phát bất kỳ bộ nhớ nào.

Ví dụ, đưa ra định nghĩa trên của bloob và nghiêm khắc {-# INLINE bloob #-} (công cụ này là một chút mong manh; sản xuất tốt đôi khi cần phải được inlined một cách rõ ràng là tốt), mã

hooby :: Int -> Int 
hooby = sum . bloob 

biên dịch để lõi GHC

$whooby :: Int# -> Int# 
$whooby = 
    \ (ww_s1oP :: Int#) -> 
    letrec { 
     $wgo_s1oL :: Int# -> Int# -> Int# 
     $wgo_s1oL = 
     \ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) -> 
      case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ { 
      False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2)); 
      True -> ww2_s1oG 
      }; } in 
    $wgo_s1oL 0 0 

hooby :: Int -> Int 
hooby = 
    \ (w_s1oM :: Int) -> 
    case w_s1oM of _ { I# ww1_s1oP -> 
    case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT } 
    } 

không có danh sách, không Maybe s và không có cặp nào; phân bổ duy nhất mà nó thực hiện là Int được sử dụng để lưu trữ kết quả cuối cùng (việc áp dụng I# đến ww2_s1oT). Toàn bộ tính toán có thể được dự kiến ​​thực hiện hợp lý trong các thanh ghi máy.

zipWith

zipWith có một chút của một câu chuyện kỳ ​​lạ. Nó phù hợp với khung công tác/xây dựng một chút lúng túng (tôi tin rằng nó hoạt động tốt hơn một chút với sự hợp nhất dòng). Có thể tạo cầu chì zipWith với đối số thứ nhất hoặc thứ hai trong danh sách thứ hai và trong nhiều năm, thư viện danh sách đã cố gắng kết hợp với một trong hai nhà sản xuất tốt. Thật không may, làm cho nó hợp nhất với đối số danh sách thứ hai của nó có thể làm cho một chương trình ít được xác định trong những trường hợp nhất định. Đó là, một chương trình sử dụng zipWith có thể hoạt động tốt khi được biên dịch mà không tối ưu hóa, nhưng tạo ra lỗi khi được biên dịch với tối ưu hóa. Đây không phải là một tình huống tuyệt vời. Do đó, kể từ base-4.8, zipWith không còn cố gắng hợp nhất với đối số danh sách thứ hai của nó nữa. Nếu bạn muốn nó hợp nhất với một nhà sản xuất giỏi, nhà sản xuất giỏi đó đã tốt hơn trong đối số danh sách đầu tiên.

Cụ thể, việc triển khai tham chiếu zipWith dẫn đến kỳ vọng rằng, zipWith (+) [1,2,3] (1 : 2 : 3 : undefined) sẽ cung cấp [2,4,6], vì nó dừng ngay khi nó chạm vào cuối danh sách đầu tiên. Với việc thực hiện zipWith trước đó, nếu danh sách thứ hai trông như thế nhưng được sản xuất bởi một nhà sản xuất tốt và nếu zipWith xảy ra để hợp nhất với nó thay vì danh sách đầu tiên, thì nó sẽ bùng nổ.