在类实例中缓存计算成本昂贵的结果

Question

假设我有类似以下内容

class C a where
  f :: a -> Text

newtype T a = T a

expensiveFunction :: (Bounded a, Enum a, ToText a) => Map a Text
expensiveFunction = _ 

cheapFunction :: (Bounded a, Enum a, ToText a) => T a -> Map a Text -> Text
cheapFunction = _

instance (Bounded a, Enum a, ToText a) => C (T a) where
  f x = cheapFunction x expensiveFunction

我想做的是这样的：

newtype U = U Int
  deriving C via (T Int)

这是我看到的问题。每次调用

expensiveFunction

时都会调用

f

。这是不好的。

我确实有这个想法，将

T a

实例更改为：

instance (Bounded a, Enum a, ToText a) => C (T a) where
  f = flip cheapFunction expensiveFunction

然后希望

f

（即一个参数的函数）被计算一次，这希望意味着

expensiveFunction

只被计算一次。

但我不确定这有多可靠。我猜如果请求的实例是多态的，那么这可能行不通，但如果实例是单态的（即上面的

T Int

），那么我希望这能解决问题。

但是

f

不是一个普通的函数，它是一个实例函数，并且由于

f

在类

C

中定义为一个函数，而不是一个独立的值，也许它会被视为一个函数并重新计算每次。

有什么想法吗？我应该在这里使用更好的方法吗？如果可能的话，我想保留通过语法的良好派生。

Answer 1

我做了一些快速实验。您使用

flip

将

expensiveFunction

移到

f

最终应用程序之外的建议似乎效果很好。

这是我使用的：

module Main where

import C
import U

main :: IO ()
main = do
  putStrLn "f @(T Int)"
  let a = f (T @Int 1)
      b = f (T @Int 2)
      c = f (T @Int 3)
  a `seq` b `seq` c `seq` print [a, b, c]

  putStrLn "\n\nU"
  let x = f (U 4)
      y = f (U 5)
      z = f (U 6)
  x `seq` y `seq` z `seq` print [x, y, z]

  putStrLn "\n\ng @(T Int)"
  let g = f @(T Int)
      i = g (T 7)
      j = g (T 8)
      k = g (T 9)
  i `seq` j `seq` k `seq` print [i, j, k]

module C
  ( C (..)
  , T (..)
  , ToText (..)
  , expensiveFunction
  , cheapFunction
  )
where


import Data.Map (Map)
import Data.Text (Text)
import Data.Text qualified as Text

import Debug.Trace (trace)


class ToText a where
  toText :: a -> Text
  default toText :: Show a => a -> Text
  toText = Text.pack . show


instance ToText Int


class C a where
  f :: a -> Text

newtype T a = T a

expensiveFunction :: (Bounded a, Enum a, ToText a, Ord a) => Map a Text
expensiveFunction = trace "expensive" $ mempty

cheapFunction :: (Bounded a, Enum a, ToText a) => T a -> Map a Text -> Text
cheapFunction (T x) !_ = trace "cheap" $ toText x

instance (Bounded a, Enum a, ToText a, Ord a) => C (T a) where
  f = flip cheapFunction expensiveFunction

如果没有优化，我会得到这个：

f @(T Int)
expensive
cheap
expensive
cheap
expensive
cheap
["1","2","3"]


f @U
expensive
cheap
cheap
cheap
["4","5","6"]


g
expensive
cheap
cheap
cheap
["7","8","9"]

正如您所想，像

T

这样的多态实例每次都会重新评估

expensiveFunction

（因为

f

是

Bounded a

等词典的函数，并且会发生

expensiveFunction

的评估）在

f

到实例字典的应用程序内部，即使它在

f

到其最终参数的应用程序之外）。

但是

f

的

U

能够保留单个共享

expensiveFunction

，因此仅评估一次。

并且如

g

所示，您始终可以定义单态变体，这将确保

expensiveFunction

在单态变体的所有用途之间共享。

当编译和优化时，我得到这个：

f @(T Int)
expensive
cheap
cheap
cheap
["1","2","3"]


f @U
cheap
cheap
cheap
["4","5","6"]


g
cheap
cheap
cheap
["7","8","9"]

编译器注意到所有这些最终都使用

expensiveFunction @Int

，甚至在不同新类型的实例之间共享它。

通过优化，即使不应用您的

flip

优化，我也会出现这种行为。

就我个人而言，我愿意依赖未优化版本中

expensiveFunction

调用（和

f @U

调用）之间的

g

共享。它符合我对一个相当幼稚的心理模型的期望，其中共享是由 let 绑定和范围决定的，因此我认为更改实现或未来编译器版本带来的扰动不太可能比这更糟糕。因此，如果共享像

C U

这样的单态实例和像

g

这样的单态包装器就足够了，那么我只需应用您的

flip

优化并感到满意。

我不太愿意依赖优化的精确行为；它们可能会受到编译器决定内联的程度的影响，这可以在未来的编译器版本中或当我对代码进行更改时轻松更改。因此，如果在所有实例之间共享（甚至对于像

C (T a)

这样的多态实例）至关重要，那么我想考虑编写更少的“好”代码，使共享更加明确。