How should you type annotate mutually recursive functions in letrec in Typed Racket?

user_3414663 0
Viewed 168

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.

typed-racket
1 Answers

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.

user_54325010
Related