"too polymorphic" type error

[Fergus Henderson]

On 31-Jul-2000, Shiv <shiv@balrog.ece.ucsb.edu> wrote:
> 
> I am getting an unfamiliar type error and wondered if somebody could
> tell me what I am doing wrong.

I'm not an expert in Clean, and I don't have the Clean language
reference manual at hand, so I could be wrong about this...
but I do have a bit of experience in Haskell, and my guess is
that problem here is probably the same as one that comes up
in Haskell every now and then.

...
> binSort :: (b a -> Bool) [b] [a] -> [[a]]
> binSort isInBin bins elems
>     = last (scan (insertInBin bins) ([[] \\ b <- bins]++[[]]) elems)
> where
>     insertInBin :: [b] [[a]] a -> [[a]] // Type Error here ************
>     insertInBin [] [as:ass] e = [[e:as]:ass]
>     insertInBin [bin:bins] [as:ass] e
>     | isInBin bin e = [[e:as]:ass]
>                     = [as:insertInBin bins ass e]
...
> Type error [test3.icl,11,insertInBin]: specified type is too
> polymorphic (contains monomorphic type variables)

I think the problem here is with the scope of the `b' in the type
declaration for `insertInBin'.  If you write a type declaration
for `insertInBin', then I think the scope of the type variables
in that declaration will be local to that declaration.  That is,
the `b' in the declaration of `insertInBin' is a different type
variable from the `b' in the declaration of `binSort'.  Your
declaration implicitly means

	insertInBin :: forall a b . [b] [[a]] a -> [[a]]

However, `insertInBin' is not fully polymorphic in this way,
since it uses the `isInBin' parameter from its environment.
The actual type inferred from `insertInBin' will be

	insertInBin :: forall a . [b] [[a]] a -> [[a]]

where the `b' here is the same type variable as the `b'
in the type declaration for the outer function `binSort'.
Unfortunately, there is probably no way to write such a type!
At least in Haskell 98 there isn't.  I don't know if Clean
provides any syntax for it, but I suspect not.

So, you can leave that type declaration out; or you can pass
`isInBin' as an explicit parameter to `insertInBin', thus ensuring
that the type of `insertInBin' does not depend on any of the type
variables in its containing function's type declaration, so that
you can write a type declaration for it.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.