12

Is there any notion of pointer quality in Haskell? == requires things to be deriving Eq, and I have something which contains a (Value -> IO Value), and neither -> nor IO derive Eq.

EDIT: I'm creating an interpreter for another language which does have pointer equality, so I'm trying to model this behavior while still being able to use Haskell functions to model closures.

EDIT: Example: I want a function special that would do this:

> let x a = a * 2
> let y = x
> special x y
True
> let z a = a * 2
> special x z
False
Improve this question

6 Answers 6

Reset to default
13

EDIT: Given your example, you could model this with the IO monad. Just assign your functions to IORefs and compare them. 

Prelude Data.IORef> z <- newIORef (\x -> x)
Prelude Data.IORef> y <- newIORef (\x -> x)
Prelude Data.IORef> z == z
True
Prelude Data.IORef> z == y
False
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I just want to see if two functions I am getting are in fact the same function. I'm trying to create an interpreter for another language which does have pointer equality, and I want to mimick this behavior.
But what does "same function" mean exactly? (\x -> x) is the same function as (\x -> x). The same function as ((\x y -> y) x), etc. I think what you need is an additional datum to track the "address" of a function in your interpreted language. A monad that models an a -> (Int, a) coalgebra might be in order.
Sadly we have the case evil = ID {unId = const undefined} also, so your example is not 100% true. Those pesky bottoms. :)
Well, yes, if you introduce an absurdity or infinite recursion, that's your fault.
9

Pointer equality would break referential transparency, so NO.

Perhaps surprisingly, it is actually possible to compute extensional equality of total functions on compact spaces, but in general (e.g. functions on the integers with possible non-termination) this is impossible.

EDIT: I'm creating an interpreter for another language

Can you just keep the original program AST or source location alongside the Haskell functions you've translated them into? It seems that you want "equality" based on that.

Improve this answer

5 Comments

I am pretty sure that the phrases extensional equality and compact topology are not in the common jargon.
the phrases extensional equality and compact topology are the phrases that keep keep me from trying haskell
Interesting link. My first thought was "this guy is talking rubbish." But we're not talking about general functions, we're talking about computable functions. That makes all the difference.
@Otto: Those phrases are about the computational equality of functions in general, so they apply to all languages. They aren't Haskell-specific.
if you're implementing an interpreter for another language, then just give a unique identifier to every function. ex: change {data Function = Function { args::ArgList, expr::Expression } to {data Function = Function { args::ArgList, expr::Expression, uniqueid::Int } } and assign ids by instantiation order
6

== requires things to be deriving Eq

Actually (==) requires an instance of Eq, not necessarily a derived instance. What you probably need to do is to provide your own instance of Eq which simply ignores the (Value -> IO Value) part. E.g.,

data D = D Int Bool (Value -> IO Value)

instance Eq D where
  D x y _ == D x' y' _ = x==x && y==y'

Does that help, maybe?

Improve this answer

2 Comments

it does, and I did this for now
Yes, x==x' is what I meant.
4

Another way to do this is to exploit StableNames.

However, special would have to return its results inside of the IO monad unless you want to abuse unsafePerformIO.

The IORef solution requires IO throughout the construction of your structure. Checking StableNames only uses it when you want to check referential equality.

Improve this answer

1 Comment

This is a pretty good solution for checking function equality, even though StableNames aren't always equivalent when it intuitively seems they might be. Just wanted to add a link to the docs: hackage.haskell.org/package/base-4.7.0.2/docs/…
3

IORefs derive Eq. I don't understand what else you need to get the pointer equality of.

Edit: The only things that it makes sense to compare the pointer equality of are mutable structures. But as I mentioned above, mutable structures, like IORefs, already instance Eq, which allows you to see if two IORefs are the same structure, which is exactly pointer equality.

Improve this answer

5 Comments

sorry, I fixed my question. IO doesn't derive Eq, and neither do functions. I want to test whether two functions happen to be the same function.
But IOs are not "pointers". I don't see what it would mean to compare them. Can you give an example?
You can't compare two functions to see if they are the same. For instance I could write "foo x = 2 * x" and "bar x = x + x". Clearly foo and bar are equal because for all x, foo x == bar x, but in the general case this is undecidable. I know that isn't quite what you wanted; you want a "may be different functions" comparison. But no, Haskell doesn't have that.
Related question about the undecidability of function equivalence: stackoverflow.com/questions/1132051/…
I realize it's undecidable to see if two functions produce all outputs given the same set of inputs. See my updated post
3

I'm creating an interpreter for another language which does have pointer equality, so I'm trying to model this behavior while still being able to use Haskell functions to model closures.

I am pretty sure that in order to write such an interpreter, your code should be monadic. Don't you have to maintain some sort of environment or state? If so, you could also maintain a counter for function closures. Thus, whenever you create a new closure you equip it with a unique id. Then for pointer equivalence you simply compare these identifiers.

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.