使用map遍历递归数据结构时如何通过完全性检查？

我完全懂你的痛点——Idris的终止检查器有时候确实会在高阶函数递归上卡壳，逼得我们手动展开代码，完全没了函数式编程的优雅。不过别担心，有几个实用的办法能解决这个问题，不用处处依赖assert_total或者手动展开：

1. 用大小类型给检查器明确的终止线索 #

Idris的终止检查器需要看到递归是在更小的子结构上进行的，给你的Tree加上大小参数，就能清晰地告诉检查器每次递归调用的结构都比原结构“小”：

data Tree : Size -> Type where
  Branches : List (Tree size) -> Tree (size + 1)
  Node : Int -> Tree (size + 1)

sumTree : Tree size -> Int
sumTree (Branches xs) = sum (map sumTree xs)
sumTree (Node x) = x

这里的Size参数让检查器能追踪到，Branches里的每个子Tree的大小都比当前Tree小，所以递归必然终止，不用手动展开map就能通过检查。

2. 用total关键字让编译器更努力地验证 #

如果确定你的函数是终止的，但检查器没自动识别出来，可以给函数加上total关键字——这比assert_total更安全，因为它会让编译器尝试做更深入的验证，而不是直接跳过检查：

total sumTree : Tree -> Int
sumTree (Branches xs) = sum (map sumTree xs)
sumTree (Node x) = x

很多时候，这个关键字能让检查器意识到map和sum的组合是终止的，毕竟标准库中的这些高阶函数本身已经被标记为total了。

3. 封装自定义的已验证辅助函数 #

如果标准库的组合满足不了需求，你可以提前写一个带有终止证明的辅助函数，之后直接复用它就行。比如封装一个sumMap，专门处理递归求和的场景：

total sumMap : (a -> Int) -> List a -> Int
sumMap f [] = 0
sumMap f (x::xs) = f x + sumMap f xs

sumTree : Tree -> Int
sumTree (Branches xs) = sumMap sumTree xs
sumTree (Node x) = x

sumMap已经被验证为完全函数，sumTree调用它的时候，检查器就能直接识别出递归的终止性，不用再手动展开逻辑。

4. 确保你的数据结构是严格归纳的 #

有时候检查器卡壳，是因为它没法确定你的数据结构不会产生无限递归。比如你的List Tree本身是有限的（Idris的List是严格有限的归纳类型），只要你的Tree定义没有无限分支的可能，调整一下函数的写法，让检查器能关联到这种有限性，也能通过检查。

总的来说，优先尝试大小类型和total关键字，这两个方法最直接，也能最大程度保留函数式编程的简洁性。

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