运行-使用 GHC 进行依赖类型编程的时间成本

Question

我正在 Haskell 中编写依赖类型的库。在我的测试可执行文件上使用分析我看到类似的东西：

commutativity' Math 1189 4022787186 29.1 27.2 29.1 27.2

commutativity' 基本上（递归）证明了类型级整数的整数加法交换性属性。它是这样定义的：

commutativity' :: SNat n -> SNat m -> Plus (S n) m :~: Plus n (S m)
commutativity' SZ m = Refl
commutativity' (SS n) m = gcastWith (commutativity' n m) Refl

然后在我的库中与gcastWith一起使用来证明各种类型的等价性。

所以...我 29% 的运行时间花在了完全无用的事情上，因为类型检查发生在编译时。

我天真地以为这不会发生。

我可以做些什么来优化这些无用的调用吗？

Answer 1

如果您非常确定证明期限终止，您可以使用类似

的东西

unsafeProof :: proof -> proof
unsafeProof _ = unsafeCoerce ()

someFunction :: forall n m.  ...
someFunction = case unsafeProof myProof :: Plus (S n) m :~: Plus n (S m) of
   Refl -> ...

这只能用于具有单个无参数构造函数的类型，例如Refl 对于 a :~: b。否则，您的程序可能会崩溃或行为异常。买者自负！

一个更安全（但仍然不安全！）的变体可能是

unsafeProof :: a :~: b -> a :~: b
unsafeProof _ = unsafeCoerce ()

请注意，如果将 bottom 传递给它，您仍然可以使用它使程序崩溃。

希望有一天 GHC 能够安全自动地执行此优化，确保通过静态分析终止。

运行-使用 GHC 进行依赖类型编程的时间成本

Run-time cost of dependently-typed programming with GHC

optimization

haskell

runtime

compile-time

dependent-type