2

F# を使用して単純なツリー構造をモデル化しようとしていますが、これは非常に下手だと思わずにはいられません。

私のツリーは基本的に葉のリストです (最終的にはデータベース テーブルに永続化されます)。リーフ NodeID を受け取り、そのリーフのすべての子を再帰的に返す関数 getChildren があります。

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# で関数型プログラミングを使用する場合、ミューテーションとループを回避する、これらすべてに対するより洗練されたアプローチがあり、私の命令型プログラミングの習慣が忍び寄っているのではないかと思います。

また、これはツリー構造をモデル化するための良い方法ですか? データベース テーブルに格納して取得する必要があることを念頭に置いてください。

4

1 に答える 1

4

すでに持っているツリー構造を維持したい場合、この関数は、ループや変更可能な値なしで子を見つけます。

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)]
于 2013-09-01T15:54:43.763 に答える