问题标签 [recursion-schemes]

下面是我编写的一些代码，作为使用parafrom的练习recursion-schemes（我知道这个简化的示例也可以使用 just 来解决cata，但对于这个问题我们忽略它）。

在执行此操作时，我注意到para如果我想访问Depth构造函数

我找到了 and 的替代实现，gcata'它para'没有这个问题，也不需要，Comonad而只是Functor. w这让我想知道：为什么没有在实现中使用这个版本recursion-schemes？它有什么问题，还是有更好的方法来实现我正在寻找的东西？

这是一个如何使用它的示例：

正如你所看到的，两个函数都做同样的事情，计算树的最大深度（不计算最外层depth调用本身）

我有一个具有 Functor 实例的递归数据类型：

现在，我有兴趣修改此数据类型以支持通用递归方案，如本教程和本 Hackage 包中所述。我设法让变态起作用：

但现在我不知道如何给出Expr2与原来相同的仿函数实例Expr。尝试定义仿函数实例时似乎存在一种不匹配：

如何为 编写 Functor 实例Expr2？

我曾考虑将 Expr2 包装在一个 newtype 中，newtype Expr2 a = Expr2 (Fix (ExprF a))但是这个 newtype 需要被解包才能传递给cata，我不太喜欢。我也不知道是否可以Expr2像我一样自动派生仿函数实例Expr1。

许多 catamorphisms 似乎很简单，主要用自定义函数替换每个数据构造函数，例如

但是，我不清楚的是，如果使用相同类型的构造函数但使用不同的类型参数会发生什么。例如，而不是传递 a List ato Cons，怎么样

或者，也许是一个更疯狂的案例：

我对这???部分的两个看似合理的想法是

• (a -> b -> b)，即List递归替换构造函数的所有应用程序）
• (a -> List b -> b)，即仅替换所有List a应用程序。

两者中哪一个是正确的——为什么？还是会完全不同？

我正试图围绕变形的概念。

在函数式编程中，变形是对列表展开概念的概括。形式上，变形是通用函数，可以核心递归地构造某种类型的结果，并由确定下一个构造步骤的函数参数化。

它的双重性，catamorphism，在这篇文章中有很好的描述：什么是 catamorphism，它可以在 C# 3.0 中实现吗？.

C# 中多变行为的一个很好的例子是 LINQ 的Aggregate方法。

什么是变形等价物？将伪随机数生成器Random视为变形构造是否正确，或者展开过程是否应该始终包含如下所示的累加器函数（取自Intro to Rx的代码片段）？

我希望能够cata从recursion-schemes包中使用 Church 编码中的列表。

为方便起见，我使用了第二等级类型，但我不在乎。如果您认为有必要，请随意添加newtype、使用 GADT 等。

Church 编码的想法广为人知且简单：

基本上是“抽象的未指定”cons并且nil被用来代替“普通”的构造函数。我相信一切都可以用这种方式编码（Maybe、树等）。

很容易证明它List1确实与普通列表同构：

所以它的基础仿函数与列表相同，应该可以实现project它并使用recursion-schemes.

但我不能，所以我的问题是“我该怎么做？”。对于普通列表，我可以进行模式匹配：

由于我无法对函数进行模式匹配，因此我必须使用折叠来解构列表。project我可以为普通列表编写一个基于折叠的：

但是，我未能将其改编为 Church 编码列表：

cata具有以下签名：

要将它与我的列表一起使用，我需要：

1. 使用声明列表的基本函子类型type family instance Base (ListC a) = ListF a
2. 实施instance Recursive (List a) where project = ...

我在两个步骤中都失败了。

在阅读（并实现） http://blog.sumtypeofway.com/recursion-schemes-part-2/的一部分之后， 我仍然想知道cata函数中的类型是如何工作的。cata函数定义为：

我有类似的东西Term Expr。打开包装后我得到Expr (Term Expr). 代数 ( f) 被定义为f :: Expr Int -> Int。我知道我可以轻松调用以下命令：

我也可以想象：

但我认为以下内容行不通：

但是，我仍然不明白它在cata函数中的工作原理 - 我如何从Expr (Term Expr)to获取Expr a. 我知道这些值确实有效，但我只是没有得到类型 - 树的叶子会发生什么？这确实是一个mystery...

编辑：我会尝试更清楚地说明我不明白的内容。

在精神上，cata似乎是这样工作的：

• 适用fmap f于叶子。
• 现在我有了Expr Int，我可以调用fmap f我拥有的节点并继续前进。

在我申请时，它显然不是这样工作的fmap (cata f)。但是，最终该函数f被Expr Int作为参数调用（在叶子中）。这种类型是如何从Expr (Term Expr)以前的类型中产生的？

我最终弄清楚了。看我演讲的视频和幻灯片：

• 幻灯片/pdf

• 视频

原始问题：

在我努力理解通用递归方案（即使用Fix）的过程中，我发现编写各种方案的仅列表版本很有用。它使理解实际方案变得更加容易（没有额外的开销Fix）。

但是，我还没有弄清楚如何定义 和 的仅列表zygo版本futu。

到目前为止，这是我的专业定义：

你如何定义histo,zygo和futufor 列表？

我正在玩Data.Fixand Data.Functor.Sum，并尝试使用catasum of functors，然后遇到了代码没有类型检查的问题。但我不确定如何进行类型检查。

这是代码。

首先，我有三个函Zero子Succ和Add。我使用Sum并定义了它们type Expr = Sum Zero (Sum Succ Add)。

我还有Value将每个仿函数转换为数字的课程。由于我不想自己编写Valuefor的实例Sum，所以我介绍IsPartOf了知道如何构造函子之和 ( inj) 以及如何将内部函子的函数应用于外部函子 ( app) 的类。

但是当我尝试使用它们时cata (app value) (succ zero)，GHC 说它不进行类型检查。

为什么 GHC 找不到合适的实例？我怎样才能进行这种类型检查，或者什么是表达这个想法的正确方法？

我用 GHC 7.10.3 试过这个。

我有这个简单的ExprAST，我可以轻松地将其转换为String.

现在我想向它添加一个额外的数据。所以我正在尝试使用Cofree

我可以转换Expr为Expr2

但我不知道如何转换Expr2为String

另外，Cofree 是解决这个注释问题的最好方法吗？

我有这个 AST

我想比较

但是所有递归方案函数似乎只适用于单一结构

显然我可以使用递归

但我希望可以使用某种 zipfold 功能。