相关疑难解决方法(0)

我不能让Agda的终止检查器接受使用结构感应定义的函数.

我创建了以下内容作为我认为最简单的例子来展示这个问题.以下定义size被拒绝,即使它总是在严格较小的组件上进行递归.

module Tree where

open import Data.Nat
open import Data.List

data Tree : Set where
  leaf : Tree
  branch : (ts : List Tree) ? Tree

size : Tree ? ?
size leaf = 1
size (branch ts) = suc (sum (map size ts))

这个问题有通用的解决方案吗？我是否需要Recursor为我的数据类型创建一个？如果是的话,我该怎么做？(我想如果有一个如何定义Recursorfor 的示例List A,那会给我足够的提示吗？)

我想在agda中实现合并排序.如果我以天真的方式执行此操作,终止检查程序无法通过程序,因为在我们将输入列表分成两部分,然后递归调用自己之后,agda不知道每个列表的大小小于大小原始清单.

我已经看过几个解决方案,例如这个:https://gist.github.com/twanvl/5635740但代码对我来说似乎太复杂了,最糟糕的是我们混合了程序和证明.