在Haskell中为左关联树实现`read`

Question

我很难为树结构实现Read.我想要一个左关联字符串(与parens)喜欢ABC(DE)F并将其转换为树.该特定示例对应于树

.

这是我正在使用的数据类型(虽然我愿意接受建议):

data Tree = Branch Tree Tree | Leaf Char deriving (Eq)

那个特定的树将在Haskell中:

example = Branch (Branch (Branch (Branch (Leaf 'A')
                                         (Leaf 'B'))
                                 (Leaf 'C'))
                         (Branch (Leaf 'D')
                                 (Leaf 'E')))
                 (Leaf 'F')

我的show功能如下:

instance Show Tree where
    show (Branch l r@(Branch _ _)) = show l ++ "(" ++ show r ++ ")"
    show (Branch l r) = show l ++ show r
    show (Leaf x) = [x]

我想做一个read功能

read "ABC(DE)F" == example

Answer 1

在这种情况下,使用解析库会使代码非常短且极具表现力.(我很惊讶,这是如此整洁,当我尝试回答这个!)

我将使用Parsec(该文章提供一些链接以获取更多信息),并在"应用模式"(而不是monadic)中使用它,因为我们不需要monad的额外功率/足部射击能力.

码

首先是各种进口和定义:

import Text.Parsec

import Control.Applicative ((<*), (<$>))

data Tree = Branch Tree Tree | Leaf Char deriving (Eq, Show)

paren, tree, unit :: Parsec String st Tree

现在,树的基本单元是单个字符(不是括号)或带括号的树.带括号的树只是(和之间的普通树).而正常的树只是左边相关的分支单元(它非常自我递归).在Haskell与Parsec:

-- parenthesised tree or `Leaf <character>`
unit = paren <|> (Leaf <$> noneOf "()") <?> "group or literal"

-- normal tree between ( and )
paren = between (char '(') (char ')') tree  

-- all the units connected up left-associatedly
tree = foldl1 Branch <$> many1 unit

-- attempt to parse the whole input (don't short-circuit on the first error)
onlyTree = tree <* eof

(是的,那就是整个解析器!)

如果我们想要,我们可以不用paren,unit但上面的代码非常具有表现力,所以我们可以保持原样.

作为简要说明(我提供了文档的链接):

• (<|>) 基本上是指"左解析器或右解析器";
• (<?>) 允许您制作更好的错误消息;
• noneOf 将解析不在给定字符列表中的任何内容;
• between 需要三个解析器,并返回第三个解析器的值,只要它由第一个和第二个解析器分隔;
• char 从字面上解析其论点.
• many1将一个或多个参数解析为一个列表(看起来空字符串无效many1,而不是many分析零或更多);
• eof 匹配输入的结尾.

我们可以使用该parse函数来运行解析器(它返回Either ParseError Tree,Left是一个错误,Right是一个正确的解析).

如 read

使用它作为read类似函数可能是这样的:

read' str = case parse onlyTree "" str of
   Right tr -> tr
   Left er -> error (show er)

(我过去常常read'避免与之冲突Prelude.read;如果你想要一个Read实例,你将需要做更多的工作来实现readPrec(或者不需要的任何东西)但是实际的解析已经完成它不应该太难.)

例子

一些基本的例子:

*Tree> read' "A"
Leaf 'A'

*Tree> read' "AB"
Branch (Leaf 'A') (Leaf 'B')

*Tree> read' "ABC"
Branch (Branch (Leaf 'A') (Leaf 'B')) (Leaf 'C')

*Tree> read' "A(BC)"
Branch (Leaf 'A') (Branch (Leaf 'B') (Leaf 'C'))

*Tree> read' "ABC(DE)F" == example
True

*Tree> read' "ABC(DEF)" == example
False

*Tree> read' "ABCDEF" == example
False

证明错误:

*Tree> read' ""
***Exception: (line 1, column 1):
unexpected end of input
expecting group or literal

*Tree> read' "A(B"
***Exception: (line 1, column 4):
unexpected end of input
expecting group or literal or ")"

最后,之间的区别tree和onlyTree:

*Tree> parse tree "" "AB)CD"     -- success: ignores ")CD"
Right (Branch (Leaf 'A') (Leaf 'B'))

*Tree> parse onlyTree "" "AB)CD" -- fail: can't parse the ")"
Left (line 1, column 3):
unexpected ')'
expecting group or literal or end of input

结论

Parsec太神​​奇了!这个答案可能很长,但它的核心只有5或6行代码完成所有工作.

Answer 2

这非常像堆栈结构.当您遇到输入字符串时"ABC(DE)F",您Leaf找到任何原子(非括号)并将其放入累加器列表中.如果列表中有2个项目,则将Branch它们放在一起.这可以用类似的东西来完成(注意,未经测试,仅包括给出一个想法):

read' [r,l] str  = read' [Branch l r] str
read' acc (c:cs) 
   -- read the inner parenthesis
   | c == '('  = let (result, rest) = read' [] cs 
                 in read' (result : acc) rest
   -- close parenthesis, return result, should be singleton
   | c == ')'  = (acc, cs) 
   -- otherwise, add a leaf
   | otherwise = read' (Leaf c : acc) cs
read' [result] [] = (result, [])
read' _ _  = error "invalid input"

这可能需要一些修改,但我认为它足以让你走上正轨.