Go backward to Parametric Types Go up to Top Go forward to Existential Quantification

Recursive Definitions

• Recursively defined type operators:
  • rec type List[Item] =
       [nil: Unit
          cons: {head: Item, tail: List[Item]} ]
  • value nil: forall Item.List[Item] = all[Item]. [nil = ()]
    value intNil: List[Int] = nil[Int]
  • value cons:
       forall Item. (Item x List[Intem]) -> List[Item] =
          all[Item].
             fun(h Item, t: List[Item])
                [cons = {head = h, tail = t}]

Cons can be only used to build homogeneous lists!