NoMonomorphismRestriction giúp duy trì việc chia sẻ?

Question

Tôi đã cố gắng trả lời another question về tính đa hình so với chia sẻ khi tôi tình cờ gặp hành vi kỳ lạ này.

Trong GHCi, khi tôi xác định một cách rõ ràng một hằng số đa hình, nó không nhận được bất kỳ sự chia sẻ, đó là điều dễ hiểu:

> let fib :: Num a => [a]; fib = 1 : 1 : zipWith (+) fib (tail fib) 
> fib !! 30 
1346269 
(5.63 secs, 604992600 bytes) 

Mặt khác, nếu tôi cố gắng để đạt được cùng bằng cách bỏ chữ ký kiểu và vô hiệu hóa các hạn chế monomorphism, liên tục của tôi đột nhiên được chia sẻ!

> :set -XNoMonomorphismRestriction 
> let fib = 1 : 1 : zipWith (+) fib (tail fib) 
> :t fib 
fib :: Num a => [a] 
> fib !! 50 
20365011074 
(0.00 secs, 2110136 bytes) 

Tại sao ?!

Ugh ... Khi được biên dịch với tối ưu hóa, nó nhanh chóng ngay cả khi hạn chế đơn cấu hình bị tắt.

Answer 1

Bằng cách đưa chữ ký kiểu tường minh, bạn ngăn GHC từ làm cho một số giả định về mã của bạn. Tôi sẽ chỉ cho một ví dụ (lấy từ question này):

foo (x:y:_) = x == y 
foo [_]  = foo [] 
foo []  = False 

Theo GHCi, loại chức năng này là Eq a => [a] -> Bool, như bạn mong muốn. Tuy nhiên, nếu bạn khai báo foo bằng chữ ký này, bạn sẽ gặp lỗi "biến loại mơ hồ".

Lý do tại sao chức năng này chỉ hoạt động mà không có chữ ký loại là do cách đánh máy hoạt động trong GHC. Khi bạn bỏ qua một chữ ký loại, foo được giả định là có một mẫu [a] -> Bool đối với một số loại cố định a. Khi bạn hoàn thành việc nhập nhóm liên kết, bạn tổng quát các loại. Đó là nơi bạn nhận được forall a. .... Mặt khác, khi bạn khai báo chữ ký kiểu đa hình, bạn tuyên bố rõ ràng rằng foo là đa hình (và do đó loại [] không phải khớp với loại đối số đầu tiên) và bùng nổ, bạn sẽ nhận được loại không rõ ràng biến.

Bây giờ, biết điều này, chúng ta hãy so sánh cốt lõi:

fib = 0:1:zipWith (+) fib (tail fib) 
----- 
fib :: forall a. Num a => [a] 
[GblId, Arity=1] 
fib = 
    \ (@ a) ($dNum :: Num a) -> 
    letrec { 
     fib1 [Occ=LoopBreaker] :: [a] 
     [LclId] 
     fib1 = 
     break<3>() 
     : @ a 
      (fromInteger @ a $dNum (__integer 0)) 
      (break<2>() 
      : @ a 
      (fromInteger @ a $dNum (__integer 1)) 
      (break<1>() 
       zipWith 
       @ a @ a @ a (+ @ a $dNum) fib1 (break<0>() tail @ a fib1))); } in 
    fib1 

Và đối với thứ hai:

fib :: Num a => [a] 
fib = 0:1:zipWith (+) fib (tail fib) 
----- 
Rec { 
fib [Occ=LoopBreaker] :: forall a. Num a => [a] 
[GblId, Arity=1] 
fib = 
    \ (@ a) ($dNum :: Num a) -> 
    break<3>() 
    : @ a 
     (fromInteger @ a $dNum (__integer 0)) 
     (break<2>() 
     : @ a 
     (fromInteger @ a $dNum (__integer 1)) 
     (break<1>() 
      zipWith 
      @ a 
      @ a 
      @ a 
      (+ @ a $dNum) 
      (fib @ a $dNum) 
      (break<0>() tail @ a (fib @ a $dNum)))) 
end Rec } 

Với loại chữ ký rõ ràng, như với foo trên, GHC có để điều trị fib như giá trị đệ quy có khả năng đa hình. Chúng tôi có thể chuyển một số khác nhau Num từ điển sang fib trong zipWith (+) fib ... và tại thời điểm này, chúng tôi sẽ phải ném hầu hết danh sách đi, vì khác nhau Num có nghĩa là khác nhau (+). Tất nhiên, một khi bạn biên dịch với tối ưu hóa, GHC nhận thấy rằng từ điển Num không bao giờ thay đổi trong "cuộc gọi đệ quy" và tối ưu hóa nó đi.

Trong lõi ở trên, bạn có thể thấy rằng GHC thực sự cung cấp cho fib một từ điển Num (có tên $dNum) lặp đi lặp lại.

Vì fib không có chữ ký loại được giả định là đơn nhất trước khi khái quát hóa toàn bộ nhóm ràng buộc được hoàn thành, các phụ đề fib được cung cấp chính xác cùng loại với toàn bộ fib. Nhờ vậy, fib trông giống như:

{-# LANGUAGE ScopedTypeVariables #-} 
fib :: forall a. Num a => [a] 
fib = fib' 
    where 
    fib' :: [a] 
    fib' = 0:1:zipWith (+) fib' (tail fib') 

Và bởi vì các loại vẫn được cố định, bạn có thể sử dụng chỉ là một từ điển được lúc khởi động.

Answer 2

Ở đây bạn đang sử dụng fib với cùng một đối số loại trong cả hai trường hợp và ghc đủ thông minh để xem điều này và thực hiện chia sẻ. Bây giờ, nếu bạn sử dụng chức năng mà nó có thể được gọi với đối số loại khác nhau và việc đặt mặc định dẫn đến một trong những đối tượng rất khác so với cách khác, thì việc thiếu hạn chế monomorphism sẽ khiến bạn khó chịu.

Cân nhắc sử dụng thuật ngữ x = 2 + 2 polymorphically trong hai bối cảnh mà không có sự hạn chế monomorphism, nơi mà trong một bối cảnh mà bạn show (div x 2) và trong một bạn sử dụng show (x/2), Trong một thiết lập mà bạn có được Integral và Show trở ngại mà làm cho bạn để mặc định Integer, trong người kia bạn nhận được Fractional và ràng buộc Show và mặc định là Double, do đó kết quả của tính toán không được chia sẻ vì bạn đang làm việc với cụm từ đa hình được áp dụng cho hai loại riêng biệt. Với sự hạn chế monomorphism bật, nó cố gắng để mặc định một thời gian cho một cái gì đó cả hai Integral và Fractional và thất bại.

Tâm trí bạn tricker của nó để có được tất cả điều này để bắn những ngày này với let không khái quát hóa vv