Re: [Algorithms] Complexity of new hardware

[Nicholas \Indy\ R. <ar...@gm...>]

On Sun, Apr 26, 2009 at 3:59 AM, Sebastian Sylvan
<seb...@gm...> wrote:
> If I (or rather, the context in which a function is called) give you the
> type "a->a", and ask you to implement a function satisfying that type, there
> is only one implementation (id). Since you know nothing about what type the
> parameter passed in has, you can't do anything except just return it back
> out. Likewise for "(a,b)->a" (fst).
> On the other hand if I give you the type "Integer->Integer" and ask you to
> write an implementation, there's an infinite number of possibilities that
> can satisfy that type (e.g. +1, +2, etc.).
> So the point is that if the expected type of a specific function is
> polymorphic, then you have less wiggle room to write something that
> satisfies the type - and in some cases the number of implementations that
> can satisfy the type is just one, but even when you add some non-polymorphic
> stuff to the type every polymorphic part will cut out a "degree of freedom"
> from the implementation. The fact that you know something is an Int means
> you can "do more" to the variable - if it's fully polymorphic you can't do
> anything to it (and likewise if it's "numeric" you can only do maths on it,
> and so on).
> Thus, the more polymorphic the type, the smaller the valid "implementation
> space" is, and therefore the more likely it is that an incorrect
> implementation will be caught by the type checker.

Ahh, I understand, And I feel this is the beauty of type inference, as
the simple act of providing an implementation for a function
automatically specializes it. in caml for instance I do not have to
provide any type annotations for the function let f(x, y , z) = x +. y
+. z;; in order for the compiler to know that it is of type float ->
float and thus the only time you encounter an a' -> a' is for
identity, which doesn't occur very often.

Nicholas "Indy" Ray