[Haskell-beginners] Type classes and synonyms

[Brent Yorgey]

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