Haskell自定义递归Trie类型实现lookup与合法性校验问题

你遇到的根节点无对应键的问题，本质是对查找终止条件的理解偏差：当输入的键列表为空时，说明已经走到目标节点，直接返回当前节点存储的Maybe valuetype即可。空列表本身是任意[e]类型的合法值，不需要额外构造空值匹配，不会触发类型错误。
实现代码如下：

trieLookup :: Ord e => [e] -> Trie e a -> Maybe a
-- 空键列表，直接返回当前节点存储的值
trieLookup [] (TNode val _) = val
-- 非空键列表，匹配首元素对应的子边后递归查找剩余键
trieLookup (k:ks) (TNode _ edges) = case lookup k edges of
  Nothing -> Nothing
  Just subTrie -> trieLookup ks subTrie

合法性的两个校验要求可以合并为「当前节点所有子边的键严格升序」：严格升序天然满足「按Ord规则排序」和「无重复键」两个条件，再递归校验所有子树合法即可。
实现代码如下：

isTrieValid :: Ord e => Trie e a -> Bool
isTrieValid (TNode _ edges) = 
  -- 校验当前节点子边键严格升序
  strictlyIncreasing (map fst edges)
  -- 递归校验所有子树合法性
  && all (isTrieValid . snd) edges
  where
    strictlyIncreasing :: Ord a => [a] -> Bool
    strictlyIncreasing [] = True
    strictlyIncreasing [_] = True
    strictlyIncreasing (x:y:xs) = x < y && strictlyIncreasing (y:xs)

注意：你之前实现的边遍历函数与本次合法性校验函数同名，如果需要同时保留两个功能，可以将遍历函数重命名为trieFlattenEdges等名称避免冲突。

内容的提问来源于stack exchange，提问作者Abdul Hajabi