当存在一些递归情况时，保持内联的可能性

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"

Answer 2

我认为您已经正确确定了问题以及必须采取哪些措施来解决问题，通常(我同意不是超级令人满意)：

• 马克·INLINE
• ETA摆弄，以便在呼叫现场完全应用左侧
• 添加一个简单的间接层，以便函数不是递归的

但我认为这样的事情在这里应该足够了：

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

正如 chi 在他们的回答中指出的那样，您在这里所做的似乎是一个手动的单级循环展开;很容易看出为什么这会更快，比如：

(DJ (D1 0) (D2 "zero"))

但不太明显的是，例如，当您深度嵌套DJ时，这会好得多。我很想知道，看看你是如何进行基准测试的。

大多数时候，我们关心以这种方式内联，因为我们的x是多态的，我们希望我们呼吁体内x的功能是专业化的。或者我们希望结果保持无框类型。

Answer 3

我已经给出了@chi勾线以上，因为他的出色回答涉及fix确实完成了这项工作。但是有点繁琐，因为在我的情况下，我的递归是多态的(fix单态)，所以我不得不滚动自己的fix.

我还担心，通过传递递归参数而不是直接调用它可能会进一步混淆编译器与递归情况。

但是受到@chi回答的启发，并认为我基本上想要两个相同的函数，一个非递归函数和一个递归函数，然后我意识到我可以这样做，就像这样：

import Data.Proxy (Proxy(Proxy))
toString x = go' (Proxy :: Proxy True)
{-# SPECIALISE INLINE go' :: Proxy True -> String #-}
go' :: (Proxy a) -> String
go' _ = case x of
(D1 x) -> "Int: show x"
(D2 x) -> "String: show x"
(DJ x y) -> "(" ++ go x ++ "," ++ go y ++ ")"
go = go' (Proxy :: Proxy False)

由于go'的特殊性，编译器将发出两个go'函数，一个用于Proxy参数True时，另一个用于False参数。

第一个，当它被True时，不是递归的，它从不调用自己(它只调用False版本)。因此，如果我们对此进行专业化，它是可内联的。因为go' (True)不是递归的，所以toString也是递归的，因为toString所做的只是调用go' (True)，所以toString是可内联的。

这种方法需要一点样板，但至少样板的长度是恒定的，它不会随着您需要处理的构造函数数量而增加。