Agda的递归方案 [英] Recursion Schemes in Agda

问题描述

不用说，Haskell的标准构造

  newtype修复f =修复{getFix :: f（修复f） } 
 
 cata ::（Functor f）=> （f a  - > a） - >修复f  - > 
 cata f = f。 fmap（cata f）。 getFix 
  

非常棒，非常有用。

试图在Agda中定义一个类似的东西（我只是为了完整起见）

  data修复（f：Set - > Set）：Set where 
 mkFix：f（Fix f） - >修正f 
  

失败，因为 f 不一定严格肯定。这是有道理的 - 我可以很容易地从这个结构中挑选适当的矛盾。

我的问题是：在Agda有没有希望编码递归方案？它完成了吗？什么是需要的？

解决方案

你会在 Ulf Norell的标准Agda教程！

不幸的是，并非所有通常的递归方案都可以真正被编码，因为所有破坏的方法都会消耗数据，而所有构造方法都会产生数据，所以将一个喂入另一个的概念必然是部分的。你也许可以在偏袒的monad中做到这一切，但这并不令人满意。尽管这些分类主义者认为哈斯克尔的真正类别是CPO⊥，但它的初始代数和终端余代数是一致的，所以它们或多或少是这样。

Needless to say, the standard construction in Haskell

newtype Fix f = Fix { getFix :: f (Fix f) }

cata :: (Functor f) => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . getFix 

is awesome and extremely useful.

Trying to define a similar thing in Agda (I'll put it just for completeness sake)

data Fix (f : Set -> Set) : Set where
    mkFix : f (Fix f) -> Fix f

fails because f is not necessarily strictly positive. This makes sense -- I could easily get a contradiction from this construction by picking appropriately.

My question is: is there any hope of encoding recursion schemes in Agda? Has it been done? What would be required?

解决方案

You'll find such a development (over a restricted universe of functors) in Ulf Norell's canonical Agda tutorial!

Unfortunately not all the usual recursion schemes can really be encoded because all the "destructiony" ones consume data and all the "constructiony" ones produce codata, so the notion of feeding one into the other is necessarily partial. You could probably do it all in the partiality monad but that's rather unsatisfactory. That is more or less what the categorists are doing when they say that Haskell's "true category" is CPO⊥ though, because its initial algebras and terminal coalgebras coincide.

这篇关于Agda的递归方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！