记忆化和类型化

Question

为了简单起见，我将使用这个人为设计的示例类(重点是我们有一些从方法派生的昂贵数据)：

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

当然，我们可以创建该类的内存实现，例如：

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

但是，需要手动向任何将成为HasNumber实例的记录中添加“因子”字段，这似乎有点难看。下一个想法：

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

然而，这将需要大量的样板文件来将原始a的所有其他操作提升到WithFactorMemo a中。

有什么优雅的解决方案吗？

Answer 1

这就是解决方案:去掉类型类。我已经讨论过这个here和here了。任何类型类TC a，如果它的每个成员都以单个a作为参数，则它与数据类型同构。这意味着您的HasNumber类的每个实例都可以用这种数据类型表示：

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

也就是说，通过这种转换：

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

显然，Number也是HasNumber的一个实例。

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

这种同构告诉我们，这个类是一种伪装的数据类型，它应该消亡。只需使用Number即可。最初可能不太清楚如何做到这一点，但有一点经验应该很快就会出现。例如，您的Foo类型变为：

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

然后，您的memoization将免费提供，因为因子存储在Number数据结构中。