问题标签 [recursion-schemes]

我想Foldable.toList用变形写一棵非空玫瑰树，但提取最后一个元素似乎是不可能的：

这确实是不可能的吗？它是否可以推广到所有非空结构？

另外（这是一个可选的奖励问题）是否有一个通用规则来确定何时Fix f -> Fix g可以使用 f 代数而不是 g 代数来实现？

顺便说一句，同构起作用了：

apo coalg6具有相同类型ana5但不丢失一个元素

我想使用“本地”重写器重写树：

所以我编写了在树的不同点rewriteGlobal应用相同的函数。match它需要一个“本地”Rewrite t并返回一个全局的。我只遍历树一次，没有尝试对每个树节点多次应用重写，直到不再可能进行重写。

但是有两种方法可以重写树。每次重写都对已重写的子树（WithChildren模式）或“原始”子树（WithoutChildren模式）进行操作。在后一种情况下，更高的重写“获胜”。

忽略 上的约束t， 的类型rewriteGlobal为：

这是一个实现：

liftChildRewrites而且liftA2 (<|>)看起来特别难看。

问题是：我不能做得更好吗？代码已经很短了，所以不是要让它更短。但是我是否朝着正确的方向前进，或者有比异态更好的局部匹配分布方法，例如更好的数据结构、单子方法或递归方案？

我没有避免替换的活页夹/名称/捕获，因此（P）HOAS 和类似方法可能不会更好。而且我没有实施 SKI 演算，这只是一个激励性的例子。

以下代码可用于测试：

问题是：是否有为本地重写设计的特定结构/方法？如果这种专门的方法不存在并且通用方法是我能做的最好的，它只是基于意见的。

斐波那契数列有一个优雅的定义：

可以翻译成使用recursion-schemes库吗？

我能得到的最接近的是以下使用完全不同方法的代码：

如有必要，我可以提供其余代码，但基本上我通过使用 Nat = Fix Maybe 的组织同态得到第 N 个斐波那契数。Maybe (Cofree Maybe a)结果与 同构[a]，因此refix可以认为只是toList使模式更短的一种。

更新：

我发现了更短的代码，但它只存储一个值并且以非通用方式：

存储完整历史记录的非通用方式：

我有一个表示算术表达式的数据类型：

我想编写一个扩展函数，它将表达式转换为变量乘积的总和（大括号扩展）。当然使用递归方案。

我只能以“进步和保存”的精神想到一种算法。每一步的算法都构建了完全扩展的术语，因此无需重新检查。

的处理Mul让我发疯了，所以我没有直接这样做，而是使用了同构类型[[String]]并利用concat并concatMap已经为我实现了：

那么我只使用cata：

并转换回来：

有明显更好的方法吗？

更新：很少有混淆。

