在Haskell中解开结的任何好工具？ [英] Any nice tools for untying knots in Haskell?

问题描述

我有一个包含几种不同类型的内部循环链接的数据结构，从 cycle 命令的意义上说它是无限的。是否有任何有趣的模块将这些结构折叠为使用索引的平面数据结构？

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

构建顺序索引，但基于内存地址散列值的索引也可能正常工作。

解决方案

这不太可能;从纯代码中无法检测到列表 repeat 1 是循环的。事实上，它甚至可以不是循环的，在Haskell的充分深奥的实现上。

它 在技术上可行然而，Haskell的常见实现使用了一种名为 observable sharing ， ¹ 的技术，但它非常复杂，除非你是一位非常有经验的Haskell程序员，大多数时候你并不是真的想用可观察的共享来解决你的问题。除非你有非常特殊的要求，这将是一个好主意，否则我会建议代之以循环图你的结构直接代表;例如使用图形库，例如标准的 Data.Graph 或 FGL 。

如果你想尝试可观察的共享，我会建议使用 data-reify 包（如 IO 类型安全的可观察的共享在Haskell中）基于code>的界面;它基本上基于内存地址（实际上，按照你的建议， StableName s）。

你不应该使用可观察的原因之一除非您确实需要共享，否则会破坏参考透明度;例如，它允许您区分 repeat 1 和 1：repeat 1 ，甚至让xs = 1：xs in xs 和 let fx = x：fx in f 1 ，其中取决于编译器优化！

¹ 可观察共享背后的基本思想是公开由标准Haskell实现完成的共享，基本上可以概括为重复值不会复制它们;所以 let xs = 1：xs in xs 是一个循环列表，因为整个 xs 的相同值是用于它的尾部，而不是每次重新计算它，并且（\ x - >（x，x））昂贵 / code>是一些产生大结果的长时间运算）只会产生两个指向 expensive 的指针，而不是复制thunk（这意味着，甚至如果你强制这两个字段，计算将只进行一次，并且结果将只存储一次）。

I've a data structure with several different types of internal circular linking, making it infinite in the sense of say the cycle command. Are there any interesting modules for collapsing such structures into flat data structures that use indexing instead?

I'm interested in serializing the complete data structure, both via Read and Show as well as via Data.Serialize or similar.

There are obviously nice features of building a sequential index, but an index based upon hash values of memory addresses might work fine too.

解决方案

This isn't really possible; there is no way to detect, from within pure code, that the list repeat 1 is cyclic. Indeed, it could even not be cyclic, on sufficiently esoteric implementations of Haskell.

It is technically possible on common implementations of Haskell, however, using a technique called observable sharing,¹ but it's rather complicated, and unless you're a very experienced Haskell programmer, most of the time you don't really want to solve your problem with observable sharing.

Unless you have very special requirements that would make this a good idea, I would suggest instead representing the cyclic graph that your structure represents directly; for instance, using a graph library such as the standard Data.Graph or FGL.

If you do want to try observable sharing, though, I would suggest using the data-reify package (as described in Type-Safe Observable Sharing in Haskell), which only requires a simple type-class instance and has a safe, IO-based interface; it's essentially based on memory addresses (actually, StableNames), as you suggested.

One of the reasons you shouldn't use observable sharing unless you really have a need to is that it breaks referential transparency; for instance, it allows you to distinguish repeat 1 and 1 : repeat 1, and even let xs = 1 : xs in xs and let f x = x : f x in f 1, of these depending on compiler optimisations!

¹ The basic idea behind observable sharing is to expose the sharing done by standard Haskell implementations, which can be basically summarised as "duplicating values doesn't copy them"; so let xs = 1:xs in xs is a cyclic list, because the same value for the entirety of xs is used for its tail, rather than recomputing it each time, and (\x -> (x,x)) expensive (where expensive is some long-running computation that produces a large result) just results in two pointers to expensive, rather than copying the thunk (which means that, even if you force both fields, the computation will only be done once, and the result will only be stored once in memory).

这篇关于在Haskell中解开结的任何好工具？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！