在f#中对多路树进行折叠/递归 [英] Fold / Recursion over Multiway Tree in f#
问题描述
我正在尝试将Brian's Fold应用于二叉树( http: //lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/)来申请Multiway树.
I am trying to adapt Brian's Fold for Bianary 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
多路树版本 [无法(完全)正常运行:
数据结构
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!
欢呼
dusiod
推荐答案
另一个解决方案可能是
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屋!