在Haskell中为左关联树实现`read` [英] Implementing `read` for a left-associative tree in Haskell

问题描述

我很难实现（该文章提供了一些链接以获取更多信息），并以应用模式（而不是一次性） ，因为我们不需要monad的额外的力量/足球射击能力。

代码

首先是各种导入和定义：

  import Text.Parsec 
 
 import Control.Applicative（（< ; *），（< $>））
 
数据树=分支树树|树叶派生（Eq，Show）
 
 paren，tree，unit :: Parsec String st树
  

现在，树的基本单位是单个字符（不是括号）或括号括起来的树。括号中的树只是（和）之间的普通树。而一棵普通的树只是单位放在左边相关的分支（这是非常自我递归的）。在带Parsec的Haskell中：

   - 带括号的树或`Leaf< character>`
 unit = paren< |> （Leaf< $> noneOf（））<> 组或字面
 
  - （和）
之间的正常树paren =之间（char'（'）（char'）'）树
 
  -  - 所有相连的单元相关联
 tree = foldl1 Branch< $>许多单元
 
  - 尝试解析整个输入（不要在第一个错误上进行短路）
 onlyTree = tree <* eof 
  

（是的，这就是整个解析器！）

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

作为一个简短的解释（我提供了文档链接）：

（<？>） 可让您制作更好的错误讯息;

noneOf 将解析不在给定字符列表中的任何内容;

之间 需要三个解析器，并且只要第一个和第二个分隔符分隔，就返回第三个解析器的值;

char 直接解析其参数。 //hackage.haskell.org/packages/archive/parsec/3.1.2/doc/html/Text-Parsec-Combinator.html#v:many1rel =noreferrer> many1 将其一个或多个参数解析为一个列表（看起来空字符串是无效的，因此 many1 ，而不是许多分析零个或多个）;

eof 匹配结束。

我们可以使用 parse 函数运行解析器（它返回或者ParseError树， Left 是一个错误， Right $ b

作为读取

使用它作为 read 类似函数可能类似于：

 读取str = case parse onlyTreestr 
 Right tr  - > tr 
左呃 - >错误（显示）
  

（我已使用读取避免与 Prelude.read 冲突;如果你想要一个 Read 实例，你必须做需要更多的工作来实现 readPrec （或者其他任何需要的），但是实际的解析已经完成了，应该不会太难。）

示例

一些基本示例：

  *树>阅读'A
叶'A'
 
 *树>阅读''AB'
分支（叶'A'）（叶'B'）
 
 *树> （'叶''）（叶'C'）
 
 *树>阅读'A（BC）
分支（叶'A'）（分支（叶'B'）（叶'C'））
 
 *树>阅读'ABC（DE）F==示例
真正
 
 *树>阅读'ABC（DEF）==示例
 False 
 
 * Tree>阅读'ABCDEF==示例
 False 
  

演示错误：

  *树>阅读'
 ***例外：（第1行，第1列）：
意外结束输入
期待组或字面值
 
 *树> （B
 ***例外：（第1行，第4列）：
意外结束输入
期待组或字面或）
  

最后， tree 和 onlyTree ：

  * Tree> （分支（叶'A'）（叶'B'））
 
 *树>解析树AB）CD - 成功：忽略解析onlyTreeAB）CD - 失败：无法解析）
左边（第1行，第3列）：
意外'）'
期待组或字面值或输入结束
  





结论

Parsec是惊人的！这个答案可能很长，但它的核心只有5或6行代码，可以完成所有工作。

I'm having a hard time implementing Read for a tree structure. I want to take a left-associative string (with parens) like ABC(DE)F and convert it into a tree. That particular example corresponds to the tree

.

Here's the data type I'm using (though I'm open to suggestions):

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

That particular tree would be, in Haskell:

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

My show function looks like:

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]

I want to make a read function so that

read "ABC(DE)F" == example

解决方案

This is a situation where using a parsing library makes the code amazingly short and extremely expressive. (I was amazed that it was so neat when I was experimenting to answer this!)

I'm going to use Parsec (that article provides some links for more information), and using it in "applicative mode" (rather than monadic), since we don't need the extra power/foot-shooting-ability of monads.

Code

First the various imports and definitions:

import Text.Parsec

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

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

paren, tree, unit :: Parsec String st Tree

Now, the basic unit of the tree is either a single character (that's not a parenthesis) or a parenthesised tree. The parenthesised tree is just a normal tree between ( and ). And a normal tree is just units put into branches left-associatedly (it's extremely self-recursive). In Haskell with 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

(Yes, that's the entire parser!)

If we wanted to, we could do without paren and unit but the code above is very expressive, so we can leave it as is.

As a brief explanation (I've provided links to the documentation):

• (<|>) basically means "left parser or right parser";
• (<?>) allows you to make nicer error messages;
• noneOf will parse anything that's not in the given list of characters;
• between takes three parsers, and returns the value of the third parser as long as it is delimited by the first and second ones;
• char parses its argument literally.
• many1 parses one or more of its argument into a list (it appears that the empty string is invalid hence many1, rather than many which parses zero or more);
• eof matches the end of the input.

We can use the parse function to run the parser (it returns Either ParseError Tree, Left is an error and Right is a correct parse).

As read

Using it as a read like function could be something like:

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

(I've used read' to avoid conflicting with Prelude.read; if you want a Read instance you'll have to do a bit more work to implement readPrec (or whatever is required) but it shouldn't be too hard with the actual parsing already complete.)

Examples

Some basic examples:

*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

Demonstrating errors:

*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 ")"

And finally, the difference between tree and 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

Conclusion

Parsec is amazing! This answer might be long but the core of it is just 5 or 6 lines of code which do all the work.

这篇关于在Haskell中为左关联树实现`read`的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！