1

すべてのノードの高さを計算するメソッドを使用して、F＃でトライ構造を実装しようとしています。

これは私がこれまでに思いついたものです：

type TrieNode =
    | SubNodes of char * bool * TrieNode list
    | Nil
    member this.Char = match this with | Nil -> ' '
                                       | SubNodes(c,weh,subnodes) -> c
    member this.GetChild(c:char) = match this with  | Nil -> []
                                                    | SubNodes(c,weh,subnodes) -> if subnodes.Length > 0 then [ (List.filter(fun (this:TrieNode) -> this.Char = c) subnodes).Head ] else []

    member this.AWordEndsHere = match this with | Nil -> false
                                                | SubNodes(c,weh,subnodes) -> weh          

module TrieFunctions = 
    let rec insertWord (wordChars:char list) = function
        | Nil -> SubNodes(' ', false, (insertWord wordChars Nil)::[])
        //daca aici inca nu e cel putin un nod atunci fa nodul radacina standard adica nodul care nu e sfarsit de cuvant si
        //are caracterul ' ' si incepe sa ii construiesti lui subnodurile
        | SubNodes(c, weh, subnodes) as node ->

            if(wordChars.Length = 1) then
                SubNodes(wordChars.Head,true,[])
            else
                let child = node.GetChild(wordChars.Head)
                if child = [] then 
                    SubNodes(wordChars.Head,false,(insertWord wordChars.Tail node)::subnodes )
                else
                    SubNodes(wordChars.Head,false,(insertWord wordChars.Tail child.Head)::subnodes )
    let stringToCharList(s:string) = List.ofSeq s 


type Trie(inner : TrieNode) =
    member this.InsertWord(wordChars:char list) = Trie(TrieFunctions.insertWord wordChars inner)
    member this.InsertWord(str:string) = Trie(TrieFunctions.insertWord (TrieFunctions.stringToCharList str) inner)


  let trie = Trie(SubNodes(' ',false,List.empty))
                .InsertWord("abc")
                .InsertWord("abcd")
                .InsertWord("abcd")
                .InsertWord("abcde")
                .InsertWord("abcdef")
                .InsertWord("ab123cd")
                .InsertWord("abc123d")
                .InsertWord("abc132d")

今、私は自分の身長計算関数を書こうとしています。これがバイナリツリーの場合、これは非常に簡単に記述できますが、このツリーには各ノードにサブノードのリストがあるため、F＃で繰り返しトラバースする方法がわかりません。

これは私がこれまでリストフォールド操作を使用して思いついたものですが、コンパイルされません：

 module NodeFunctions = 
    let rec nextLevel(node:TrieNode,curlevel:int) = function
                        | Nil -> curlevel
                        | SubNodes(_,_,subnodes) -> 
                            List.fold (fun acc (node:TrieNode,_,_) -> let res = nextLevel(node,curlevel+1) and 
                                                                      if( acc > res) then acc else res) curlevel subnodes

この関数を機能させるためにどのように書き直すことができるかについてのアイデアはありますか？または、私の目標を達成するための他の方法についてのアイデアは、これが正しいアイデアではないはずですか？

前もって感謝します

4

4 に答える 4

2

あなたのコードはほぼ正しいようです。以下は私のためにコンパイルします（値を作成するときに例外が発生するため、実行しようとしませんでしたtrieが、再帰スキームは正しく聞こえます）：

let rec nextLevel(node:TrieNode,curlevel:int) = 
  match node with
  | Nil -> curlevel
  | SubNodes(_,_,subnodes) -> 
      List.fold (fun acc (node:TrieNode) -> 
        let res = nextLevel(node,curlevel+1) 
        if (acc > res) then acc else res) curlevel subnodes

私が行った変更：

  • あなたが書いnextLevel(...) = function ...た。functionコンストラクトは、値とパターンマッチングをとる関数を作成します（したがって、2つの引数をとる関数を作成しました）TrieNode。これをシンプルに置き換えましたmatch。

  • あなたのラムダにはあなたが持っていましたlet res = nextLevel(node,curlevel+1) and-andキーワードはそこに属していません（あなたは書くことができますlet res = .. inが、インデントのために必要ではありません）。

  • ラムダ関数はパターンマッチングを使用してタプルの要素を抽出しましたが、タプル(node:TrieNode,_,_)のsubnodesリストではなく、TrieNode値のリストにすぎません。

