-3

特里的类型是

data Trie a = TrieNode (Maybe a) [(Char, Trie a)]
deriving Show

我想编写一个接收键值对和前缀树的函数。然后我希望它返回包含键值对的符号表。如果键已经存在，则新值应替换旧值。

例子：

trieInsert ("abc",10) emptyTrie == 
    TrieNode Nothing [
        ('a', TrieNode Nothing [
            ('b', TrieNode Nothing [
                ('c', TrieNode (Just 10) [])])])]

我还希望能够在 trie 中搜索并找到以某个前缀开头的键。例子：

findTrie "c" oneTrie -> ["at","in"]
findTrie "ca" oneTrie -> ["z","r"]
4

1 回答 1

2

除非您正在寻求家庭作业的帮助，否则 hackage 的尝试有许多不同的实现：

http://hackage.haskell.org/packages/archive/pkg-list.html（在那里搜索“trie”）

尝试需要很多代码来实现，所以不要指望这里的人提供完整的实现——我们只能提供一些线索。所以我们需要知道您面临哪些问题，这样我们才能帮助您继续前进。

where一般提示是使用, 解构参数并放置undefined而不是尚未开发的部分来开始从上到下的开发：

步骤1：

trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = undefined

第2步：

然后考虑一些最简单的“基本”案例：

trieInsert [] value (TrieNode _ oldChildren) = TrieNode (Just value) oldChildren
trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = undefined

在此示例中，第一行显示“如果我们添加一个空键，则该值必须在根处替换，并且子节点必须保持原样”。第二行显示：'如果我们添加一个非空键，那么......'

第 3 步：

trieInsert [] value (TrieNode _ oldChildren) = TrieNode (Just value) oldChildren
trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = TrieNode oldValue newChildren where 
    newChildren = undefined

第二行现在显示：“如果我们添加一个非空键，那么我们将 oldValue 保持原样并以某种方式修改子项”。

然后在第 4 步详细说明 newChildren 等等

于 2011-11-04T00:10:26.083 回答