How to type annotate a function that can take anything as argument, and can output anything as value (parametric polymorphism)?

I need to bind a function to the property of a structure. I'm using typed racket, so it means that I also need to type annotate said function. This function can be any function. It doesn't matter what it takes as arguments or their types. It doesn't matter what the value it returns is or its type.

I'm looking for a way to annotate a function type of this nature. The most general function type there is. It doesn't matter what the function does, it just matters that it is a function.

Something like

'a -> 'b in ocaml
t1 -> t2 in haskell
(...args: any[]) => any in typescript
Callable in python
parametric polymorphism in some languages
generic function in some languages

I read about polymorphic functions in the docs, and found that it can be done using All. Then tried with the type annotation:

(All (A B) (-> A B))

But it doesn't work. For example, with the code:

#lang typed/racket

(define (f x y) (list x y))
(struct some-struct ([g : (All (A B) (-> A B))]))

(define example (some-struct f)) ; Doesn't typecheck

I get the following typecheck error:

type mismatch
  expected: (All (A B) (-> A B))
  given: (-> Any Any (List Any Any))

Also tried with:

#lang typed/racket

(define (f x y) (list x y))
(struct some-struct ([g : (-> Any Any)]))

(define example (some-struct f)) ; Doesn't typecheck

But getting the following typecheck error with that:

type mismatch
  expected: (-> Any Any)
  given: (-> Any Any (List Any Any))

How can a function type annotation be defined, so that it can take any number of arguments, of any type, and return any type as value? Can this be done in typed racket? If so, is All the way to achieve this? Or perhaps it is done through another polymorphic or generic idiom?

Is there a type that matches all functions? Is there a type annotation that will typecheck all functions?

Solution

This answer is a mirror of my answer on Reddit.

Procedure is the supertype of all function types. You can use this as a struct field type, but it's not very useful because there's no way to typecheck something like:

(struct some-struct
  ([proc : Procedure]))

; and then later ...

(λ ([s : some-struct])
  ((some-struct-proc s) 1))

The trick is that the solution doesn't come from a function type annotation, but TR's struct. Notice maybe-type-vars here. When used, the structure itself is polymorphic. The name becomes a type constructor, not a type in itself:

(struct (T) some-struct
  ([proc : (∩ T Procedure)]))

This lets you use any function, but its usage will need to be annotated:

(define (use-num->num-struct-proc
         [s : (some-struct (Number -> Number))]
         [arg : Number]) : Number
  ((some-struct-proc s) arg))

(use-num->num-struct-proc (some-struct add1) 1)

You can generalize this (including to any arity!) like so:

(: use-struct-proc (All (B A ...)
                        (-> (some-struct (-> A ... A B))
                            A ... A
                            B)))
(define
  (use-struct-proc s . args)
   (apply (some-struct-proc s) args))

(use-struct-proc
 (some-struct +))
(use-struct-proc
 (some-struct +) 1 2)
(use-struct-proc
 (some-struct add1) 1)

Since you want a struct with a single procedure and metadata, consider having the struct act as the procedure with prop:procedure:

(struct (T) some-struct
  ([proc : (∩ T Procedure)]
   [metadata : String])
  #:property prop:procedure
  (struct-field-index proc))

This lets you do stuff like:

(define annotated-add1 (some-struct add1 "this procedure adds 1"))

(ann annotated-add1 (Number -> Number))

(map annotated-add1 '(1 2 3 4 5))

(some-struct-metadata annotated-add1)