当我的大脑因为卡在树上而受伤时,我会尽量简单明了地说出我想说的话:
- 给定一棵信息树,列出与谓词匹配的所有子树(在本例中,info = 3)。
一种直接的方法是列出树的所有节点,然后过滤谓词。
type 'info tree = Node of 'info * 'info tree list
let rec visit = function
| Node( info, [] ) as node -> [ node ]
| Node( info, children ) as node -> node :: List.collect visit children
let filter predicate tree =
visit tree
|> List.filter (fun (Node(info,_)) -> predicate info)
这是针对 OP 的示例数据运行的树过滤器:
let result = filter (fun info -> info = 3) test
令我吃惊的一件事是,代码对于任何带有适当谓词的“信息类型”来说是多么容易:
let test2 =
Node(("One",
[Node("Two",
[Node("Three",[Node("Five",[]);Node("Three",[])]);
Node("Three",[])]);
Node("Three",[])]))
let res2 = filter (fun info -> info = "Three") test2
或者,如果您想列出信息而不是子树,则代码非常简单:
let rec visit = function
| Node( info, [] ) -> [ info ]
| Node( info, children ) -> info :: List.collect visit children
let filter predicate tree =
visit tree
|> List.filter predicate
它支持相同的查询,但只返回'信息记录,而不是树结构:
let result = filter (fun info -> info = 3) test
> val result : int list = [3; 3; 3; 3]