scala - Scala 的 Option 以何种方式折叠 catamorphism？

Question

this的答案问题表明 Scala 中 Option 的 fold 方法是一种catamoprhism。来自维基百科 catamophism是“从初始代数到其他代数的独特同态。这个概念已被应用于函数式编程作为折叠”。所以这看起来很公平，但让我想到了 initial algebra作为F-algebras类别中的初始对象.

因此，如果 Option 上的折叠真的是一个 catamophism，则需要一些仿函数 F，以创建 F-代数的范畴，其中 Option 将是初始对象。我无法弄清楚这个仿函数是什么。

对于列表类型 A仿函数 F是 F[X] = 1 + A * X .这是有道理的，因为 List 是一种递归数据类型，所以如果 X是 List[A]然后上面的内容是 A 类型的列表要么是空列表( 1 )，要么是( + )一对( * )A和一个 List[A] .但是 Option 不是递归的。 Option[A]就是 1 + A (没有或 A )。所以我看不到仿函数在哪里。

为了清楚起见，我意识到 Option 已经是一个仿函数，因为它需要 A至 Option[A] ，但对列表所做的事情是不同的，A是固定的，仿函数用于描述如何递归构造数据类型。

与此相关的是，如果它不是 catamorphism，它可能不应该被称为折叠，因为这会导致一些 confusion .

Answer 1

嗯，评论是在正确的轨道上。我只是一个初学者，所以我可能有一些误解。是的，重点是能够对递归类型进行建模，但我认为没有什么可以排除“非递归”F 代数。由于初始代数是方程 X ~= F X 的“最小不动点”解。在 Option 的情况下，解是微不足道的，因为不涉及递归:)

初始代数的其他例子:

List[X] = 1 + A * X 代表 list = Nil |缺点列表

Tree[X] = A + A * X * X 代表树 = 叶子 a |节点一棵树

以同样的方式:

Option[X] = 1 + A 代表 option = None |一些

“常数”仿函数存在的理由很简单，你如何表示树的节点？
事实上，要对(简单)递归数据类型进行代数建模，您只需要以下仿函数:

U(单位，代表空)

K(常量，捕获一个值)

I(身份，代表递归位置)

*(产品)

+(副产品)

我找到的一个很好的引用是 Functional Generic Programming

无耻的插件:我在 scala-reggen 中的代码中玩弄这些概念