haskell - 在 Haskell 中解开结的任何好工具？

Question

我有一个具有几种不同类型的内部循环链接的数据结构，使其在 cycle 的意义上是无限的。命令。是否有任何有趣的模块可以将此类结构折叠成使用索引的平面数据结构？

我对通过 Read 序列化完整的数据结构感兴趣。和 Show以及通过Data.Serialize或类似的。

构建顺序索引显然有很好的特性，但是基于内存地址哈希值的索引也可以正常工作。

Answer 1

这真的不可能；无法从纯代码中检测到列表 repeat 1是循环的。事实上，在 Haskell 的足够深奥的实现中，它甚至可能不是循环的。

它在 Haskell 的常见实现上在技术上是可行的，但是，使用一种称为可观察共享的技术，1 但它相当复杂，除非你是一个非常有经验的 Haskell 程序员，大多数时候你并不想解决你的问题具有可观察的共享。

除非您有非常特殊的要求可以使这成为一个好主意，否则我建议您改为表示您的结构直接表示的循环图；例如，使用标准 Data.Graph 等图形库或 FGL .

但是，如果您确实想尝试可观察共享，我建议使用 data-reify包(如 Type-Safe Observable Sharing in Haskell 中所述)，它只需要一个简单的类型类实例并有一个安全的 IO - 基于界面；正如您所建议的，它基本上基于内存地址(实际上是 StableName s)。

除非您确实需要，否则不应使用可观察共享的原因之一是它破坏了引用透明度；例如，它可以让您区分 repeat 1和 1 : repeat 1 , 甚至 let xs = 1 : xs in xs和 let f x = x : f x in f 1 ，其中取决于编译器优化!

1 可观察共享背后的基本思想是公开标准Haskell实现所做的共享，基本上可以概括为“复制值不复制它们”；所以let xs = 1:xs in xs是一个循环列表，因为整个 xs 的值相同用于它的尾部，而不是每次都重新计算它，并且 (\x -> (x,x)) expensive (其中 expensive 是一些长时间运行的计算，会产生很大的结果)只会产生两个指向 expensive 的指针，而不是复制 thunk(这意味着，即使您强制两个字段，计算也只会进行一次，结果只会在内存中存储一​​次)。