is identity the only polymorphic function without typeclasses?

Jerzy Karczmarczuk
Mon, 03 Mar 2003 11:09:17 +0100

Cagdas Ozgenc quotes himself (and somebody else):

 >>>Is identity function the only meaningful function one can write
 >>>without constraining the type variable using a typeclass?  If not,
 >>>could you please give a counter-example?

 >>Certainly you can write lots of ``meaningful function''s without type
 >>classes: not, (&&), (||), as well as many more complicated functions at
 >>more complicated types.
 >>You can also write useful polymorphic functions without type classes, as
 >>long as you specify at least one type.

 >>I'm somewhat curious, though: why do you ask this question?  How do you
 >>expand your question that makes the answer seem to be ``no''?
 > I did not mean to include functions that take type constructors as
 > parameters (so lists are out of my discussion scope). I am only considering
 > functions that uses type variables that are not restricted by typeclasses.
 > In this setting could you give a few useful function signatures, and their
 > explanation? How does "not" work polymorphically for example?

Bernard James POPE proposes:

 > There is const:
 >    const ::  a -> b -> a
 >    const x _ = x
 > And of course a family of const like functions:
 >    const' :: a -> b -> c -> a
 >    const' x _ _ = x
 > and so on...

 > There is also undefined:
 >    undefined :: a
 >    undefined = undefined
 > Is this what you are looking for?


My three eurocents.
I believe that the Author of the original query won't care more about
undefined stuff than most of us. He wants truly polymorphic functions,
of the type, say, a->b->a etc., without constraints.

The answer exists, although it is not always trivial to find interesting

Imagine a (postulated) polymorphic type, say, (a->b)->(b->a) . Consider
the symbol (->) to be an implication in logic. Ask yourself; "is it
a tautology, valid for *any* objects of types "a" or "b"? If yes, then
this is a type, and you can in principle find a model for it.

Example: composition

type: (a->b)->(c->a) -> (c->b)
function: (.)
   (.) f g x = f (g x)

On the other hand the "type" (a->b) is *NOT* a valid theorem. This is not
a type. You won't find any model of it. No, no, get out with your
f x = undefined.

The "subst" combinator:  subst f g x = f x (g x) has the type

(a->b->c) -> (a->b) -> a -> c   (unless I've produced some mistake)

You can sing the rest of this solemn song yourself, you know the basic tune.
Read Luca Cardelli papers, Wadler's "Theorems for free", etc.

Jerzy Karczmarczuk