[Haskell-cafe] Is there a notion for identity?

[Robert Dockins]

On Sunday 08 January 2006 06:43 am, Tim Walkenhorst wrote:
> {- Disclaimer: I'm rather new to Haskell and completely new to this board.
>      I may not use the correct terminology in all cases, but I hope my
>      intention becomes clear when you have a look at the code-snippets. -}
>
> Hey ho,
>
> Is there any way two find out whether two variables refer to the
> same cell? That is I'm looking for a notion of identity (compareable
> to == in Java) as opposed to equality (== in Haskell).

Another poster has already replied with a link to a long answer.  The short 
answer is "no, not really".

An attempted rationale:

The semantics of such an "identity" operator are unclear.  The operator could 
be a test for leibenz equality (ie, structural equality, ie replaceability in 
all contexts), but such an operator cannot be decidable (proof due to 
Church), so that wouldn't help in your situation anyway.  The general 
usefulness of such an operator is debatable.

We could instead provide an implementation-dependent operation that tests for 
identical heap location, but such an operator would give different results 
with different Haskell implementations and would be sensitive to 
optimizations.  That would either be a horribly broken operator or (to fix 
the brokeness) greatly constrain the avaliable optimizations and 
implementation strategies.



For the problem at hand (involving the STLC), you will not be able to type 
omega because omega is a non-normalizing closed term and STLC has the strong 
normalization property.  You will have to move to a more expressive calculus 
to type omega.


Rob Dockins