CODEWITHSUNDEEP
schemerackettypecheckingtyped-racket
Pillsy
Pillsy

Reputation: 9901

Simple Typed Racket program doesn't type-check

I'm a rank beginner with Typed Racket, and I was playing around with the very simple Tree type defined in the Beginner's Guide:

#lang typed/racket
(define-type Tree (U leaf node))
(struct: leaf ([val : Number]))
(struct: node ([left : Tree] [right : Tree]))

As an exercise, I decided to write a higher-order function to descend the tree:

(: tree-descend : All (A) (Number -> A) (A A -> A) Tree -> A)
(define (tree-descend do-leaf do-node tree)
  (if (leaf? tree)
      (do-leaf (leaf-val tree))
      (do-node (tree-descend do-leaf do-node (node-left tree))
               (tree-descend do-leaf do-node (node-right tree)))))

This type-checks fine. However, when I try to use it to redefine the tree-sum function that sums all over the leaves, I get a surprising and verbose error message:

(: tree-sum : Tree -> Number)
(define (tree-sum t)
  (tree-descend identity + t))

The error messages are 

Type Checker: Polymorphic function `tree-descend' could not be applied to arguments:
  Argument 1:
    Expected: (Number -> A)
    Given:    (All (a) (a -> a))
  Argument 2:
    Expected: (A A -> A)
    Given:    (case-> (-> Zero) (Zero Zero -> Zero) (One Zero -> One) 
               (Zero One -> One) (Positive-Byte Zero -> Positive-Byte)  
               [...lots of ways of combining subtypes of Number...]
               (Index Positive-Index Index -> Positive-Fixnum) 
               (Index Index Positive-Index -> in: (tree-descend identity + t)

Now, to my untrained eye, it looks like this should work just fine, because clearly the polymorphic type A should just be Number and then everything works. Obviously the language disagrees with me for some reason, but I'm not sure what that reason is.

Upvotes: 3

Views: 242

Answers (1)

Sam Tobin-Hochstadt
Sam Tobin-Hochstadt

Reputation: 5053

Unfortunately, Typed Racket can't infer the proper instantiation of polymorphic functions like tree-descend when you apply them to polymorphic arguments like identity. If you replace identity with (inst identity Number), then the program works fine.

Upvotes: 5

Related Questions