haskell - 如何在 Haskell 中定义树状 DAG

Question

如何在Haskell中定义最好的有向无环图(DAG)(字符串)(只有一个根)？

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

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

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

当字符串列表 ([String]) 包含(直接)子代的名称时，您还可以再次使用 [(String,[String])] 。但同样，第一个任务很难完成。

我能做什么？还有哪些替代方案？哪种方式最有效？

编辑:还有一点:我也希望它能够轻松定义。我必须自己“手动”定义此数据类型的实例，因此我想避免不必要的重复。

Answer 1

你看过the tree implemention in Martin Erwig's Functional Graph Library吗？ ？每个节点都表示为包含其子节点和父节点的上下文。请参阅graph输入类以了解如何访问它。它可能不像您要求的那么容易，但它已经存在，经过充分测试且易于使用。我已经在一个大型项目中使用它十多年了。