4

F# で trie データ構造を実装しようとしています。私はいくつかの問題を抱えています。単語挿入機能をデバッグできません。この関数内のブレークポイントには到達せず、何かがクラッシュしますが、エラーは表示されません。また、私が正しいことを実装したかどうか、私は深刻な疑問を抱いています。とにかくここにコードがあります：

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) ->[ (List.filter(fun (this:TrieNode) -> this.Char = c) subnodes).Head ]

    member this.AWordEndsHere = match this with | Nil -> false
                                                | SubNodes(c,weh,subnodes) -> weh
module TrieFunctions = 
    let rec insertWord (wordChars:char list) = function
        | Nil -> SubNodes(wordChars.Head, false, [])
        | SubNodes(c, weh, subnodes) as node ->
            let child = node.GetChild(wordChars.Head)
            if child = [] then 
                SubNodes(wordChars.Head,false,[insertWord wordChars.Tail node])
            else
                SubNodes(wordChars.Head,false,[insertWord wordChars.Tail child.Head])


type Trie(inner : TrieNode) =

    member this.InsertWord(wordChars:char list) = TrieFunctions.insertWord(wordChars)


  let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i'])

私の質問は次のとおり
です。1. insertWord 関数へのデバッグ アクセスを取得するにはどうすればよいですか? なぜ私は今それを取得していないのですか? エラーが表示されないのはなぜですか?
2. 呼び出しを角かっこ ("[","]") で囲む必要がないように、関数挿入単語が TrieNode オブジェクトのリストを返すようにするにはどうすればよいですか。これはエラーだと思います。
3. このデータ構造を F# に実装する際に、他にアドバイスがあれば歓迎します。私はこの言語に非常に慣れていないので、多くのことを間違っているに違いないことはわかっています。たとえば、リストが空であるかどうかをチェックしないため、単語挿入機能に欠陥があり、途中で終了することを知っています。その橋に着いたら、私はその橋を渡りたかった。

前もって感謝します

前もって感謝します

4

2 に答える 2

4

  1. を完全に適用していないため、ブレークポイントのトリガーに失敗している可能性がありinsertWordsます。2 つのカリー化されたパラメーターが必要ですが、1 つの引数しか渡していませんwordChars。おそらくTrie、代わりにこのように型を定義するつもりでしたか?

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

  2. すべての戻り値を でラップ[]してシングルトン リストにし、 への再帰呼び出しをラップしないようにすることもできますinsertWords。ただし、シングルトンリストしか取得できないため、アルゴリズムに(いずれにせよ)何か問題がある可能性があります...

    現時点では、既存のリストを完全に破棄していることに注意してください。subnodesその前に追加したい場合は、(insertWord wordChards.Tail node)::subnodes代わりに使用してください。ただし、新しいエントリを追加するのではなく、既存のエントリを置き換えたい場合があり、これにはより多くの労力が必要です。

  3. いくつかの問題があります。開始するためのいくつかを次に示します。

    • Head特に、呼び出し時にリストが空でないことを常に知っているとは限らないため、 の使用を避けるようにしてください。
    • 空の に単語を挿入するとTrie、最初の文字以外はすべて削除されます! 同様に、再帰呼び出しも再考する必要があります。
    • さらに重要なことに、あなたのTrieNodeタイプには少し問題があります。"in"との 2 つの単語だけを含む結果のトライを書き出すことができます"to"か?
于 2011-02-15T21:01:02.323 に答える
1

最初の質問に関しては、@kvb が言ったように、部分的に適用していますinsertWord。定義中に明示的な引数を指定し、パターン マッチングwordCharsの構造を使用して、基本的に型の 2 番目のパラメーターを追加しているため、関数は次のシグネチャで終了します。functionTrieNode

insertWord : char list -> TrieNode -> TrieNode

への呼び出しInsertWord(これは への単なるラッパーinsertWordです) では、1 つの引数 (char リスト) のみを提供するため、関数は呼び出されませんが、TrieNodeバックを期待する関数を取得します。InsertWordの署名はそれを明確にします：

InsertWord : wordChars:char list -> (TrieNode -> TrieNode)

括弧に注意してください。

Nil概念的には空のトライを拡張しているので、おそらくあなたの場合にa を提供したいと思うでしょう:

let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i']) Nil

トライ構造の実装例は、http: //lepensemoi.free.fr/index.php/2009/10/15/trie-and-anagrams-with-fにあります。

于 2011-02-16T06:53:52.033 に答える