Pfthb

If I understand it correctly this is the correct way to annotate functions defined in a letrec in Typed Racket:

#lang typed/racket

(letrec ((is-even? (lambda ((n : Nonnegative-Integer))
 : Boolean
 (or (zero? n)
 (is-odd? (sub1 n)))))
 (is-odd? (lambda ((n : Nonnegative-Integer))
 : Boolean
 (and (not (zero? n))
 (is-even? (sub1 n))))))
 (is-odd? 11))

However this gives the error message:

Type Checker: insufficient type information to typecheck. please add more
 type annotations in: is-odd?

A workaround is this:

(local ((: is-even? : Nonnegative-Integer -> Boolean)
 (define (is-even? n)
 (or (zero? n)
 (is-odd? (sub1 n))))
 (: is-odd? : Nonnegative-Integer -> Boolean)
 (define (is-odd? n)
 (and (not (zero? n))
 (is-even? (sub1 n)))))
 (is-odd? 11))

Also forms of the legacy notation work such as this question but I would expect to be able to annotate letrec using current notation too.

You can put type annotations after the function names in the letrec, like this:

(letrec ([f1 : type1 expr1]
 [f2 : type2 expr2])
 body)

For your example, that looks like:

(letrec ([is-even? : (-> Nonnegative-Integer Boolean)
 (lambda (n)
 (or (zero? n)
 (is-odd? (sub1 n))))]
 [is-odd? : (-> Nonnegative-Integer Boolean)
 (lambda (n)
 (and (not (zero? n))
 (is-even? (sub1 n))))])
 (is-odd? 11))

Why does this work, but putting type annotations inside the lambda doesn't?

It's because making sure each lambda typechecks relies on the types of is-odd? and is-even? respectively. However, if you don't annotate the function-names directly, it can only try to infer those types by typechecking the lambdas.

Annotating the function-names directly means that it doesn't even have to look at the lambdas before it knows what types is-even? and is-odd? must have.