How do I write higher-order functions that take polymorphic functions as arguments in Typed Racket?

Question

For example, how can I write a version of map that will work with polymorphic functions in Typed Racket? I use a simple id function defined as:

(: id : (All (A) A -> A))
(define (id x) x)

When I try to map it over a list i get an error:

> (map id '(1 2 3))

Type Checker: Polymorphic function `map' could not be applied to arguments:
Types: (-> a b ... b c) (Listof a) (Listof b) ... b -> (Listof c)
   (-> a c) (Pairof a (Listof a)) -> (Pairof c (Listof c))
Arguments: (All (A) (-> A A)) (List One Positive-Byte Positive-Byte)
Expected result: AnyValues
   in: (map id (quote (1 2 3)))

Answer 1

You have to manually instantiate the polymorphism in this case:

->  (map (inst identity Integer) '(1 2 3))
- : (Listof Integer) [more precisely: (Pairof Integer (Listof Integer))]
'(1 2 3)

The reason is explained in the Typed Racket Guide here:

Typed Racket’s local type inference algorithm is currently not able to infer types for polymorphic functions that are used on higher-order arguments that are themselves polymorphic.

(see docs for more explanation and examples)