在Haskell中重用/ memoization全局多态(类)值

Question

我关心的是,何时以及何时共享/记忆多态"全局" 类值,特别是跨模块边界.我已经读过这个和这个,但它们似乎并不能反映我的情况,而且我看到了一些与人们对答案的期望不同的行为.

考虑一个暴露一个计算成本高昂的值的类:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

module A

import Debug.Trace

class Costly a where
  costly :: a

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = trace "costly!" $ (repeat 1) !! 10000000

foo :: Int
foo = costly + 1

costlyInt :: Int
costlyInt = costly

还有一个单独的模块:

module B
import A

bar :: Int
bar = costly + 2

main = do
  print foo
  print bar
  print costlyInt
  print costlyInt

运行main产生两个单独的评估costly(如跟踪所示):一个用于foo,一个用于bar.我知道,costlyInt刚刚返回(评估)costly从foo,因为如果我删除print foo从main那么第一个costlyInt成本变高.(costlyInt无论如何,我也可以通过概括footo 的类型来执行单独的评估Num a => a.)

我想我知道为什么会发生这种情况:实例Costly实际上是一个带Num字典并生成Costly字典的函数.因此,在编译bar和解析引用时costly,ghc会生成一个新的Costly字典,其中包含一个昂贵的thunk.问题1:我对此是否正确？

有几种方法只能进行一次评估costly,包括:

• 将所有内容放在一个模块中
• 删除Num i实例约束,只需定义一个Costly Int实例.

不幸的是,这些解决方案的类比在我的程序中是不可行的 - 我有几个模块以其多态形式使用类值,并且只在顶级源文件中是最终使用的具体类型.

还有一些变化不会减少评估的数量,例如:

• costly对实例中的定义使用INLINE,INLINABLE或NOINLINE .(我没想到这会起作用,但嘿,值得一试.)
• SPECIALIZE instance Costly Int在实例定义中使用pragma.

后者是令人惊讶的,我-我希望它是基本上等同于上述第二项所做的工作.也就是说,我认为这将产生一个特殊的Costly Int字典,这是所有的foo,bar以及costlyInt也有同感.我的问题2:我在这里错过了什么？

我的最后一个问题:是否有任何相对简单和万无一失的方式来获得我想要的东西,即所有对costly模块共享的特定具体类型的引用？从我到目前为止所看到的,我怀疑答案是否定的,但我仍然抱着希望.

Answer 1

控制共享在GHC中很棘手.GHC做了许多可以影响共享的优化(例如内联,浮动等).

在这种情况下,为了回答为什么SPECIALIZE编译指示没有达到预期效果的问题,让我们看一下B模块的核心,特别是bar函数的核心:

Rec {
bar_xs
bar_xs = : x1_r3lO bar_xs
end Rec }

bar1 = $w!! bar_xs 10000000
--     ^^^ this repeats the computation. bar_xs is just repeat 1

bar =
  case trace $fCostlyi2 bar1 of _ { I# x_aDm -> I# (+# x_aDm 2) }
  --         ^^^ this is just the "costly!" string

那不行我们想要的.而不是重复使用costly,GHC决定只是内联costly功能.

因此,我们必须防止GHC内联成本高昂,否则计算将会重复.我们怎么做？你可能会认为添加一个{-# NOINLINE costly #-}pragma就足够了,但不幸的是,没有内联的专业化似乎不能很好地协同工作:

A.hs:13:3: Warning:
    Ignoring useless SPECIALISE pragma for NOINLINE function: ‘$ccostly’

但有一个技巧可以说服GHC做我们想做的事情:我们可以用costly以下方式写:

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = memo where
    memo :: i
    memo = trace "costly!" $ (repeat 1) !! 10000000
    {-# NOINLINE memo #-}
  {-# SPECIALIZE instance Costly Int #-}
-- (this might require -XScopedTypeVariables)

这使我们能够专门化costly,同时避免内联计算.