新手F# trie实现出了问题

Question

新手F# trie实现出了问题

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. 如何使insertWord函数返回TrieNode对象列表，这样我就不必将调用包装在方括号（“[”，“]”）中。我认为这是一个错误。
3. 如果您对在F＃中实现此数据结构有任何其他建议，欢迎提出。我知道我一定做错了很多事情，因为我对这种语言非常陌生。例如，我知道单词插入函数存在缺陷，因为它没有检查列表是否为空，所以它会过早地结束。我想在到达目的地时解决这个问题。

谢谢您的帮助

- Para

不想在确认之前进行编辑 - 你是指一棵树，对吗？一个列表和二叉树的扩展？ - Ramon Snir

最终的trie值类型为(Trie->Trie)，这表明它在部分评估insertWord函数。 - Jimmy

Trie，指的是前缀树，而不是普通树。 - Para

2个回答

1

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

insertWord : char list -> TrieNode -> TrieNode

由于在您对InsertWord的调用中（它只是insertWord的包装器），您只提供了一个参数（一个字符列表），因此该函数不会被调用，但您将得到一个期望返回TrieNode的函数。 InsertWord的签名表明了这一点：

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

注意括号。

在您的情况下，您可能希望提供一个 `Nil`，因为从概念上讲，您是在扩展一个空的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

- Alex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kvb · Accepted Answer

You are probably failing to trigger your breakpoint because you aren't fully applying insertWords: it takes two curried parameters, but you're only passing the single argument wordChars in. Perhaps you meant to define your Trie type like this instead?
```
type Trie(inner : TrieNode) =
  member this.InsertWord(wordChars:char list) = TrieFunctions.insertWord wordChars inner
```
Well, you could wrap all of your return values in [] to make them singleton lists and then not wrap the recursive calls to insertWords. However, it seems likely that there's something wrong with your algorithm (either way), since you only ever get singleton lists...

Note that at the moment you're completely discarding the existing subnodes list - if you want to append to the front of it, use (insertWord wordChards.Tail node)::subnodes instead. However, sometimes you'll want to replace an existing entry rather than append a new one, which will require more effort.
There are several issues. Here are a few to get you started:
- Try to avoid using Head, particularly since you don't always know that your lists are non-empty when you're calling it.
- When you're inserting a word into an empty Trie, you're dropping all but the first character! Similarly, you need to reconsider your recursive calls too.
- More importantly, your TrieNode type has a bit of a problem. Can you write out the resulting trie you would expect to see which just contains the two words "in" and "to"?