Scala的选项以什么方式折叠了一个变形？

Question

这个问题的答案表明,Scala中Option的fold方法是一种catamoprhism.从维基百科中,一个catamophism是"从初始代数到其他代数的独特同态.这个概念已经应用于函数式编程作为折叠".所以这似乎是公平的,但引导我将初始代数作为F-代数类别中的初始对象.

因此,如果Option上的折叠实际上是一个catamophism,那么需要有一些仿函数F来创建F代数的类别,其中Option将是初始对象.我无法弄清楚这个仿函数是什么.

对于类型列表,A仿函数F是F[X] = 1 + A * X.这是有道理的,因为List是一个递归数据类型,所以如果X是,List[A]那么上面读取的类型列表A是空列表(1),或(+)a 和a的一对(*).但Option不是递归的.只会(没什么或一个).所以我没看到仿函数在哪里.AList[A]Option[A]1 + AA

只是要清楚,我认识到,期权已经是一个仿函数,因为它需要A给Option[A],但是什么名单做是不同的,A是固定的,仿函数是用来描述如何构建递归的数据类型.

在一个相关的说明中,如果它不是一个catamorphism它可能不应被称为折叠,因为这会导致一些混乱.

Answer 1

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

初始代数的其他例子：

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

Tree[X] = A + A * X * X 表示tree = Leaf a | 节点一棵树

以同样的方式：

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

“常量”函子存在的理由非常简单，如何表示树的节点？事实上，要对（简单）递归数据类型进行代数建模，您只需要以下函子：

• U（单位，代表空）
• K（常数，捕获一个值）
• I (Identity，代表递归位置)
• * （产品）
• +（联积）

我发现的一个很好的参考是函数式通用编程

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