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. 如何让函数 insert word 返回一个 TrieNode 对象列表，这样我就不必将调用括在方括号（“[”，“]”）中。我认为这是一个错误。
3. 欢迎您就在 F# 中实现此数据结构提供任何其他建议。我知道我一定做错了很多事情，因为我对这种语言非常陌生。例如，我知道单词插入函数有缺陷，因为它不检查列表是否为空，因此它过早结束。当我到达它时，我想穿过那座桥。

先感谢您

先感谢您

4

2 回答 2

4

  1. 您可能无法触发断点，因为您没有完全应用insertWords：它需要两个咖喱参数，但您只传入单个参数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"and"to"吗？
于 2011-02-15T21:01:02.323 回答
1

关于您的第一个问题，正如@kvb 所说，您正在部分申请insertWord. 在定义它时，您指定了一个显式参数wordChars，并且通过使用function模式匹配的构造，您基本上添加了第二个类型参数，TrieNode因此您的函数最终具有以下签名：

insertWord : char list -> TrieNode -> TrieNode

因为在您调用InsertWord（这只是一个包装器insertWord）时，您只提供一个参数（一个字符列表），该函数不会被调用，但您会得到一个期待TrieNode返回的函数。InsertWord的签名清楚地表明了这一点：

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

注意括号。

您可能希望Nil在您的情况下提供 a ，因为从概念上讲您正在扩展一个空的 trie：

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

您将在此处找到 trie 结构的示例实现：http: //lepensemoi.free.fr/index.php/2009/10/15/trie-and-anagrams-with-f

于 2011-02-16T06:53:52.033 回答