haskell - Haskell中树数据结构的邻接表

Question

我在 Haskell 中定义了以下抽象数据类型:

data Trie = Leaf
          | Node [(Char, Trie)]
          deriving (Eq)

Node type 是元素列表 (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

但现在我被困在如何递归打印 children 。特别是，我如何给子节点编号？

Answer 1

标记节点非常简单，因为 GHC 将为您完成所有繁重的工作:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import qualified Data.Traversable as T
import qualified Data.Foldable as F 
import Control.Monad.State 

data Trie a = Leaf a | Node a [(Char, Trie a)] 
  deriving (Eq, Functor, F.Foldable, T.Traversable)

number :: Trie a -> Trie (a, Int)
number = flip evalState 1 . T.mapM (\x -> state $ \n -> ((x,n),n+1))

至于打印trie，恐怕我不太了解所需的输出。