我在Haskell中定义了以下抽象数据类型:
data Trie = Leaf
| Node [(Char, Trie)]
deriving (Eq)
的Node
类型是元素的列表(c, t)
,其中c
,是从当前节点到边缘的标签t
。
现在,我要打印出树的邻接列表。具体来说,我需要每行打印一个边缘,其中边缘的格式为:
n1 n2 c
带有n1
源,n2
目标和c
边缘标签。
我可以使用以下命令从根节点打印边缘
instance Show Trie where
show = show' 2 1
where show' _ _ Leaf = ""
show' next n1 (Node ts) = unlines $ zipWith (\n2 (c, _) ->
show n1 ++ " " ++ show n2 ++ " " ++ show c)
[next..] ts
但是现在我陷入了如何递归打印孩子的问题。特别是如何给子节点编号?
我想出了以下解决方案:
import Data.List (foldl')
enum :: Int -> Trie -> ([(Int,Int,Char)],Int)
enum x Leaf = ([],x+1)
enum x (Node pairs)
= let go (acc,y) (c,t) = (acc',y')
where acc' = [(x,y,c)] ++ edges ++ acc
(edges,y') = enum y t
in foldl' go ([],x+1) pairs
enum
接受起始ID和a,Trie
并返回边列表和下一个可用ID。
-- some examples:
leafs xs = [ (c,Leaf) | c <- xs ]
t1 = Node $ leafs "XYZ"
t2 = Node [('W', t1)]
t3 = Node $ [('A',t2)] ++ leafs "BC"
enum 1 t1 -- ([(1,4,'Z'),(1,3,'Y'),(1,2,'X')],5)
enum 1 t2 -- ([(1,2,'W'),(2,5,'Z'),(2,4,'Y'),(2,3,'X')],6)
enum 1 t3 -- ([(1,8,'C'),(1,7,'B'),(1,2,'A'),(2,3,'W'),(3,6,'Z'),(3,5,'Y'),(3,4,'X')],9)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句