Memoization và typeclasses

Question

Để giữ cho nó đơn giản, tôi sẽ sử dụng lớp ví dụ contrived này (Vấn đề là chúng ta có một số dữ liệu đắt tiền có nguồn gốc từ phương pháp):

class HasNumber a where 
    getNumber :: a -> Integer 
    getFactors :: a -> [Integer] 
    getFactors a = factor . getNumber 

Tất nhiên, chúng ta có thể làm cho việc triển khai memoizing của lớp này như:

data Foo = Foo { 
    fooName :: String, 
    fooNumber :: Integer, 
    fooFactors :: [Integer] 
} 

foo :: String -> Integer -> Foo 
foo a n = Foo a n (factor n) 

instance HasNumber Foo where 
    getNumber = fooNumber 
    getFactors = fooFactors 

Nhưng nó có vẻ hơi xấu xí để được yêu cầu tự thêm một lĩnh vực 'yếu tố' đến bất cứ hồ sơ đó sẽ là một ví dụ HasNumber. Ý tưởng tiếp theo:

data WithFactorMemo a = WithFactorMemo { 
    unWfm :: a, 
    wfmFactors :: [Integer] 
} 

withFactorMemo :: HasNumber a => a -> WithFactorMemo a 
withFactorMemo a = WithFactorMemo a (getFactors a) 

instance HasNumber a => HasNumber (WithFactorMemo a) where 
    getNumber = getNumber . unWfm 
    getFactors = wfmFactors 

này sẽ đòi hỏi rất nhiều soạn sẵn để nâng tất cả các hoạt động khác của bản gốc a vào WithFactorMemo a, mặc dù.

Có giải pháp thanh lịch nào không?

Answer 1

Đây là giải pháp: mất kiểu chữ. Tôi đã nói về điều này here và here. Bất kỳ typeclass TC a mà mỗi thành viên của nó lấy một a là một đối số là đẳng cấu cho một kiểu dữ liệu. Điều đó có nghĩa rằng tất cả các thể hiện của lớp HasNumber của bạn có thể được đại diện trong kiểu dữ liệu này:

data Number = Number { 
    getNumber' :: Integer, 
    getFactors' :: [Integer] 
} 

Cụ thể, bằng cách chuyển đổi này:

toNumber :: (HasNumber a) => a -> Number 
toNumber x = Number (getNumber x) (getFactors x) 

Và Number rõ ràng là một thể hiện của HasNumber là tốt.

instance HasNumber Number where 
    getNumber = getNumber' 
    getFactors = getFactors' 

Tính đẳng hình này cho chúng ta thấy lớp này là loại dữ liệu ngụy trang và phải chết. Chỉ cần sử dụng Number để thay thế. Nó có thể ban đầu không rõ ràng làm thế nào để làm điều này, nhưng với một chút kinh nghiệm nên đến một cách nhanh chóng. . Ví dụ, gõ Foo của bạn trở thành:

data Foo = Foo { 
    fooName :: String, 
    fooNumber :: Number 
} 

memoization của bạn sau đó sẽ đến miễn phí, bởi vì các yếu tố này được lưu trữ trong cơ cấu Number dữ liệu.