于 2011-02-18T00:48:01.653 に答える
2

これがより機能的なコードレイアウトです。コードと同じロジック。私は実用的なソリューションに取り組んでいます。

module Trie = 
    type Node = Node of (char * bool * Node list) Option

    let char = function
        | Node(None) -> ' '
        | Node(Some(c, _, _)) -> c

    let getChild (c:char) = function
        | Node(None) -> None
        | Node(Some(c, weh, subnodes)) -> 
            List.tryFind (fun (node:Node) -> (char node) = c) subnodes

    let rec insertWordChars (wordChars:char list) = function
        | Node(None) -> Node(Some(wordChars.Head, false, [insertWordChars wordChars.Tail (Node(None))]))
        | Node(Some(c, weh, subnodes)) as node ->
            if wordChars.Length = 1 then
                Node(Some(wordChars.Head, true, []))
            else
                match getChild (wordChars.Head) node with
                | None -> Node(Some(wordChars.Head, false, (insertWordChars wordChars.Tail node)::subnodes))
                | Some(child) -> Node(Some(wordChars.Head, false, (insertWordChars wordChars.Tail child)::subnodes))

    let insertWord (s:string) = insertWordChars (List.ofSeq s)

印刷の高さ。

let rec nextLevel (curlevel:int) = function
    | Trie.Node(None) -> curlevel
    | Trie.Node(Some(_, _, subnodes)) -> 
        List.fold (fun acc (node:Trie.Node) -> 
            let res = nextLevel (curlevel + 1) node
            if (acc > res) then acc else res) curlevel subnodes

let trie = 
    Trie.Node(Some(' ', false, []))
    |> Trie.insertWord("abc")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcde")
    |> Trie.insertWord("abcdef")
    |> Trie.insertWord("ab123cd")
    |> Trie.insertWord("abc123d")
    |> Trie.insertWord("abc132d")

printf "%A" (nextLevel 0 trie)
于 2011-02-18T03:34:33.850 に答える
1

私は別のアプローチを取ります：

let rec depth = function
| Nil -> 0
| SubNodes(_,_,l) ->
    let d = l |> List.map depth |> List.max
    d + 1

私にとって、これはfoldを使用するバージョンよりもはるかに読みやすくなっていますが、サブノードのリストを2回トラバースします。

于 2011-02-18T02:35:02.523 に答える
1

Trieについてもう少し考えてみると、最初のアプローチは近いものでしたが、すべてが同じ文字で始まる必要がありました。これは、文字列ではなく、元のアイデアのような文字を使用する実用的なトライです。文字列ノードとリーフを実装するための演習として、読者に任せます。

module Trie = 
    type Node = Node of (char * bool * Node) list

    let empty = Node([])

    let partition c = function
        | Node(nodes) -> List.partition (fun (ct, _, _) -> ct = c) nodes

    let rec insert wordChars node = 
        match wordChars, node with
        | c::cx, Node([]) -> Node([c, cx.IsEmpty, (insert cx empty)])
        | c::cx, _ -> 
            match partition c node with
            | (ct, weh, children)::_, others -> 
                Node((c, (weh || cx.IsEmpty), insert cx children)::others)
            | [] , others -> 
                Node((c, cx.IsEmpty, insert cx empty)::others)
        | [], _ -> node

    let insertWord (s:string) node = insert (List.ofSeq s) node

そしていくつかのテスト

let rec nextLevel (curlevel:int) = function
    | Trie.Node([]) -> curlevel
    | Trie.Node(nodes) -> 
        List.fold (fun acc (_, _, node) -> 
            let res = nextLevel (curlevel + 1) node
            if (acc > res) then acc else res) curlevel nodes

let rec print acc = function
    | Trie.Node(nodes) -> 
        List.iter (fun (c, w, node) ->
            let str = acc + c.ToString()
            if w then printfn "%s" str
            print str node) nodes

let trie = 
    Trie.empty
    |> Trie.insertWord("abc")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcde")
    |> Trie.insertWord("abcdef")
    |> Trie.insertWord("ab123cd")
    |> Trie.insertWord("abc123d")
    |> Trie.insertWord("abc132d")

printf "%d\n" (nextLevel 0 trie)

print "" trie

出力

7
abc
abc132d
abc123d
abcd
abcde
abcdef
ab123cd
于 2011-02-18T06:13:34.353 に答える