Polymorphism

Virtually every Scheme program uses lists and sexpressions. Fortunately, Typed Scheme can handle these as well. A simple list processing program can be written like this:

(module add-list (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define: (sum-list [l : (Listof number)]) : number
    (cond [(null? l) 0]
          [else (+ (car l) (sum-list (cdr l)))])))

This looks similar to our earlier programs — except for the type of l, which looks like a function application. In fact, it’s a use of the type constructor Listof, which takes another type as its input, here number. We can use Listof to construct the type of any kind of list we might want.

We can define our own type constructors as well. For example, here is an analog of the Maybe type constructor from Haskell:

(module maybe "typed-lang.ss"
  (define-typed-struct Nothing ())
  (define-typed-struct (a) Just ([v : a]))
  
  (define-type-alias (Maybe a) (U Nothing (Just a)))
  
  (define: (find [v : number] [l : (Listof number)]) : (Maybe number)
    (cond [(null? l) (make-Nothing)]
          [(= v (car l)) (make-Just v)]
          [else (find v (cdr l))])))

The first define-typed-struct defines Nothing to be a structure with no contents.

The second definition

(define-typed-struct (a) Just ([v : a]))

creates a parameterized type, Just, which is a structure with one element, whose type is that of the type argument to Just. Here the type parameters (only one, a, in this case) are written before the type name, and can be referred to in the types of the fields.

The type alias definiton

  (define-type-alias (Maybe a) (U Nothing (Just a)))

creates a parameterized alias — Maybe is a potential container for whatever type is supplied.

The find function takes a number v and list, and produces (make-Just v) when the number is found in the list, and (make-Nothing) otherwise. Therefore, it produces a (Maybe number), just as the annotation specified.