8

我正在尝试将 Brian 的二叉树折叠 ( http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ ) 用于申请多路树。

来自 Brian 的博客的总结：

数据结构：

type Tree<'a> =  
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a>  
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),  
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

二叉树折叠函数

let FoldTree nodeF leafV tree =   
    let rec Loop t cont =   
        match t with   
        | Node(x,left,right) -> Loop left  (fun lacc ->    
                                Loop right (fun racc ->   
                                cont (nodeF x lacc racc)))   
        | Leaf -> cont leafV   
    Loop tree (fun x -> x)

例子

let SumNodes = FoldTree (fun x l r -> x + l + r) 0 tree7
let Tree6to0 = FoldTree (fun x l r -> Node((if x=6 then 0 else x), l, r)) Leaf tree7

多路树版本 [不（完全）工作]：

数据结构

type MultiTree = | MNode of int * list<MultiTree>

let Mtree7 = MNode(4, [MNode(2, [MNode(1,[]); MNode(3, [])]);  
                    MNode(6, [MNode(5, []); MNode(7, [])])])

折叠功能

let MFoldTree nodeF leafV tree = 
    let rec Loop  tree cont =   
        match tree with   
        | MNode(x,sub)::tail -> Loop (sub@tail) (fun acc -> cont(nodeF x acc))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x)

示例 1 返回 28 - 似乎有效

let MSumNodes = MFoldTree (fun x acc -> x + acc) 0 Mtree7

示例 2

不运行

let MTree6to0 = MFoldTree (fun x acc -> MNode((if x=6 then 0 else x), [acc])) Mtree7

最初我认为MFoldTree需要一个map.something地方，但我让它与@操作员一起工作。

对第二个示例的任何帮助和/或纠正我在MFoldTree函数中所做的事情都会很棒！

干杯

杜西奥德

4

2 回答 2

9

诀窍是你需要传递一个额外的函数来折叠。

在 Brian 的版本中， fold 函数只nodeF使用节点中的值和左右子树产生的两个值调用。

这对于多路树来说是不够的。在这里，我们需要一个nodeF使用节点中的值调用的函数，以及通过聚合子树的所有值产生的结果。但是您还需要一个函数 - 比如说combineF结合从节点的多个子树产生的值。

您的 fold 函数是一个好的开始 - 您只需要再添加一个递归调用 process tail：

let MFoldTree nodeF combineF leafV tree = 
    let rec Loop trees cont =   
        match trees with   
        | MNode(x,sub)::tail -> 
            // First, process the sub-trees of the current node and get 
            // a single value called 'accSub' representing (aggregated)
            // folding of the sub-trees.
            Loop sub (fun accSub -> 
              // Now we can call 'nodeF' on the current value & folded sub-tree
              let resNode = nodeF x accSub
              // But now we also need to fold all remaining trees that were
              // passed to us in the parameter 'trees'..
              Loop tail (fun accTail ->
                // This produces a value 'accTail' and now we need to combine the
                // result from the tail with the one for the first node 
                // (which is where we need 'combineF')
                cont(combineF resNode accTail) ))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x)

求和很容易，因为我们只+对这两个函数使用运算符：

let MSumNodes = MFoldTree (+) (+) 0 Mtree7

过滤树更加棘手。该nodeF函数将获取节点中的元素和子节点列表（即聚合的结果）并生成单个节点。该combineF函数将从第一个节点（即一个MultiTree值）和从剩余节点生成的子节点列表中获取结果。从空树产生的初始值是一个空列表：

let MTree6to0 = 
  MFoldTree (fun x children -> MNode((if x=6 then 0 else x), children)) 
            (fun head tail -> head::tail) [] Mtree7
于 2013-06-01T18:45:43.700 回答
5

另一种解决方案可能是

let rec mfold f a (MNode(x,s)) = f (List.fold (fun a t -> mfold f a t) a s) x

实际上，我们可以将树视为线性结构（折叠它）。

用例

> mfold (+) 0 Mtree7;;
val it : int = 28

过滤器与普通折叠相同（因为mfold是普通折叠）：

> mfold (fun a x -> if x = 6 then a else x + a) 0 Mtree7;;
val it : int = 22

该函数可以是泛型的（因为List.fold, Array.fold, ... 可以是泛型的）。

“但第二个的目的是返回修改过的整个树，以便任何具有值 6 的节点现在都具有值 0”

但这不是fold计算，是map！

您可以轻松完成（再次将其视为线性结构）

let rec mmap f (MNode(x,s)) = MNode(f x, List.map (mmap f) s)

用例

> mmap (fun x -> if x=6 then 0 else x) Mtree7;;
val it : MultiTree =
  MNode
    (4,
     [MNode (2,[MNode (1,[]); MNode (3,[])]);
      MNode (0,[MNode (5,[]); MNode (7,[])])])

同样，我建议对每个可能的列表容器（Seq, List, Array, ...）执行此操作，它使用户能够在上下文中选择最佳策略。

笔记：

  • 我是 F# 的新手，如有错误请见谅。
  • 堆栈大小应该不是问题，堆栈级别等于树的深度。
于 2013-06-01T22:18:53.633 回答