On 28/12/2007, at 4:21 PM, Miguel Mitrofanov wrote:
How can I test that partial order in Haskell ?
You can't. It's kinda internal. More specifically, if you try to compute a value, which is not maximal in this order, you'll get an error or loop forever. But you still can use such values in your programs if you don't try to compute them. The point is, maximal values are the only interesting ones, and all others are just approximations.
Right, so when I say to GHCi: Prelude> take 5 [1..] and it says: [1,2,3,4,5] then it really has computed the entirety of the infinite sequence [1..], and not some approximation? Perhaps it is better to say that in a lazy language both approximations and maximal values (least upper bounds of a chain) are interesting. In a strict language we only get our hands on the latter. The "take lemma" nicely captures this kind of thinking. (Ask google about the generalised take lemma, it's a nice paper.) Also note that the notion of equality that's being thrown around is "observational equality", i.e. "x=y" implies that for all contexts (some expression with a suitably-typed hole), if you plug 'x' into the hole, and 'y' into hole, then those two expressions denote the same value. ((Roughly) equivalently, you can use the idea of Leibniz equality: there is no function that distinguishes them. These notions may diverge in Haskell - does anyone know?) As Lennart observed, any (semi-)computable equality predicate is not going to be that strong. cheers peter