CODEWITHSUNDEEP
haskellfunctional-programming
Chris Taylor
Chris Taylor

Reputation: 47402

Is it ever possible to detect sharing in Haskell?

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?

Upvotes: 12

Views: 700

Answers (3)

Yuras
Yuras

Reputation: 13876

There is reallyUnsafePtrEquality#. Also see here

Upvotes: 1

Joachim Breitner
Joachim Breitner

Reputation: 25782

It is not possible in Haskell, the pure language.

But in its implementation in GHC, there are loopholes, such as

In any case, using this in regular code would be very unidiomatic; at most I could imagine that building a highly specialized library for something (memoizatoin, hash tables, whatever) that then provides a sane, pure API, might be acceptable.

Upvotes: 5

Daniel Wagner
Daniel Wagner

Reputation: 153172

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.

Upvotes: 16

Related Questions