缓存实例中默认方法的结果是什么时候

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将被缓存，并且随后的每个引用都将使用该值

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

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 1的结果之后打印g 2的结果。显然，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，所以结果不缓存OR
2. BigSum的每个实例都有一个单独的bigSum实现，专门用于所讨论的类型，因此当为特定类型调用bigSum时，只为该类型计算一次

我的测试表明发生的是case(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

我想可靠地确定的是，对于某些X和blah，f不会每次调用conversionX blah时都被重新计算。相反，我希望每种类型的SimpleConversion只运行一次f。任何其他操作都会完全增加运行时成本，因为与实际转换相比，f做了很多工作。

如有任何相关文件/参考，不胜感激。

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

CCD_ 28的派生字典和实例降为：

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

CCD_ 29降糖为

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

注意，A(不使用默认方法)和B(确实使用)都有一个通过多态函数定义的bigSum字段(doBigSum直接用于A；doBigSum通过多态函数dm_bigSum用于B)。重要的是，两个bigSum字段值——即bigSumA和bigSumB——都是命名的单态值。

在对f的调用中，每次调用f时都会重新评估表达式doBigSum dEnum dNum。然而，在对g的调用中，字段选择表达式bigSum dBigSum仅从字典中选择单形字段。如果在类型A中调用它十几次，它只会返回相同的bigSumA :: Athunk。

因此，对于本例，可以保证每个实例对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]

这可能导致CCD_ 60的重新评估。

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

在您的Conversions示例中，一旦解析了类型变量a，字段Conversions 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