F#: 用于互递归数据结构的Catamorphisms

Question

假设有以下相互递归的结构：

type Tree<'a> = 
    | Empty 
    | Node of 'a * 'a Forest
and Forest<'a> = 
    | Nil 
    | Cons of 'a Tree * 'a Forest

目标：为此结构生成常见的消解函数：foldl、foldr和foldk。

我已经生成了原始消解函数，如下所示：

let rec foldTree fEmpty fNode fNil fCons = 
    function 
    | Empty -> fEmpty
    | Node (a, f) -> fNode a (foldForest fEmpty fNode fNil fCons f)
and foldForest fEmpty fNode fNil fCons =
    function
    | Nil -> fNil
    | Cons (t, f') -> fCons (foldTree fEmpty fNode fNil fCons t) (foldForest fEmpty fNode fNil fCons f')

我该如何“机械地”生成使用累加器的尾递归foldl和使用延续的尾递归foldr？

我已经阅读了Scott's Recursive Types and Folds series，并且理解如何“机械地”为递归结构生成折叠。但是，我无法在Google上找到任何关于递归数据结构的“机械”的内容。

注：可以通过内联来消除上面的相互递归，但让我们保留它，因为它代表了tpetricek's Markdown parser中相互递归的简化版本。

- Partha P. Das

---

“机械地”是什么意思？就我所看到的，您的函数已经实现了您想要的功能，但我不确定您想如何改进它？ - Tomas Petricek

在稍微不相关的注释中，我认为这种树处理方式在理论上很好，但实际上，编写更专门的函数来执行您可能实际想要在树上执行的常见树操作会更有用 - 并且让人们只需模式匹配即可获得完全通用的结构。换句话说，我认为“catamorphisms”对于可读代码并不是非常有用 - 这就是为什么Markdown解析器没有实现它们的原因 :) - Tomas Petricek

Answer 1

我不确定这是否符合您的要求，但似乎可以提供您想要的（在某种程度上）。

关键是仅处理类型“内部”的内容，并将“外部”的内容留给其他东西（某些抽象层）来处理。

//val foldTree : 'a -> ('b -> 'c -> 'a) -> ('b Forest -> 'c) -> 'b Tree -> 'a
let foldTree fEmpty fNode fForest = function
  Empty       -> fEmpty
| Node (a, f) -> fNode a (fForest f)

// val foldForest : 'a -> ('b -> 'a -> 'a) -> ('c Tree -> 'b) -> 'c Forest -> 'a
let rec foldForest fNil fCons fTree =
  let recurse = foldForest fNil fCons fTree
  function
    Nil         -> fNil
  | Cons (t, f) -> fCons (fTree t) (recurse f)

let foldForestAcc fNil fCons fTree =
  let rec aux acc = function
    Nil         -> acc
  | Cons (t, f) -> aux (fCons (fTree t) acc) f
  aux fNil

let foldForestCont fNil fCons fTree =
  let rec aux cont = function
    Nil         -> cont fNil
  | Cons (t, f) -> aux (fCons (fTree t) >> cont) f
  aux id

---

这里还有一个替代方案，如果更适合您的需求：

let fold fEmpty fNode fNil fCons =
  let rec auxT = function
    Empty       -> fEmpty
  | Node (a, f) -> fNode a (auxF f)
  and auxF = function
    Nil         -> fNil
  | Cons (t, f) -> fCons (auxT t) (auxF f)
  auxT

let foldAcc fEmpty fNode fNil fCons =
  let rec auxT acc = function
    Empty       -> acc
  | Node (a, f) -> fNode a (auxF fNil f)
  and auxF acc = function
    Nil         -> acc
  | Cons (t, f) -> auxF (fCons (auxT fEmpty t) acc) f
  auxT fEmpty

let foldCont fEmpty fNode fNil fCons =
  let rec auxT cont = function
    Empty -> cont fEmpty
  | Node (a, f) -> cont (fNode a (auxF id f))
  and auxF cont = function
    Nil -> cont fNil
  | Cons (t, f) -> auxF (cont >> fCons (auxT id t)) f
  auxT id

- Sehnsucht