实例中默认方法的结果何时被缓存？

Question

考虑以下模块：

{-# LANGUAGE GeneralisedNewtypeDeriving #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DefaultSignatures #-}

module Lib where

import Data.List (foldl')

doBigSum :: (Enum a, Num a) => a
doBigSum = foldl' (+) 0 [1..200000000]

f :: (Enum a, Num a) => a -> a
f x = x + doBigSum

class BigSum a where
  bigSum :: a
  default bigSum :: (Enum a, Num a) => a
  bigSum = doBigSum

newtype A = A Integer deriving newtype (Enum, Num, Show)
newtype B = B Integer deriving newtype (Enum, Num, Show)

instance BigSum A where
  bigSum = doBigSum

instance BigSum B

g :: (Num a, BigSum a) => a -> a
g x = x + bigSum

假设我们在这里也使用 GHC。

我在这里要注意一些事情（我相信这是真的，如果我错了，请纠正我）：

1. 除非有一些奇特的优化/内联，否则很有可能doBigSum不会被缓存，而是会为每个引用重新计算，因为doBigSum实际上采用一个隐藏参数，即a它所实例化的类型的类型类字典。
2. 但是，在实例定义中BigSum A，bigSum将被缓存，并且每个后续引用都将使用该值。

事实上，如果我创建一个像这样的 main 函数，这就是我所看到的：

import Lib

main :: IO ()
main = do
  print "Start"
  print ((f 1) :: A)
  print ((f 2) :: A)

并且在没有优化的情况下进行编译（这里单独的模块很重要），两个打印语句的输出之间显然存在时间差距。

但如果我这样做：

import Lib

main :: IO ()
main = do
  print "Start"
  print ((g 1) :: A)
  print ((g 2) :: A)

然后 的结果g 2会在 的结果之后立即打印g 1。显然，实例定义会导致创建BigSum A一个单独的常量。bigSum :: A

现在考虑

import Lib

main :: IO ()
main = do
  print "Start"
  print ((g 1) :: B)
  print ((g 2) :: B)

请注意，实例定义BigSum B并不明确，它取决于默认值。

现在这里发生了什么？是吗：

1. 的一种实现bigSum，即默认值，它有一个类型的隐藏参数，很像doBigSum，所以结果不被缓存或者
2. bigSum对于 的每个实例都有一个单独的实现BigSum，它专门针对相关类型，因此在调用bigSum特定类型时，仅针对该类型计算一次。

我的测试表明发生的情况是情况 (2)，这对我的用例有好处，但我想知道我可以在多大程度上依赖它。

我的实际用例更像是以下内容：

data ConversionInfo a = ...

data Conversions a = Conversions { convA :: a -> A, convB :: a -> B, convC :: a -> C } 

f :: ConversionInfo a -> Conversions a
f = ... -- Lots of work happens here

class SimpleConversion a where
  conversionInfo :: ConversionInfo a
  conversions :: Conversions a
  conversions = f conversionInfo

class Conversions a where
  conversionA :: a -> A
  default conversionA :: SimpleConversion a => a -> A
  conversionA = convA conversions

  conversionB :: a -> B
  default conversionB :: SimpleConversion a => a -> B
  conversionB = convB conversions

  conversionC :: a -> C
  default conversionC :: SimpleConversion a => a -> C
  conversionC = convC conversions

我想要可靠地确定的是，每次我调用some和 时f都不会重新计算。相反，我只想每种类型只运行一次。其他任何事情都会完全增加运行时成本，因为与实际转换相比需要做很多工作。conversionX blahXblahfSimpleConversionf

任何有关此的文档/参考文献将不胜感激。

Answer 1

简短回答： 方法是通过默认类方法还是通过每个实例定义来定义并不重要。重要的是方法的类型在特定实例定义中是单态的。这意味着一旦实例类型变量被解析，方法的类型就必须是单态的（例如，bigSum :: A），并且实例本身是单态的（例如，instance BigSum A，但不是instance BigSum [a]）。在这种情况下，可以保证bigSum每个实例仅评估一个值。

长答案： 正如您无疑知道的那样，在编译过程的早期，类被脱糖为字典数据类型，实例被脱糖为这些数据类型的值，约束被转换为显式字典参数。默认方法被简单地脱糖为多态函数，这些函数将在必要时用于为声明的实例中的非特定方法创建方法字段。换句话说，您的示例或多或少被脱糖为以下内容：

-- dictionary-passing versions of `doBigSum` and `f`
doBigSum :: Enum a -> Num a -> a
doBigSum dEnum dNum = ...

f :: Enum a -> Num a -> a -> a
f dEnum dNum x = x + doBigSum dEnum dNum

-- the BigSum class
data BigSum a = BigSum { bigSum :: a }

-- default class method for bigSum
dm_bigSum :: BigSum a -> Enum a -> Num a -> a
dm_bigSum _dBigSum dEnum dNum = doBigSum dEnum dNum

与派生字典和实例A脱糖为：

newtype A = A Int
fEnumA = coerce fEnumInt   -- `Enum A` dictionary
fNumA = coerce fNumInt     -- `Num A` dictionary

fBigSumA :: BigSum A
fBigSumA = BigSum { bigSum = bigSumA }

bigSumA :: A
bigSumA = doBigSum fEnumA fNumA

以及脱糖后的派生字典和实例B：

newtype B = B Int
fEnumB = coerce fEnumInt
fNumB = coerce fNumInt

fBigSumB :: BigSum B
fBigSumB = BigSum { bigSum = bigSumB }

bigSumB :: B
bigSumB = dm_bigSum fBigSumB fEnumB fNumB

并g脱糖为：

g :: Num a -> BigSum a -> a -> a
g dNum dBigSum x = (+) dNum x (bigSum dBigSum)

请注意，A（不使用默认方法）和B（确实）都有一个bigSum通过多态函数定义的字段（doBigSum直接 for A;doBigSum通过多态函数dm_bigSumfor B）。重要的是两个bigSum字段值（即bigSumA和bigSumB）都是命名的单态值。

在调用 时，每次调用时都会重新计算f表达式。但是，在调用 时，字段选择表达式仅从字典中选择单态字段。如果你在 type 调用它十几次，它只会返回相同的thunk。doBigSum dEnum dNumfgbigSum dBigSumAbigSumA :: A

因此，可以保证bigSum在此示例中每个实例都会评估一次。

然而，这种保证依赖于两件事。首先，它依赖于实例参数解析后方法是单态的。如果你有：

class BigPair a where
  bigPair :: (Num b) => (a,b)
  default bigPair :: (Enum a, Num a, Num b) => (a, b)
  bigPair = (doBigSum, 123456789)

instance BigPair A where
  bigPair = (doBigSum, 123456789)
instance BigPair B

g :: (Num a, BigPair a, Num b) => a -> (a, b)
g x = let (a, b) = bigPair in (a+x, b)

您可能会发现类似的表达式会导致每次运行时g 1 :: (A, Int)重新计算。doBigSum与 相同g 1 :: (B, Int)。问题是实例字典中的字段为A类型forall b. Num b => (A, b)，因此它不是单态的。编译器可能会提升字段表达式之外的计算doBigSum，但您现在依赖于优化。在我的测试中，每次在 GHCi 下运行或使用-O0,编译时都会重新评估。doBigSum编译时-O2，仅评估一次。

其次，它依赖于实例本身是单态的。您可以轻松编写一个多态实例，该实例可能会导致bigSum每次调用时都重新评估。考虑：

instance (Enum a, Num a) => BigSum [a] where
  bigSum = [doBigSum]

这将糖化为一个生成一系列实例字典的函数：

fBigSumList :: Enum a -> Num a -> BigSum [a]
fBigSumList dEnum dNum = BigSum { bigSum = bigSumList dEnum dNum }

bigSumList :: Enum a -> Num a -> a
bigSumList dEnum dNum = [doBigSum dEnum dNum]

现在，任何特定类型不再有任何命名的单态字段值a。表达方式：

bigSum :: [Int]

通话中脱糖：

bigSum (fBigSumList fEnumInt fNumInt) 
= bigSumList fEnumInt fNumInt
= [doBigSum dEnum dNum]

这可能会导致重新评估doBigSum。

doBigSum在我对一个简单示例的测试中，每次评估时GHCi 都会重新评估bigSum :: [Int]。然而，即使-O0只计算一次也可以进行编译，但可能是因为函数中公共子表达式的消除main，所以这可能是一个非常脆弱的优化。

在您的Conversions示例中，Conversions a一旦解析了类型变量，该字段就应该是单态的a，因此我相信您定义的任何单态实例都应该共享conversions. （一个警告：由于字段是函数，您依赖于正在执行的“工作”被f适当地从返回的函数集合中取出f。）如果您更改数据类型的定义，Conversions使其包含一些更高的-排名多态性，或者如果您定义了多态SimpleConversion实例，则可能会失去此保证。

您可以通过使用以下内容进行编译来检查精确的脱糖：

ghc -O0 -ddump-ds -dsuppress-all -dno-suppress-type-applications 
        -dno-suppress-type-signatures -dsuppress-uniques -fforce-recomp 
        ...

请注意，具有单个方法的类被脱糖为新类型，因此实例字典最终成为单个字段的强制，而不是data具有多个命名字段的类型。例如，您的代码实际上脱糖为如下所示：

-- the polymorphic function `doBigSum`
doBigSum :: forall a. (Enum a, Num a) => a
doBigSum = \ @a $dEnum $dNum -> ...

-- the polymorphic default method
$dmbigSum :: forall a. (BigSum a, Enum a, Num a) => a
$dmbigSum = \ @a _ $dEnum $dNum -> doBigSum @a $dEnum $dNum

-- the instance dictionary for A
-- (note: because it's only got one field, it's a cast *of* that field)
$fBigSumA :: BigSum A
$fBigSumA = $cbigSum_A `cast` <Co:3>

-- bigSum as defined in the A instance
$cbigSum_A :: A
$cbigSum_A = doBigSum @A $fEnumA $fNumA

-- the instance dictionary for B
$fBigSumB :: BigSum B
$fBigSumB = $cbigSum_B `cast` <Co:3>

-- bigSum from the default method
$cbigSum_B :: B
$cbigSum_B = $dmbigSum @B $fBigSumB $fENumB $fNumB