发现孩子在一棵树上使用F＃

Question

我试图使用F＃一个简单的树形结构模型，也忍不住想，我很厉害这样做：

我的树基本上是树叶的列表（这最终将是坚持到数据库表）。我有一个函数getChildren，它接收一个叶节点ID并递归地返回该叶的所有子节点。

open System.Collections.Generic 

type leaf = { nodeID : int; nodeDescr : string; parentID : int option} 

let myTree = [ { nodeID = 0; nodeDescr = "Root"; parentID = None }; 
       { nodeID = 1; nodeDescr = "Mechanical"; parentID = Some(0) } ; 
       { nodeID = 2; nodeDescr = "Electrical"; parentID = Some(0) } ; 
       { nodeID = 3; nodeDescr = "High Voltage"; parentID = Some(2) } ; 
       { nodeID = 4; nodeDescr = "Low Voltage"; parentID = Some(2) } ; 
       { nodeID = 5; nodeDescr = "HV Maintanence"; parentID = Some(3) } ; 
       { nodeID = 6; nodeDescr = "City Power"; parentID = Some(3) } ; 
       { nodeID = 7; nodeDescr = "LV Wiring"; parentID = Some(4) } ; 
       { nodeID = 8; nodeDescr = "LV Maintanence"; parentID = Some(4) } ] 


let getChildren (id : int) (tree : list<leaf>) = 
    let allChildren = new List<leaf>() // Mutable list 

    let rec getAllChildren (id : int) (t : list<leaf>) = 
     let cl = List.filter (fun x -> x.parentID = Some id) t // Get the immediate children 
     for c in cl do // Loop through the immediate children and recursively get their children 
      allChildren.Add(c) 
      getAllChildren c.nodeID t 
    getAllChildren id tree 
    allChildren 

我这里所关注的问题是：

1. 我使用的是可变列表
2. 我使用循环

我怀疑有一个更优雅的态度对待所有的这在F＃中使用函数式编程时可避免突变和循环，而且我的命令式编程习惯也在偷偷摸摸。

此外，这是一个很好的方式来建模树结构，铭记它将需要存储并从数据库表中检索？

Answer 1

如果你想保持树形结构中，已经有了，这个功能会找到适合你的孩子，没有循环或可变值：

let getChildren (id : int) (tree : list<leaf>) = 
    let parent node = tree |> Seq.filter (fun x -> Some x.nodeID = node.parentID) |> Seq.exactlyOne 

    let rec hasAncestor (node : leaf) = 
     node.parentID = Some id || (node.parentID.IsSome && hasAncestor (parent node)) 

    tree |> Seq.filter hasAncestor 

可能是你真正想要的是一个结构，其中每个节点存储一提到它的孩子，你当你去序列化数据，你可以找到参考

事情是这样的ID应该有希望足以为你指明正确的方向：

type Node = { 
    Id : int; 
    Description: string; 
    Children: seq<Node> 
} 

let myTree = 
    { Id = 0; Description = "Root"; Children = 
    [ 
     { Id = 1; Description = "Mechanical"; Children = [] }; 
     { Id = 2; Description = "Electrical"; Children =   
     [ 
      { Id = 3; Description = "High Voltage"; Children = 
      [ 
       { Id = 5; Description = "HV Maintanence"; Children = [] }; 
       { Id = 6; Description = "City Power"; Children = [] } 
      ] }; 
      { Id = 4; Description = "Low Voltage"; Children = 
      [ 
       { Id = 7; Description = "LV Wiring"; Children = [] } ; 
       { Id = 8; Description = "LV Maintanence"; Children = [] } 
      ] } 
     ]}; 
    ]} 

let rec getChildren (node : Node) = 
    Seq.concat [node.Children; (Seq.collect getChildren node.Children)]