在 haskell 中使用自定义递归数据类型 -> TRIE

Question

我正在学习Haskell，我刚刚遇到了一个似乎很难的问题。

我有一个用于 Trie 的自定义递归数据类型。

data Trie keytype valuetype = TNode (Maybe valuetype) [Edge keytype valuetype]
deriving (Show, Eq)
type Edge e a = (e, Trie e a)

我正在尝试实现与之配合使用的功能。我发现如何遍历它的顺序不正确。

isTrieValid :: Ord e => Trie e a -> [e]
isTrieValid (TNode _ []) = []
isTrieValid (TNode _ ((edge, TNode maybe innerlist):children)) =  edge : printChildren innerlist  ++ printChildren children
where  
printChildren :: Ord e => [Edge e valuetype] -> [e]
printChildren [] = []
printChildren ((edge_name, TNode _ innerlist):xs) =edge_name : printChildren innerlist ++ printChildren xs

例如，对于以下trie返回所有"键"(边缘名称)->"abbce">

trie1 = TNode (Just 42) [('a', TNode (Just 16) []),
('b', TNode Nothing
[('b', TNode (Just 1) []),
('c', TNode (Just 5) []),
('e', TNode (Just 2) [])
])
]

现在我正在尝试制作能够基于"键"查找元素的函数，如下所示：

trieLookup :: Ord e => [e] -> Trie e a -> Maybe a

但我目睹了两个问题。首先，如果我使用递归遍历 Trie，我不确定如何处理第一个元素。因为第一个元素没有"钥匙"，我应该返回什么？我认为空字符串可以工作，但我希望整个"Ord"类型类用于键，因此会引发类型错误。

我尝试制作的下一个函数将检查 Trie 有效性。

isTrieValid :: Ord e => Trie e a -> Bool

我的理解是，Trie必须具有这种品质才能被认为是有效的。

• 当前元素后面的所有元素都按第一个元素排序(按Ord e排序)
• 没有两个后继者具有相同的密钥

因此，如果根节点有效并且所有子树/子树(不确定如何编写)也有效，则整个 TRIE 都是有效的。

我想创建一个函数来检查一个节点的有效性，然后使用上面的函数在所有节点上复制它，但我失败了。

感谢您的任何帮助。

Answer 1

我建议更改您的Trie类型。isTreeValid的所有属性都可以通过使用Data.Map k v而不是[Edge k v]轻松维护。

而且我真的不明白你在说什么问题trieLookup.如果输入键([e])为空，则返回根部的值，否则进一步下降到树中，这似乎很简单。在什么时候会出现如何处理根的问题？如果您需要有关该功能的帮助，请包括您解决它的尝试，并描述出了什么问题或需要在哪里工作。