是否有可能检测到 Haskell 中的共享? [英] Is it ever possible to detect sharing in Haskell?

问题描述

在Scheme 中，原始eq? 测试它的参数是否是同一个对象.例如，在下面的列表中

In Scheme, the primitive eq? tests whether its arguments are the same object. For example, in the following list

(define lst
  (let (x (list 'a 'b))
    (cons x x)))

结果

(eq? (car x) (cdr x))

是真的，而且无需查看(car x)和(cdr x)也是真的.这使您可以为具有大量共享的数据结构编写高效的相等性测试.

is true, and moreover it is true without having to peer into (car x) and (cdr x). This allows you to write efficient equality tests for data structures that have a lot of sharing.

在 Haskell 中可以实现同样的事情吗?例如，考虑以下二叉树实现

Is the same thing ever possible in Haskell? For example, consider the following binary tree implementation

data Tree a = Tip | Bin a (Tree a) (Tree a)

left  (Bin _ l _) = l
right (Bin _ _ r) = r

mkTree n :: Int -> Tree Int
mkTree 0 = Tip
mkTree n = let t = mkTree (n-1) in Bin n t t

在各个级别都有共享.如果我用 let tree = mkTree 30 创建一棵树，我想看看 left tree 和 right tree 是否相等，我天真地必须遍历十亿个节点发现它们是同一棵树，因为数据共享应该很明显.

which has sharing at every level. If I create a tree with let tree = mkTree 30 and I want to see if left tree and right tree are equal, naively I have to traverse over a billion nodes to discover that they are the same tree, which should be obvious because of data sharing.

我不认为在 Haskell 中有一种简单的方法可以发现数据共享，但我想知道处理此类问题的典型方法是什么，什么时候检测共享以提高效率(或例如检测循环数据结构).

I don't expect there is a simple way to discover data sharing in Haskell, but I wondered what the typical approaches to dealing with issues like this are, when it would be good to detect sharing for efficiency purposes (or e.g. to detect cyclic data structures).

是否有可以检测共享的 unsafe 原语?有没有一种众所周知的方法来构建带有显式指针的数据结构，以便您可以比较指针的相等性?

Are there unsafe primitives that can detect sharing? Is there a well-known way to build data structures with explicit pointers, so that you can compare pointer equality?

推荐答案

有很多方法.

1. 生成唯一 ID 并将所有内容粘贴到有限地图中(例如 IntMap).
2. 最后一个选择的改进版本是制作一个明确的图形，例如使用 fgl.
3. 使用稳定名称.
4. 使用IORefs(另见)，它们都有 Eq 和 Ord 实例，无论包含的类型如何.
5. 有用于可观察共享的库.
6. 如上所述，有reallyUnsafePtrEquality#，但在使用它之前，您应该了解它真正不安全的地方！

1. Generate unique IDs and stick everything in a finite map (e.g. IntMap).
2. The refined version of the last choice is to make an explicit graph, e.g. using fgl.
3. Use stable names.
4. Use IORefs (see also), which have both Eq and Ord instances regardless of the contained type.
5. There are libraries for observable sharing.
6. As mentioned above, there is reallyUnsafePtrEquality# but you should understand what's really unsafe about it before you use it!

另见这个关于完全避免平等检查的答案.

这篇关于是否有可能检测到 Haskell 中的共享?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！