Haskell trie 函数 - 插入值和搜索

发布于 2024-12-13 20:39:02 字数 538 浏览 1 评论 0原文

trie 的类型是

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

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

示例：

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"]

原文

The type of the trie is

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

I want to write a function that takes in a key-value pair and a prefix trie.
I then want it to return the symbol table where the key-value pair is included. If the key already exists the new value should replace the old one.

Example:

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

I also want to be able to search in the trie and find keys that start with a certain prefix.
Example:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

鲸落 2024-12-20 20:39:02

除非您正在寻求家庭作业方面的帮助，否则 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 等等

Unless you are looking for help with homework, there are many different implementations of tries on hackage:

http://hackage.haskell.org/packages/archive/pkg-list.html (search for 'trie' there)

Tries take a lot of code to implement, so don't expect people here to provide full implementations - we can only give some clues. So we need to know which problems you face, so we can help you to move forward.

A general tip is to start top-to-bottom development using where, deconstruction of arguments and putting undefined instead of yet undeveloped parts:

Step 1:

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

Step 2:

Then think about some simplest 'base' cases:

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

In this example, the first line reads 'if we add an empty key, then the value must be replaced at the root, and child nodes must be left as they are'. The second line reads: 'if we add a non-empty key, then ...'

Step 3:

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

The second line now reads: 'if we add a non-empty key, then we leave oldValue as is and modify children somehow'.

Then in step 4 elaborate newChildren somehow et cetera

回复收藏 0 原文

~没有更多了~