私はタイプの定義を持っています:
type FsTree = Node of (string * FsTree) list
空のノードを作成します。
let createEmptyFsTree () : FsTree = Node[]
文字列リストのパスからツリーを構築したいと思います。次に例を示します。
let fs1 = create ["MainNode";"nodeA";"nodeB"] (createEmptyFsTree())
let fs2 = create ["MainNode";"nodeC";"nodeD"] fs1
let fs3 = create ["MainNode";"nodeC";"nodeE"] fs2
結果は次のようになります。
Node [("MainNode", Node [
("nodeA", Node [("nodeB", Node [])]);
("nodeC", Node [
("nodeD", Node[]);
("nodeE", Node[])])])]
これはこれまでの私のコードです。私は2日間立ち往生しています。助けてください。
let create (p : string list) (fs : FsTree) =
let rec create (p : string list) (fs : FsTree) =
match fs with
| Node n -> match p, n with
| h :: t, (name, rsNode) :: rsTree when name = h -> Node([(h, (create t rsNode))] @ rsTree)
| _, lNode :: rsTree -> Node([lNode]@rsTree)
| h :: t, [] -> Node ([h, (create t (createEmptyFsTree()))])
| [],[] -> Node[]
create p fs
渡された最初のパスからのみツリーを作成できます。
Node [("MainNode", Node [("nodeA", Node [("nodeB", Node [])])])]
この問題の難しさは、それが機能するために同時に再帰的にトラバースする必要があるいくつかの構造(パスは、、list
各ノードは、list
およびサブツリー)があることです。1つの関数だけでそうすることは、理解するのが非常に難しくなります。
そのため、問題を小さな部分に分割して単純化するのが好きです。ここでは、2つの相互再帰関数を使用します(構文に注意してください)。まず、関数の名前を変更して、関数の機能をよりよく理解できるようにします。また、混乱を招くため、関数と変数に同じ名前を繰り返すことは避けています。私の最初の関数は、パスのトラバースのみを処理しますp
。
let rec addPath (p : string list) (Node ns) =
match p with
| [] -> Node ns
| hp :: tp -> Node (addHeadPath hp tp ns)
2番目のパラメーターでパターンマッチングを使用して(Node ns)
サブノードのリストを取得します。これは、次の関数がそのリストをトラバースするためです。
私のmatch
表現では、再帰の終わりである空のリストの場合を最初に処理するのが好きです。2番目のケースでは、頭と尾を分離し、それらを別の関数に送信して処理します。
and addHeadPath hp tp ns =
match ns with
| [] -> [hp, addPath tp (Node[]) ]
| (nn, st) :: tn when nn = hp -> (nn, addPath tp st ) :: tn
| hn :: tn -> hn :: addHeadPath hp tp tn
addHeadPathTo
は相互に再帰的であるaddPathTo
ためand
、別のの代わりにそれらを結び付けますlet rec
。
ここでも、空のケースが最初に処理され、1つのノードを含むリストが返さaddPathTo
れ、残りのパスを追加するように呼び出されます。2番目のケースは、ノードがすでに存在する場合です。この場合、残りのパスをサブツリーに追加しst
ます。3番目のケースは、それ自体を再帰的に呼び出すことにより、ノードのリストを調べ続けます。
次のように呼び出します。
createEmptyFsTree()
|> addPath ["MainNode";"nodeA";"nodeB"]
|> addPath ["MainNode";"nodeC";"nodeD"]
|> addPath ["MainNode";"nodeC";"nodeE"]
|> printfn "%A"
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加