[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).
-Brent
More information about the Beginners
mailing list