1. 该解决方案确实允许多行变量名称。Add (Val "foo" (Mul (Val "foo) (Var "bar")))是 的表示foo + foo * bar。我不代表x*y*z什么Val "xyz"。请注意，由于没有标量，因此完全允许重复 var，例如“foo * foo * quux”。

2. 我所说的产品总和是指产品的“咖喱” n 元总和。乘积之和的一个简明定义是我想要一个没有任何括号的表达式，所有括号都由关联性和优先级表示。

所以(foo * bar + bar) + (foo * bar + bar)不是产品的总和，因为中间+是总和的总和

(foo * bar + (bar + (foo * bar + bar)))或相应的左关联版本是正确的答案，尽管我们必须保证关联性总是左而不是右。所以正确的关联解决方案的正确类型是

这与非空列表同构：（NonEmpty Poly注意Sum Mono Poly而不是Sum Poly Poly）。如果我们允许空的总和或产品，那么我们只会得到我使用的列表表示的列表。

3. 你们也不关心性能，乘法似乎只是liftA2 (++)

我编写了一个小程序来查找数字的素数分解。main除了抱怨找不到Show1实例的函数外，一切似乎都可以编译。

日志：

在下面的代码中，如何让 cataM 自上而下（而不是像目前的情况那样自下而上）遍历树？

我想我应该foldMap以不同的方式实现，但是如何在branch子节点之前处理节点本身，因为branch没有t不是子节点的实例？

对于我正在做的一个副项目，我目前必须处理一个抽象语法树并根据规则对其进行转换（细节并不重要）。

AST 本身是不平凡的，这意味着它具有仅限于某些类型的子表达式。（例如，运算符A必须采用B仅类型的参数，而不是 any Expr。我的数据类型的一个大大简化的简化版本如下所示：

我的目标是排除显式递归并改为依赖递归方案，正如这 两篇优秀的博客文章所展示的那样，它们提供了非常强大的通用工具来操作我的 AST。应用必要的因式分解，我们最终得到：

如果我没有搞砸，type Expr = Fix ExprF现在应该与之前定义的Expr.

然而，为这些案例编写cata变得相当乏味，因为我必须在 for 内部进行模式匹配才能B a :: StrF a进行良好的类型化。对于整个原始 AST，这是不可行的。Str :: ExprF acata

我偶然发现了修复 GADTs，在我看来这似乎是解决我的问题的方法，但是重复的高阶类型类等用户不友好的界面是相当不必要的样板。

所以，总结一下我的问题：

1. 将 AST 重写为 GADT 是解决此问题的正确方法吗？
2. 如果是，我如何将示例转换为运行良好的版本？第二点，现在 GHC 中是否有对更高种类的更好的支持Functor？

给定一个具有固定点的任意数据结构，我们可以在不手动指定所有情况的情况下构造一个单曲面代数吗？

假设我们得到如下数据类型Expr。使用该recursion-schemes库，我们可以派生一个基础仿函数，它也ExprF自动具有Functor和实例。FoldableTraversable

现在，假设我们要计算 中的叶子数expr。我们可以很容易地为这样一个小数据结构写一个代数：

现在，我们可以调用cata alg expr，它返回5正确的结果。

让我们假设Expr它变得非常庞大和复杂，并且我们不想为所有数据构造函数手动编写案例。怎么cata知道如何组合所有案例的结果？我怀疑这可能使用Monoids，可能与Const仿函数一起使用（虽然不完全确定最后一部分）。

fail返回4，而我们实际上有5叶子。我假设问题出在不动点上，因为我们只能剥一层Fixing，因此Mult [..]只能算作一片叶子。

是否可以在不手动指定所有实例的情况下以某种方式通用地折叠整个固定点并以类似Monoid结构的方式收集结果？我想要的是一种但更通用的方式。foldMap

我有一种感觉，我错过了一些非常明显的东西。

我一直在尝试构建一个替代品Lens.para，以在 para 函数工作时为它提供镜头上下文。但是，我似乎在某处的递归中犯了错误。

根据我对它的理解，它是递归代数数据类型中值Lens.para的一个变形函数。也就是说，它使用并采用一个函数来展开选项列表，以用于遍历一段数据的“自相似语法空间”，同时使其遍历数据上下文对函数可用这是工作。它的类型是，其中是数据上下文值的列表，并且是每个值的类型，它知道如何“查看”连续级别。platedLens.Plated a => (a -> [r] -> r) -> a -> r[r]a

我用于概念验证的极其简单的玩具示例数据类型如下：

data EExp a = ELit a | EAdd (EExp a) (EExp a) deriving (Show, Eq)

所以，这是我的代码，包括现有的工作版本showOptions和我的新版本，showOptions'它使用我的自定义Lens.para，称为paraApp. 不同之处在于，Pretext它在工作时将 a 与数据一起传递，以便稍后我可以调整我的代码，以便在需要时利用它Pretext来调整原始数据结构。

如果我进入GHCi并执行以下代码，它会提供预期的输出：

当我不想对上下文做任何事情（比如更新原始值的特定部分）时，这很好

因此，当我尝试替换功能时，会发生以下情况（应该与上述相同）：

显然我的递归在某个地方出错了，但我无法解决。与往常一样，我们将不胜感激任何帮助。

如果您不熟悉 的原始定义Lens.para，可以在https://hackage.haskell.org/package/lens-4.15.2/docs/src/Control.Lens.Plated.html#para找到

我有以下数据类型和示例方程，我想用 futumorphism 进行转换......

使用futu 这是我尝试编写一个函数以(Div (Num 1.0) (Num 4.0))从等式中分解出来。最后，我希望生成的树是(Mult (Div (Num 1.0) (Num 4.0)) (Add (Num 3.0) (Num 3.0))). 这个函数类型检查但我一定做错了什么，因为它在我运行它时没有评估。