12

你如何在Haskell中最好地定义一个有向无环图（DAG）（字符串）（有一个根）？

我特别需要尽快在这个数据结构上应用以下两个函数：

  1. 查找一个元素的所有（直接和间接）祖先（包括父母的父母等）。
  2. 找到一个元素的所有（直接）子元素。

我想到了[(String,[String])]每一对是图形的一个元素，由它的名称 ( String) 和一个字符串列表 ( )组成，[String]其中包含该元素的（直接）父级的名称。这个实现的问题是很难完成第二个任务。

[(String,[String])]当字符串列表 ( [String]) 包含（直接）子项的名称时，您也可以再次使用。但是在这里，第一个任务很难完成。

我能做些什么？有哪些选择？哪种方式最有效？

编辑：还有一句话：我也希望它可以轻松定义。我必须自己“手动”定义这种数据类型的实例，所以我想避免不必要的重复。

4

1 回答 1

2

你看过Martin Erwig 的功能图库中的树实现吗？每个节点都表示为一个包含其子节点和父节点的上下文。请参阅图形类型类以了解如何访问它。它可能不像您要求的那么简单，但它已经存在，经过充分测试且易于使用。我已经在一个大型项目中使用了十多年。

于 2013-05-19T03:02:36.547 回答