On Wed, Jul 20, 2011 at 10:48 AM, Thiago Negri
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe