PL | 递归数据结构

算法与结构的递归同构

在上期博客里，我提到一个问题：

对于尾递归的链表排序，似乎需要创造一个很逆天的 Zipper！有没有能利用上 ADT 的更好的思路？

该论文^1 中的 Hylomorphisms 表达的差不多正是这种东西！同时，论文揭示了 Hylomorphisms 为 Catamorphisms 和 Anamorphisms 的复合。然而，原论文充斥着猫话，我选择选择看原论文比较简明的部分，再加上一些论文解读^2，一系列对 Recursion Schemes 的介绍博客^3，以及一篇 Medium 文章^4。

目的论地，我们可以直接整一个更适合用于排序的 ADT，这里是二叉树，也是我们整个递归函数的递归结构。这时用 Anamorphism 从数组生成二叉树，用 Catamorphism 从二叉树生成数组即可。

1
2
3
4
5
6
7
8
9
10
mergeSort :: Ord a => [a] -> [a]
mergeSort = hylo alg coalg where
  alg EmptyF      = []
  alg (LeafF c)   = [c]
  alg (NodeF l r) = merge l r

  coalg []  = EmptyF
  coalg [x] = LeafF x
  coalg xs  = NodeF l r where
    (l, r) = splitAt (length xs `div` 2) xs

事实上，Anamorphism 是满射（这会导致部分不同的值被映射到相同的「递归结构实例」，这也是理解记忆化^5 只能对 Anamorphism 做的一条路径），Catamorphism 是单射，观察一些自然数递归容易感受到这一规律。

一些小改进

介绍系列大部分讲的是关于 Catamorphisms 和 Anamorphisms 的小改进：

  • Paramorphism: 保留原参数的可引用性
    • 如果在想实现就地修改的时候，只需要使用 Ana- + Catamorphism 就够了
  • Apomorphism: 即使 ADT 没有单位元，也允许 break
  • Histomorphism: 记录结果历史
    • 无法实现自动记忆化，记忆化的课题需要和 Vector 一同探索
  • Futumorphism: 允许返回多层嵌套结构
  • Chrono- / Hypomorphism: 先前东西的神秘组合

bind 可以自动生成

上面生成的是 map、cata、ana、fold 之类的函数，但其实 bind 也是可以生成的。

在参数化 ADT，例如 Interaction next，使之成为 Functor 后，Free Monad^6 可以自动为 Free Interaction r = Free (Interaction (Free Interaction)) | Pure r 生成 bind 函数。其和 Fix 的区别就是添加了单位元 Pure r，但这也使其实例有了可控的递归层数，拥有了 Futumorphism 的性质。

下一步

  • 尝试更多例子
    • 尝试改成 fully in-place 的版本
  • 恶补猫论知识，了解对偶到底是什么含义