P73 - 多路树的 S 表达式表示
Multiway tree representation with S-expressions
官方模块：
Problems.P73核心函数：treeToSexp、sexpToTree
编码规则
叶子直接写字符；有孩子的节点写成 (根 子树1 子树2 ...)。
方法一：递归下降
1treeToSexp :: MultiwayTree Char -> String
2treeToSexp (MultiwayTree x []) = [x]
3treeToSexp (MultiwayTree x children) =
4 "(" ++ [x] ++ " " ++ unwords (map treeToSexp children) ++ ")"
递归下降解析
1sexpToTree :: String -> Maybe (MultiwayTree Char)
2sexpToTree input = do
3 (tree, rest) <- parse (dropWhile (== ' ') input)
4 if null (dropWhile (== ' ') rest) then Just tree else Nothing
5
6parse :: String -> Maybe (MultiwayTree Char, String)
7parse [] = Nothing
8parse ('(':rest) = do
9 (root, afterRoot) <- nextChar rest
10 (children, remaining) <- parseList afterRoot
11 pure (MultiwayTree root children, remaining)
12parse (')':_) = Nothing
13parse (x:rest) = Just (MultiwayTree x [], rest)
14
15nextChar input = case dropWhile (== ' ') input of
16 x:rest | x /= '(' && x /= ')' -> Just (x, rest)
17 _ -> Nothing
18
19parseList input = case dropWhile (== ' ') input of
20 ')':rest -> Just ([], rest)
21 [] -> Nothing
22 xs -> do
23 (child, afterChild) <- parse xs
24 (siblings, rest) <- parseList afterChild
25 pure (child : siblings, rest)
方法二：ReadP 解析组合子
1import Text.ParserCombinators.ReadP
2
3sexpToTreeReadP :: String -> Maybe (MultiwayTree Char)
4sexpToTreeReadP input = case
5 [tree | (tree, "") <- readP_to_S (skipSpaces *> treeP <* skipSpaces <* eof) input] of
6 [] -> Nothing
7 trees -> Just (last trees)
8 where
9 treeP = branchP <++ leafP
10
11 leafP = MultiwayTree <$> nodeChar <*> pure []
12
13 branchP = do
14 char '('
15 skipSpaces
16 root <- nodeChar
17 children <- many (skipSpaces *> treeP)
18 skipSpaces
19 char ')'
20 pure (MultiwayTree root children)
21
22 nodeChar = satisfy (\c -> c /= '(' && c /= ')' && c /= ' ')
23
24treeToSexpDL :: MultiwayTree Char -> String
25treeToSexpDL tree = build tree ""
26 where
27 build (MultiwayTree value []) = (value :)
28 build (MultiwayTree value children) =
29 ('(' :) . (value :) . foldr addChild id children . (')' :)
30 addChild child rest = (' ' :) . build child . rest
ReadP 用组合子直接描述“叶子或括号分支”的文法；差异列表编码避免多层 ++。它与方法一显式管理剩余字符串的方式形成对照。
方法对比
| 方法 | 空白和分支处理 |
|---|---|
| 手写递归下降 | 显式 dropWhile 和剩余字符串 |
ReadP | skipSpaces、many 和选择组合子 |
测试
1>>> treeToSexp multitree5
2"(a (f g) c (b d e))"
3>>> sexpToTree (treeToSexp multitree5) == Just multitree5
4True
5>>> sexpToTree "(a b"
6Nothing
7>>> sexpToTreeReadP (treeToSexp multitree5) == Just multitree5
8True
9>>> treeToSexpDL multitree5 == treeToSexp multitree5
10True