SML Operator and operand don't agree in foldr

Question

I'm working on an assignment where I have to write a function to get the length of a list. This is a trivial task, but I've come across something that I don't understand.

My simple code

val len = foldr (fn(_, y) => y + 1) 0

produces this warning

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

and when I try to run it in the REPL, I get this:

len [1, 2, 3, 4];
stdIn:18.1-18.17 Error: operator and operand don't agree [overload conflict]
operator domain: ?.X1 list   operand:     
[int ty] list   in expression:
    len (1 :: 2 :: 3 :: <exp> :: <exp>)

I don't understand why this doesn't work. I do know some functional programming principles, and this should work, since its very simple partial application.

Of course I can make it work without partial application, like this

fun len xs = foldr (fn(_, y) => y + 1) 0 xs

but I would like to understand why the first version doesn't work.

Anton Trunov Anton Trunov · Accepted Answer · 2016-10-12T13:27:00

This is an instance of the value restriction rule application:

In short, the value restriction says that generalization can only occur if the right-hand side of an expression is syntactically a value.

Syntactically,

foldr (fn(_, y) => y + 1) 0

is not a value, it's a function application, that's why it hasn't been assigned a polymorphic type. It has been instantiated with a dummy type, which has a very limited use, e.g. this works:

len []

but in most cases len defined as val is useless.

This restriction exists to guarantee type safety in the presence of variable assignment (via references). More details can be found in the linked page.

SML Operator and operand don't agree in foldr

1 Answers