[Haskell] standard prelude and specifications
Malcolm.Wallace at cs.york.ac.uk
Thu Apr 13 06:14:55 EDT 2006
Laszlo Nemeth <lnemeth at 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.
More information about the Haskell