Haskell的特里功能 - 將值和搜索

-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) [])])])]

我也希望能夠在特里搜索和查找與某一前綴開頭的鍵。例子：

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

來源

2011-11-03 Oakin

樹和Trie是不同的數據結構。你可以編輯帖子，以便不使用樹而不使用樹，反之亦然？這是功課嗎？如果是 - 添加作業標籤 – nponeccop

請注意，您的示例是錯誤的：「findTrie」的結果c「'必須包含'findTrie」ca「'的結果。所以第一行應該是'findTrie'c「oneTrie - > [」at「，」in「，」z「，」r「]' – nponeccop

除非你正在尋找家庭作業幫助，也有嘗試對hackage許多不同的實現：

http://hackage.haskell.org/packages/archive/pkg-list.html（搜索「線索」有）

嘗試次數走了很多的代碼來實現，所以不要指望這裏的人提供完整的實現 - 我們只能給出一些線索。所以我們需要知道你面臨的問題，所以我們可以幫助你前進。

一般尖端是自頂至底的發展使用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-04 00:10:26 nponeccop

Haskell的特里功能 - 將值和搜索

回答

相關問題