使用存在将值提升到类型而不损害性能

Question

我正在尝试对序列进行可组合折叠（类似于 foldl 库），但是在类型级别完成了更多的工作，希望编译器能够更轻松地进行内联和 CSE 处理（这些希望不是根据一些实验没有根据）。

为此，我有一个类型类（这是一个非常简化的示例）：

class Statistic a where
  type StateOf a = k | k -> a
  type ResultOf a = k | k -> a
  extract :: StateOf a -> ResultOf a
  computeStep :: StateOf a -> Double -> StateOf a
  ...

我也有几个基本实例

data Stats = Min | Max | Avg | Stddev

instance Statistic 'Min where ...
instance Statistic 'Max where ...
...

以及一个组合实例

data a ::: b = a ::: b

instance (Statistic a, Statistic b) => Statistic (a '::: b) where
  type StateOf (a '::: b) = StateOf a ::: StateOf b
  type ResultOf (a '::: b) = ResultOf a ::: ResultOf b
  extract (a ::: b) = extract a ::: extract b
  computeStep = ...

以及真正完成工作的东西：

run :: Statistic s => [Double] -> ResultOf s
run = ...

如果我做类似的事情run @('Avg '::: 'Stddev)，得到的代码性能与手写模拟大致相同，所以它看起来很有希望（而且它看起来也比 foldl 更好，证明了这些努力——它实际上看起来和run @('Stddev '::: 'Stddev)单个的一样快标准差！）。

但是如果我想编写一个命令行应用程序并允许用户选择他们想要计算的统计数据怎么办？我需要将术语（解析的选项）翻译成一种类型（的实例Statistic）！

这并不难，这段代码可以完成这项工作（我真的很喜欢 ghc 允许在模式中进行类型注释）：

data SomeStats where
  MkSomeStats :: (Statistic s, Show (ResultOf s)) => proxy s -> SomeStats

run' :: SomeStats -> [Double] -> String
run' (MkSomeStats (_ :: proxy s)) input = show $ run @s input

promoteStat :: Stats -> SomeStats
promoteStat Min = MkSomeStats (Proxy :: Proxy 'Min)
promoteStat Max = MkSomeStats (Proxy :: Proxy 'Max)
...

promoteStats :: [Stats] -> SomeStats  -- uh oh, I should've used NonEmpty
promoteStats [s] = promoteStat s
promoteStats (s:ss) =
  case (promoteStat s, promoteStats ss) of
       (MkSomeStats (_ :: proxy1 s), MkSomeStats (_ :: proxy2 ss)) -> MkSomeStats (Proxy :: Proxy (s '::: ss))

结果甚至可以正常工作，但结果代码的性能很糟糕，比没有任何存在性的直接类型应用程序的变体差一两个数量级。这实际上是有道理的——现在编译器没有机会内联东西，它只需要携带Statistic类的字典，即使是Statistic!

在这一点上，我实际上正在考虑使用 Template Haskell 生成一个选项处理程序2^|Stats| - 1 case，它只会生成分支，但它看起来不雅。有没有更好的办法？