Laszlo Nemeth <lnemeth@cs.bilgi.edu.tr> wrote:
Chp 8 of the Haskell Report says:
In this chapter the entire Haskell Prelude is given. It constitutes a *specification* for the Prelude.
My question is how strictly this word "specification" is to be interpreted? I can think of a strict and a loose interpretation:
Surely the obvious meaning is observational equivalence, also sometimes known as referential transparency. For any Prelude function specified as p, you can implement it differently as p', provided that for all possible arguments x to p, p x == p' x So this is your non-loose interpretation. I hesitate to use the word strict, because that has a different accepted meaning in this context. If p is strict in x, then p' must be strict in x as well, and vice versa; if p is non-strict in x, then p' must also be non-strict. The important point is that p and p' could use algorithms that belong to different complexity classes, or have different constant factors, and that is fine, provided the results are the same. Regards, Malcolm