haskell - 如何从 Haskell 中的文件中读取二叉树

Question

我已经定义了树的类型。

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Read , Eq, Ord, Show)

现在，在一个文本文件中，我有二叉树，例如：

(7 (3 (1 () ()) (5 () ())) (11 (9 () ()) (13 () ())))

如何编写一个函数来读取树的这种表示并构造 Tree 类型的树？

Answer 1

Answer 2

你正在编写一个解析函数。基本类型类似于String -> Tree Int，但有一些强大的改进值得考虑。

首先，并不是所有String的 s 实际上都可以翻译成Trees （即")"绝对不是一棵树），所以最好将函数细化为类似 的类型String -> Maybe (Tree Int)，Maybemonad 表示可能的失败。

其次，您可能真的不想重新发明Int解析器。您可以使用Readtypeclass 来访问解析器的集合。所以你可能

• 然后再次细化类型Read a => String -> Maybe (Tree a)
• 导入Safe模块以访问readMay :: Read a => String -> Maybe a
• 然后只需构建Tree解析组件。

第三，Trees 是高度递归的，你的括号 Lispy 语法是高度递归的，你的解析器也应该是。为此，专注于只解析单个节点"(...)"，然后根据需要递归解析内部节点。

最后，您可能希望最终考虑一些更强大的解析工具。Parsec它比Read类更强大，并且可以轻松地从更小、更简单的部分构建更复杂、更递归的解析器。

Answer 3

让我给你一些提示：

1. 树是一种自相似结构。听起来你应该使用...

2. ()代表一棵树Empty

3. 树的表示具有这种结构(string_data_with_type_a string_tree string_another_tree)。似乎这两个括号可以省略，空格分隔这三个参数。

就这样。祝你旅途愉快，哈斯凯勒。

如果你问，我可以给你答案。