Haskell如何消除函数显式递归 解决Foldable类型推导报错

初始代码骨架如下：

f :: (Monad m) => b -> m ()
f x = traverse_ (f . g x) =<< h x -- 待解决：如何消除此处的显式递归？
g :: b -> a -> b
-- 待排查：将h泛化为Foldable约束版本时，报"Could not deduce (Foldable t0) arising from a use of ‘traverse_’"错误
-- h :: (Foldable t) => b -> m (t a)
h :: b -> m [a]

核心问题有两个：

• 如何消除f定义中的显式递归？
• 尝试将h的返回类型从具体的[a]泛化为带Foldable t约束的m (t a)时类型检查失败，报错原因是什么？

消除显式递归的方法 #

使用Control.Monad提供的不动点组合子fix即可消除显式递归。fix会自动将递归引用注入处理逻辑，无需函数在定义中显式调用自身。
首先引入需要的依赖：

import Control.Monad (fix)
import Data.Foldable (traverse_)

重构后的无显式递归版本如下：

f :: (Monad m, Foldable t) => (b -> a -> b) -> (b -> m (t a)) -> b -> m ()
f g h = fix $ \recur x -> traverse_ (recur . g x) =<< h x

该写法中，递归调用的引用由fix作为recur参数传入，整个f的定义没有出现自引用，完全消除了显式递归。

Foldable泛化报错的原因 #

报错根因是最初的泛化写法没有将Foldable t约束对应的类型变量t绑定到f的顶层类型签名上：如果仅给h单独标注带Foldable t的类型，GHC无法确认递归调用时t的类型是否一致，会生成一个独立的、无法确定具体实例的t0类型变量，自然找不到对应的Foldable实例。
修复方式是将g、h作为f的显式参数，把Foldable t约束放在f的顶层类型签名中，保证全函数范围内t类型统一，即可通过类型检查。

该逻辑实际用于监控摄像头录像目录的递归遍历：Right分支处理名称为整数的子目录，继续向下递归；Left为基例，处理名称非整数的叶子节点，对应业务代码如下：

-- 辅助组合子，将两个分支函数组合为Either类型的处理函数
a <|||> b = left a . right b

doDir :: Either FilePath FilePath -> IO ()
doDir (Right d) = traverse_ (doDir . doInt) =<< listDirectory d 
  where doInt s = ((<|||>) <$> (,) <*> const) (d </> s) $ (TR.readEither :: String -> Either String Int) s

代码中各部分和骨架的对应关系：

• f对应doDir
• g对应doInt的路径拼接、整数判断逻辑
• h对应listDirectory，用于获取指定目录下的所有子项

内容的提问来源于stack exchange，提问作者user1441998