[Haskell-beginners] Type classes and synonyms

Brent Yorgey byorgey at seas.upenn.edu
Sun Nov 22 10:42:38 EST 2009

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).


More information about the Beginners mailing list