[Haskell-cafe] Re: Wikipedia on first-class object

[Peter Gammie]

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