Why does my permutations function give me a warning when an empty list is passed in?

Question

my permutation function:


    fun perms [] = [[]]
        | perms (x::xs) = let
            fun insertEverywhere [] = [[x]]
            | insertEverywhere (y::ys) = let
                fun consY list = y::list
            in
                (x::y::ys) :: (map consY (insertEverywhere ys))
            end
        in
            List.concat (map insertEverywhere (perms xs))
        end;

input:

perms [];

output:

stdIn:813.1-813.9 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)

val it = [[]] : ?.X1 list list

Can someone explain why the type vars aren't generalized?

I should note, the type of perms is given after inputting perms; as

perms;
val it = fn : 'a list -> 'a list list

So it looks like I have achieved generalized variables, to me at least.

pad pad · Accepted Answer · 2011-11-03T06:13:31

Empty list is a special list which could potentially have any type for its elements. When you invoke perms [], the compiler is confused about the type of elements. You can either use:

> val ps: int list list = perms [];

or

> val ps = perms ([]: int list);

then the compiler is happy because in can inference a specific type of the lists.

Why does my permutations function give me a warning when an empty list is passed in?

1 Answers