On Sun, Nov 22, 2009 at 03:32:07PM +0000, pbrowne wrote:
On Sat, Nov 21, 2009 at 21:08 Felipe Lessa wrote:
Most definitions, if not all, are just the corresponding free theorems (meaning roughly that the definition follows from the type because that's the only definition that doesn't have undefined's).
Question: Is it correct to paraphrase Felipe's description as follows: In Haskell the *term theorems for free* means roughly that the definition of a class, instance or a function follows from the supplied types because they are the only types that don’t have undefined argumens or undefined return types.
That is a good way to paraphrase Felipe's description --- but I don't think Felipe's terminology is correct. Many types do indeed have only a small number, or even only one, possible "interesting" implementation that does not involve undefined anywhere. However, this is not what is meant by "free theorems". A "free theorem" is a *property* which is satisfied by any function with a particular type. For example, any function with the type foo :: [a] -> Maybe a necessarily satisfies foo (map f xs) = fmap f (foo xs) (or, in points-free form, foo . map f = fmap f . foo ) for any list xs and function f, no matter what the implementation of foo (as long as it does not involve undefined or unsafePerformIO or any "cheating" of that sort). -Brent