在存在一些递归案例时保持内联的可能性

Question

请考虑以下数据类型,该类型仅用于管理:

data D where
  D1 :: Int -> D
  D2 :: String -> D
  DJ :: D -> D -> D

也许它上面有一个功能,说toString:

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> "Int: show x"
  (D2 x) -> "String: show x"
  (DJ x y) -> "(" ++ toString x ++ "," ++ toString y ++ ")"

(值得注意的是,我所做的与打印无关,这只是一个说明性的例子)

所以我发现通过toString这样的定义使我的程序快15倍:

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> "Int: show x"
  (D2 x) -> "String: show x"
  (DJ x y) -> undefined

发生的事情toString现在能够被GHC内联.这允许在未来的道路上进行大量的优化.该DJ案件是什么造成的问题.那么我试过这个:

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> intShow x
  (D2 x) -> strShow x
  _ -> go x
  where
    go (D1 x) -> intShow x
    go (D2 x) -> strShow x
    go (DJ x y) -> "(" ++ go x ++ "," ++ go y ++ ")"
    intShow x = "Int: show x"
    strShow x = "String: show x"

这实际上意味着它可以快速编译.原因是(我很确定无论如何)因为toString不再是递归的.go是,但toString不是.因此编译器将很乐意内联toString,允许更多优化.

但在我看来,上述代码是丑陋的.

就像我说的,我的功能比这更复杂,这种问题在我的代码中都会出现.我有一个包含许多构造函数的数据类型,有些是简单的,有些是递归的.然而,每当我定义一个递归的情况时,即使是简单的情况也会减慢速度.有没有办法保持顶部函数内联而不像我上面那样使用代码？

Answer 1

我没有优雅的解决方案,但也许这样的事情可行.未经测试.

{-# INLINE toString #-}
toString x = go (fix go)  -- equivalent to (fix go), but unrolled once
  where
  {-# INLINE go #-}
  go _ (D1 x) -> intShow x
  go _ (D2 x) -> strShow x
  go k (DJ x y) -> "(" ++ k x ++ "," ++ k y ++ ")"
  intShow x = "Int: show x"
  strShow x = "String: show x"