The most succinct way of describing the problem is that you are asking for a higher-rank type whereas Elm only supports rank-1 types.
Let’s unpack that terminology a bit by looking at another example that isolates the problem.
myPair : (Int, String)
myPair = (identity 0, identity "")
We reuse identity for two different inputs of different types. Easy peasy. identity is polymorphic after all.
Let’s say we want to do a common refactor and pull out identity as a parameter to myPair instead.
myPairF f = (f 0, f "")
Uh oh, Elm has an error.
The 1st argument to `f` is not what I expect:
1| myPairF f = (f 0, f "")
^^
This argument is a string of type:
String
But `f` needs the 1st argument to be:
number
Hint: Try using String.toInt to convert it to an integer?
But what if we really try to tell Elm that f is meant to be polymorphic just like identity by adding a type annotation?
myPairF : (a -> a) -> (Int, String)
myPairF f = (f 0, f "")
Still no luck.
The 1st argument to `f` is not what I expect:
2| myPairF f = (f 0, f "")
^
This argument is a number of type:
number
But `f` needs the 1st argument to be:
a
What’s going on? Elm elides a certain feature of our type annotations that is often called forall.
-- The "real" type of identity, note forall isn't valid Elm syntax
identity : forall a. a -> a
When you call identity 0, the Int associated with the 0 is substituted for the variable that appears in the left-most forall.
Importantly, because our forall is on the “outside,” how a gets substituted is determined by the caller of identity. E.g. identity 0 turns a into an Int because 0 is an Int, identity "" turns a into a String because "" is a String, etc.
So in myPair everything is fine, identity has its a substituted twice in different ways (by an Int and String respectively) and we’re fine.
What about myPairF?
-- Again the "real" type signature of myPairF
myPairF : forall a. (a -> a) -> (Int, String)
Again, because forall is on the left-most side of this type signature, the caller gets to decide how a is substituted.
So whoever calls myPairF gets to arbitrarily set a to Int, String, Float, or whatever!
This means the following type signatures are all valid specializations of myPairF:
myPairF : (String -> String) -> (Int, String)
myPairF : (Int -> Int) -> (Int, String)
-- etc.
So for example myPairF String.toUpper turns a into a String. That’s bad! myPairF String.toUpper which makes f = String.toUpper is impossible to square with f 0. This is why when Elm’s typechecker goes to typecheck the definition of myPairF, within myPairF a is an opaque type that is incompatible with Int and String.
So what you need is some way to tell Elm to “delay” the resolution of a.
-- Hypothetical Elm syntax
myPairF0 : (forall a. a -> a) -> (Int, String)
myPairF0 f = (f 0, f "")
Notice now that forall a has been “moved in” one level; it is no longer on the left-most side. In particular that means arguments to myPairF0 cannot cause concrete type substitutions for a. In other words, your caller isn’t allowed now to willy-nilly say “I want a to be an Int.” You can only decide to set a to a concrete value after “unwrapping” it once (in this case by using it in the body of myPairF0.
In particular myPairF0 String.toUpper is a type error because String -> String is not the same type as forall a. a -> a. However, myPairF0 identity works just fine, and yields the original myPair result.
Now myPairF0 is an example of a type signature with a rank-2 type, where a rank-n type is how “deep” a forall is in the type signature (in this case it is one additional level deep because it’s inside a set of parentheses, rather than at the outermost layer of the type signature). Elm only supports rank-1 types. That means that forall must always appear on the left-most side of the type signature and cannot be inside any parentheses. That also means that you cannot write the myPairF0 function in Elm!
Okay now that we’ve isolated the particular problem, how does this apply to your original puzzle? Let’s write out everything with explicit foralls.
-- Notice that forall is on the left-most side!
obj : forall a. { int : Int, fn : a -> a }
obj = { int = 0, fn = identity }
-- This is not the "same" fn as obj.fn
-- You're effectively "re-specializing" obj.fn
-- Read on for what I mean
fn : forall a. a -> a
fn = obj.fn
-- For example this is perfectly valid as well
fn0 : Int -> Int
fn0 = obj.fn
-- Just to drive the point home, notice that this is valid!
-- (which is probably not what you want)
-- Elm is allowing an "in-place" update of `identity` to `\x -> x + 1`!
thisIsValid : { int : Int, fn : Int -> Int }
thisIsValid = { obj | fn = (\x -> x + 1) }
y : forall a. { int : Int, fn : a -> a }
y = fn obj
puzzle : forall a. { int : Int, fn : a -> a } -> ???
puzzle arg = arg.fn arg
-- Notice that because forall is on the left-most side
-- puzzle thisIsValid
-- must be a valid Elm value. But what could it be?
-- `fn` in `thisIsValid` is `Int -> Int` after all.
Notice that because forall is on the left-most side of puzzle, it must decided once upfront by the caller, so something like puzzle thisIsValid could completely spoil puzzle!
What you really want is for the forall to be nested inside your record.
fixedObj : { int : Int, fn : forall a. a -> a }
fixedObj = { int = 1, fn = identity }
puzzle : { int : Int, fn : forall a. a -> a } -> { int : Int, fn : forall a. a -> a }
puzzle arg = arg.fn arg
-- We're fine here because `arg.fn` exposes its `forall a` _inside__ puzzle.
-- This allows `arg`'s type signature to be substituted for `a`
-- Notice that thisIsValid wouldn't work here:
-- (\x -> x + 1) does not have the type signature forall a. a -> a
puzzle fixedObj -- Works great!
puzzle thisIsValid -- Type error
But you can’t write this in Elm and it is unlikely Elm would ever get the ability to move foralls in and out of parentheses. This is because this affects type inference. Notice that obj and fixedObj have identical definitions, but have incompatible type signatures (unlike Int -> Int and a -> a one cannot be substituted for the other). This would mean that certain expressions in Elm would require* type annotations (whereas right now type annotations are always optional).
* I’m telling a small fib here. It turns out you can preserve global type inference for rank-2 types, but not for any even higher-rank types, e.g. if you had even further levels of nesting of forall. However, the rank-2 type inference algorithm is significantly more complicated than Elm’s current type inference algorithm.
EDIT: I made a small error in one of my code samples (see the edit history of this post for details)
EDIT 2: Also just for accuracy’s sake, what I’ve actually illustrated in the revised type signature of puzzle is something known as impredicative types, but the difference is subtle and somewhat moot for Elm because Elm’s not getting either one unless something drastically changes in its philosophy.
The pure rank-2 type would be
puzzle : forall b. (forall a . { int : Int, fn : a -> a }) -> { int : Int, fn : b -> b }
but it’s a bit overwhelming to parse the repeated nested foralls and I’d need to explain why forall b is allowed to appear at the beginning of the type signature rather than also being nested with the output (I can if people are interested, but it’d make this reply even longer). So I cheated a little by using impredicative types. However, the fundamental idea is the same: judicious application of forall gets you what you want, but Elm is not capable of expressing it.