4

In Haskell, equality test is normally performed using == coming the Eq class. This function is (in most cases) defined under pure Haskell terms, so it follows all consequences of applying it recursively to big data structures. Therefore, a seemingly trivial comparison can take significant amount of time. Come on, this should be instant (reminder about laziness):

ghci> let x = [1..100000000] in x == x
True
(2.81 secs, 14,400,130,800 bytes)

Why doesn't Haskell use comparison by reference here? Does Haskell even allow me to do so if I really want to?

Improve this question
5
  • 2
    No, it uses a concept called referential transparency that means that you can not see a difference between an expression that will produce output, and the actual output. This is important since otherwise it could be used as some backdoor mechanism to make functions impure. Commented Mar 30, 2022 at 13:52
  • 1
    Would you provide such a backdoor? Commented Mar 30, 2022 at 14:03
  • 2
    The main thing is it makes evaluation observable. If I have xs = [1, 2, 3] and ys = id xs and then later I ask xs == ys, if == means a pointer comparison then I get different results depending on whether ys has been evaluated or not. And if that's observable then we need to carefully define when evaluation can happen, so that we can make sure the result of evaluating xs == ys is predictable. Which would basically force us to being an imperative language with code as a sequence of steps, rather than a "timeless" expression language. Plus it rules out many compiler optimisations. Commented Mar 30, 2022 at 14:23
  • Somewhat aside, don't time things in GHCi, as the code is not optimized like it would be in the compiled code where you would really care about performance. Commented Mar 31, 2022 at 12:21
  • 1
    You may be interested in reallyUnsafePtrEquality# and these other questions: stackoverflow.com/q/9649500, stackoverflow.com/q/19355772, stackoverflow.com/q/30175974, stackoverflow.com/q/48163259. Commented Apr 4, 2022 at 16:15

2 Answers 2

Reset to default
14

Short answer: No this isn't possible in Haskell, and for very good reasons. Referential equality is a fundamental part of the language design, and preserving it makes Haskell distinct from many other languages in the language design space.

A slightly longer answer: This is a well-studied topic, typically referred to as observable sharing, dating back to at least early 2000s:

  • Claessen and Sands explain cases in which cases Observable Sharing is useful and how it can be incorporated into the language. This is a very easy to read paper which explains the issue in detail and suggests a non-conservative extension. Good for understanding the basic problems.

  • Gill's solution to this problem is a very viable approach that is used in practice, called type-safe observable sharing. The idea here is that you can create equalities in pure code, but you can only observe them in the monadic IO context; which preserves referential equality. It has no false negatives, and very few false positives. There is also an implementation of this idea on hackage that you can readily use.

Long story short: No, you cannot do referential-equality, or pointer-equality, or directly observe sharing in Haskell for very good reasons. The problem is well studied and understood, and there are practical solutions to address the issue in the Haskell ecosystem without breaking referential transparency.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

If you search for an alternative to comparing references for faster equality calculation, try System.Mem.StableName. The equality of the StableNames of two objects guarantee that both objects are actually the same object. But the inequality does not imply anything, because objects can be duplicated and moved around by the runtime system.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.