在 f# 中折叠/递归多路树 [英] Fold / Recursion over Multiway Tree in f#

问题描述

我正在尝试为二叉树调整布赖恩折叠 (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/) 申请多路树.

I am trying to adapt Brian's Fold for Binary Trees (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/) to apply for Multiway trees.

来自 Brian 博客的总结:

Summarizing from Brian's Blog:

数据结构:

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

Multiway Tree 版本 [不(完全)工作]:

数据结构

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 - 似乎有效

Example 1 Returns 28 - seems to work

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 但我让它与 @ 操作符一起工作.

Initially I thought the MFoldTree needed a map.something somewhere but I got it to work with the @ operator instead.

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

Any help on the second example and or correcting what I've done in the MFoldTree function would be great!

干杯

日常

推荐答案

另一个解决方案可能是

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

真的，我们可以将树视为线性结构(折叠它).

really, we can treat tree as a lineal struct (to fold it).

用例

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

过滤器和普通折叠一样(因为mfold是普通折叠):

Filter is the same with normal fold (because mfold is a normal fold):

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

那个函数可以是泛型的(如List.fold、Array.fold、...可以是泛型).

That function could be generic (as List.fold, Array.fold, ... could be generics).

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

但这不是fold计算，是map！

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

You can do easilly (treating, again, as a lineal struct)

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、...)做这件事，它启用让用户根据上下文选择最佳策略.

Again, I suggest to do it for each possible list container (Seq, List, Array, ...), it enable to user select best strategy in context.

注意事项:

• 我是 F# 新手，如有错误请见谅.
• 堆栈大小应该不是问题，堆栈级别等于树的深度.

这篇关于在 f# 中折叠/递归多路树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！