F#将列表转换为树 [英] F# transform list to a tree
问题描述
我有一个元组int * string列表,其中int是级别,字符串是名称
I have a list of tuples int*string where int is level and string is name
let src = [
(0, "root");
(1, "a");
(2, "a1");
(2, "a2");
(1, "b");
(2, "b1");
(3, "b11");
(2, "b2");
]
我需要将其转换为以下内容
and i need to transform it to following
let expectingTree =
Branch("root",
[
Branch("a",
[
Leaf("a1");
Leaf("a2")
]);
Branch("b",
[
Branch("b1", [Leaf("b11")]);
Leaf("b2")
]);
]);
下面是我的操作方式,但是任何人都可以提出更好的建议。
我是F#的新手,执行相同操作的C#代码会更短一些,所以我想我做错了。
Below is the way how i did it, but could anybody advice with a better way to achieve that. I'm new to F#, and C# code to do the same thing would be some shorter, so i guess i'm going it wrong.
type Node =
| Branch of (string * Node list)
| Leaf of string
let src = [
(0, "root");
(1, "a");
(2, "a1");
(2, "a2");
(1, "b");
(2, "b1");
(3, "b11");
(2, "b2");
]
let rec setParents (level:int) (parents:list<int>) (lst:list<int*int*string>) : list<int*int*string> =
//skip n items and return the rest
let rec skip n xs =
match (n, xs) with
| n, _ when n <= 0 -> xs
| _, [] -> []
| n, _::xs -> skip (n-1) xs
//get parent id for given level
let parentId (level) =
let n = List.length parents - (level + 1)
skip n parents |> List.head
//create new parent list and append new id to begin
let newParents level id =
let n = List.length parents - (level + 1)
id :: skip n parents
match lst with
| (id, l, n) :: tail ->
if l = level then (id, parentId(l), n) :: setParents l (newParents l id) tail
elif l <= level + 1 then setParents l parents lst
else [] //items should be in order, e.g. there shouldnt be item with level 5 after item with level 3
| _ -> []
let rec getTree (root:int) (lst: list<int*int*string>) =
let getChildren parent =
List.filter (fun (_, p, _) -> p = parent) lst
let rec getTreeNode (id:int) (name:string) =
let children = getChildren id
match List.length children with
| 0 -> Leaf(name)
| _ -> Branch(name,
children
|> List.map (fun (_id, _, _name) -> getTreeNode _id _name))
match getChildren root with
| (id, _, n) :: _ -> getTreeNode id n
| _ -> Leaf("")
let rec printTree (ident:string) (tree:Node) =
match tree with
| Leaf(name) ->
printfn "%s%s" ident name
| Branch(name, children) ->
printfn "%s%s" ident name
List.iter (fun (node) -> printTree (" " + ident) node) children
let tree =
src
|> List.mapi (fun i (l, n) -> (i+1, l, n)) //set unique id to each item
|> setParents 0 [0] //set parentId to each item
|> getTree 0
printTree "" tree
Console.ReadKey() |> ignore
推荐答案
首先,您并不需要如果您的分支包含子树列表,则 Leaf
有一个特殊的情况,因为leaf只是一个没有子树的分支。因此,我将使用以下树类型:
First of all, you do not really need to have a distinguished case for Leaf
if your branch is containing a list of sub-trees, because leaf is just a branch with no sub-trees. So, I'm going to use the following tree type:
type Tree =
| Branch of string * list<Tree>
使用显式递归列表处理可能更容易实现将列表转为树的核心功能。您可以一次性完成-只要找到嵌套索引就可以遍历元素并开始一个新分支(或者当索引较小时从适当数量的递归调用返回)。这是我的尝试:
The core function for turning list to a tree is probably easier to implement using explicit recursive list processing. You can do it in one pass - just go over the elements and start a new branch whenever you find nested index (or return from an appropriate number of recursive calls when you get a smaller index). This is my attempt:
/// Build a tree from elements of 'list' that have larger index than 'offset'. As soon
/// as it finds element below or equal to 'offset', it returns trees found so far
/// together with unprocessed elements.
let rec buildTree offset trees list =
match list with
| [] -> trees, [] // No more elements, return trees collected so far
| (x, _)::xs when x <= offset ->
trees, list // The node is below the offset, so we return unprocessed elements
| (x, n)::xs ->
/// Collect all subtrees from 'xs' that have index larger than 'x'
/// (repeatedly call 'buildTree' to find all of them)
let rec collectSubTrees xs trees =
match buildTree x [] xs with
| [], rest -> trees, rest
| newtrees, rest -> collectSubTrees rest (trees @ newtrees)
let sub, rest = collectSubTrees xs []
[Branch(n, sub)], rest
该函数获取初始偏移量,并收集到目前为止的树。 trees
参数始终将为 []
,并且您需要一些初始偏移值
。结果是低于给定级别的树木列表和其余元素的列表:
The function takes initial offset and trees collected so far. The trees
parameter is always going to be []
and you need some value for initial offset
. The result is a list of trees below the given level and a list of remaining elements:
let res = buildTrees -1 [] src
假设根在-1以上,您可以忽略元组的第二部分(应该为空列表)并获得第一棵树(应该只有一棵树):
Assuming root is above -1, you can just ignore the second part of the tuple (it should be empty list) and get the first tree (there should be only one):
/// A helper that nicely prints a tree
let rec print depth (Branch(n, sub)) =
printfn "%s%s" depth n
for s in sub do print (depth + " ") s
res |> fst |> Seq.head |> print ""
这篇关于F#将列表转换为树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!