recursion - F#:互递归数据结构的变态

Question

假设以下相互递归结构:

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

目标:为这个结构生成常见的变形:foldl、foldr、foldk。

我已经生成了如下的 naive-catamorphism:

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')

我如何“机械地”生成尾递归折叠(使用累加器)和尾递归折叠(使用延续)？

我经历过Scott's Recursive Types and Folds series并且我了解如何“机械地”为递归结构生成折叠。但是我在谷歌上找不到任何东西来为递归数据结构做“机械”的事情。

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

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