[Haskell-cafe] pointer equality

[Antoine Latter]

On Wed, Jul 20, 2011 at 10:48 AM, Thiago Negri <evohunz at gmail.com> wrote:
> Hello all,
> I'm a newbie at Haskell and I was not aware of this problem.
> So, equality comparison can run into an infinite-loop?
>
> My current knowledge of the language tells me that everything is
> Haskell is a thunk until it's value is really needed.
> Is it possible to implement (==) that first check these thunks before
> evaluating it? (Considering both arguments has pure types).
>

One thing to remember is that (==) is an ordinary Haskell function -
it isn't a special built-in operator. Every type that implements
implements it as an ordinary Haskell function. There is support to
have the compiler right the function for you in some cases, but I
don't believe it uses any facilities unavailable to an ordinary
app/library author.

The notion of "thunks" is a deep implementation detail - there's no
mandate that the concept be used in a Haskell implementation, so the
language doesn't expose the concept in a concrete way.

I think that some folks have released libraries that call into
internal GHC hooks to see if a run-time value points to an unevaluated
thunk.


>
> E.g.,
>
> Equivalent thunks, evaluates to True, does not need to evaluate its arguments:
>    [1..] == [1..]
>

How would we measure "equivalence" on thunks? We would need to open up
the thunk, inspect the pieces, and then somehow call the appropriate
(==) method on the different pieces - and then some of the pieces
themselves might be thunks on the LHS but not the RHS, and the thunks
on the LHS and the RHS might be equivalent but of completely different
nature:

think of:

> f x == g y

Where f & g are completely different functions. Both might evaluate to
[1..] through independent means, the only way to know would be to
evaluate them, which might not terminate.

>
> Another case:
>
> fib = 1:1:zipWith (+) fib (tail fib)
> fibA = 1:tail fib
> fib == fibA -- True
>
>
> Evaluating:
>
> 1:1:zipWith (+) fib (tail fib) == 1:tail fib -- first item match, check further
> 1:zipWith (+) fib (tail fib) == tail fib -- thunks do not match,
> evaluate arguments
> 1:zipWith (+) fib (tail fib) == 1:zipWith (+) fib (tail fib) -- thunks
> matches, comparison stops and the value is True
>
>
> As I said before, I'm a newbie at Haskell. Sorry if my question or
> examples makes no sense.

One other thing to note is that GHC strips away almost all types
during the process of compilation, so a lot of advanced reflection
needs to be done with structures that explicitly keep the type around
during run-time,

>
> Thanks,
> Thiago.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>