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

问题描述

在Scheme中，原语 eq？测试它的参数是否是同一个对象。例如，在下面的列表中：

 （define lst 
（let（x（list'a'b）） 
（cons xx）））
  

的结果

 （eq？（car x）（cdr x））
  

是真的，而且如果没有必须同行（car x）和（cdr x）。这允许你为有很多共享的数据结构编写高效的相等性测试。

Haskell有可能做到同样的事情吗？例如，考虑下面的二叉树实现

 数据树a =提示| Bin a（Tree a）（Tree a）
 
 left（Bin _l _）= l 
 right（Bin _ r）= r 
 
 mkTree n :: Int  - > Tree Int 
 mkTree 0 =提示
 mkTree n = let t = mkTree（n-1）in Bin ntt 
  

在每个级别都有分享。如果我使用创建一棵树让let tree = mkTree 30 并且我想看看是否有左树和右树是平等的，天真地，我必须遍历十亿个节点才能发现它们是同一棵树，这应该是显而易见的，因为数据共享。

我并不认为有一种简单的方法可以发现Haskell中的数据共享，但我想知道处理类似问题的典型方法是什么，如果为了效率目的而检测共享或者例如检测循环数据结构）。

是否存在不安全可检测共享的基元？是否有一种众所周知的方式来构建带有显式指针的数据结构，以便您可以比较指针的相等性？ 解决方案

。

1. 生成唯一的ID并将所有内容粘贴在有限映射中（例如 IntMap ）。


2. 最后一个选择的精炼版本是制作一个明确的图形，例如使用 fgl 。


3. 使用稳定的名称。
   
4. 使用 IORef （另见），它们都有 Eq 和 Ord 实例，无论包含的类型如何。
   
5. 如上所述，有<$ li>
c $ c> reallyUnsafePtrEquality＃但在使用它之前，您应该了解它的真正不安全程度！

另见这个答案完全避免了平等检查。

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)))

The result of

(eq? (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.

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

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.

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).

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?

解决方案

There's lots of approaches.

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!

See also this answer about avoiding equality checks altogether.

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