Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Testing for congruence in Haskell

Name: Anonymous 2008-12-06 14:08

Hello /prog/ Haskell programers users. Is it possible to test for the congruence of expression in Haskell? I know i can say
this a = if (a 12) == 12 then (a 12) else (a 13)
and expect this (\ x -> x + 1) to eval to 14. But is there anyway to test for the equivalence of two (or more) expressons without actually applying either of them? In other words, can haskell do anything with thunks, aide from than apply them?

(\ x -> x) == (\ x -> x) is not an expression. Is there a corrext syntax for this type of thing?
Thanks,

Name: Anonymous 2008-12-06 15:25

There is no way to know in general if two programs compute the same function.  This is because not all programs actually halt and give an answer and there is no way to know before hand if a program is in that class.  Since there is no way (in general) to know what a program will output without actually running it there is no way to tell if two programs are equivalent.

Not only that, but programs could have infinite domains meaning in order to know they are equivalent you'd have to compare an infinite amount of outputs.

The only way this could possibly work is if you limited your notion of "expressions" to something less than Turing complete and if you only wanted to assert equivalence over a limited domain.

TL;DR no, but maybe if you limited what you actually want.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List