问题标签 [recursion-schemes]

使用递归方案库，可以轻松编写抽象语法树和相应的表达式评估器：

现在看一下algwhere 子句中函数中的 case eval。我认为所有的x和y变量都不应该是必要的。因此，我正在寻找某种方法（语法、语言扩展等）来删除这个样板，然后写：

以下是列表的一些简单 F 代数。它们使用递归方案库中的cata函数 。

现在我编写它们：

doubleAndTriple按预期工作。两个代数都是结构保留的，它们不会改变列表的长度，因此 cata 可以将两个代数应用于列表的每个项目。

下一个是过滤器和双重：

它不能正常工作。我认为这是因为algFilterBig没有保留结构。

现在是最后一个例子：

这里两个代数都不是结构保留的，但这个例子是有效的。

构成 f 代数的确切规则是什么？

Wikipedia writes about Hylomorphism:

In [...] functional programming a hylomorphism is a recursive function, corresponding to the composition of an anamorphism (which first builds a set of results; also known as 'unfolding') followed by a catamorphism (which then folds these results into a final return value). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is an example of deforestation, a program optimization strategy.

(Bold markup by me)

Using the recursion-schemes library I wrote a very simple hylomorphism:

In the cabal file I instructed GHC to optimize the code:

Using stackage lts-10.0 (GHC 8.2.2) I compile with stack build and run with stack exec Hylo -- +RTS -s and I get:

Now I change hylosum 1000 to hylosum 1000000 (1000 times more) and I get:

So heap usage goes up from 84 KB to 16,664 KB. This is 200 times more than before. Therefore I think, GHC does not do the deforestation / fusion mentioned in wikipedia!

This is not really a surprise: The anamorphism creates the list items from left to right (from 1 to n) and the catamorphism consumes the items the opposite way from right to left (from n to 1) and it's difficult to see how the hylomorphism can work without creating the whole intermediate list.

Questions: Is GHC able to perform the deforestation? If yes, what do I have to change in my code or cabal file? If yes, how does it really work? if no, where is the issue: in wikipedia, GHC or in the library?

作业问题：

(diginlist '(4 5 3 2 8))应该返回(4(5(3)2)8)

返回：

(list (list (list (list (list '())))))

我知道我应该合并 removelast 和 last，但我在这样做时遇到了麻烦。

这个问题是部分理论/部分实施。背景假设：我使用monad-bayes库将概率分布表示为 monad。分布 p(a|b) 可以表示为函数MonadDist m => b -> m a。

假设我有一个条件概率分布s :: MonadDist m => [Char] -> m Char。我想得到一个新的概率分布sUnrolled :: [Char] -> m [Char]，在数学上（我认为）定义为：

直观地说，它是您通过获取、从st :: [Char]中采样新字符、反馈到中等获得的分布。我相信或多或少是我想要的。为了使它成为我们可以实际查看的分布，假设如果我们击中某个角色，我们就会停止。然后工作。cs stst++[c]siterateM siterateMaybeM

理论问题：由于各种原因，如果我可以用更一般的术语来表达这种分布，那将非常有用，例如，在给定随机余代数的情况下，可以推广到树的随机构造。看起来我在这里有某种变形（我意识到数学定义看起来像变形，但在代码中我想建立字符串，而不是将它们解构为概率）但我不太清楚细节，不是至少是因为概率单子的存在。

实际问题：例如，以使用递归方案库的方式在 Haskell 中实现这一点也很有用。

按照这个优秀系列中的术语，让我们表示一个表达式，例如(1 + x^2 - 3x)^3by a Term Expr，其中数据类型如下：

是否有适合执行符号微分的递归方案？我觉得它几乎是专门用于 的 Futumorphism Term Expr，即futu deriveFutu用于适当的功能deriveFutu：

这看起来很不错，只是下划线的变量是Terms 而不是CoAttrs：

没有递归方案的版本如下所示：

作为对这个问题的扩展，是否有一种递归方案来区分和消除“空” Expr，例如由于Plus (Const 0) x差异而出现的“空”——一次遍历数据？

所以我一直在尝试将这个检查列表是否没有任何重复的 Haskell 函数转换为 Hylomorphism，但它有些奇怪。

如果有人可以提供帮助，我会很高兴！谢谢

我有一个我正在使用注释的 AST Cofree：

我type Expr = Fix ExprF用来表示未标记的 AST，并type AnnExpr a = Cofree ExprF a表示标记的 AST。我想出了一个函数，通过丢弃所有注释将标记的 AST 转换为未标记的 AST：

这看起来可能是某种变态（我使用的是 Kmett 的recursion-schemes包中的定义）。

我认为使用 catamorphism 重写的上述内容看起来像这样，但我不知道要放置什么来alg进行类型检查。

任何帮助确定这是否真的是 cata/anamorphism，以及为什么它是/不是的一些直觉将不胜感激。

现在，我有一个表达式的 AST，它在递归类型上是多态的：

这非常有用，因为它允许我使用一种类型进行普通递归 ( Fix Expr) 并在我需要附加额外信息时使用另一种类型 ( Cofree Expr ann)。

当我想在此递归方案中引入另一种类型时，会出现此问题：

Expr如果不引入额外的类型变量并破坏与我已经编写的所有通用函数的兼容性，我不确定该术语的含义。

可以做到这一点，如果可以，这是一个有用的模式吗？

Cofree根据这篇文章，我正在尝试通过变形创建一个结构。但是编译器抱怨类型不匹配：

但是在package的源码中recursion-schemes，有一个类型实例定义：

如何使 haskell 编译器成功地将该类型与该特定类型实例方程统一起来？

代码与链接中的代码几乎相同：

以及确切的错误信息：