Introduction to Programming in ATS:
<<< PreviousDatatypesNext >>>

Recursive Datatypes

A recursive datatype is one such that its associated constructors may form values by applying to values of the datatype itself. For instance, the following declared datatype charlst is recursive: 

datatype charlst =
  | charlst_nil of () | charlst_cons of (char, charlst)
// end of [charlst]

When applied to a character and a value of the type charlst, the constructor charlst_cons forms a value of the type charlst. As an example, the following value represents a character list consisting of 'a', 'b' and 'c': 

char_cons ('a', char_cons ('b', char_cons ('c', char_nil ())))

We can define a function charlst_length as follows to compute the length of a given character list: 

fun charlst_length (cs: charlst): int =
  case cs of
  | charlst_cons (_, cs) => 1 + charlst_length (cs)
  | charlst_nil () => 0
// end of [charlst_length]

Note that this implementation is recursive but not tail-recursive. By relying on the commutativity and associativity of integer addition, we can give the following implementation of charlst_length that is tail-recursive: 

fun charlst_length
  (cs: charlst): int = let
  fun loop (cs: charlst, n: int): int = case cs of
    | charlst_cons (_, cs) => loop (cs, n+1) | charlst_nil () => n
  // end of [loop]
in
  loop (cs, 0)
end // end of [charlst_length]

Note that the naming convention I follow closely in this book (and elsewhere) mandates that only a tail-recursive function be given a name indicative of its being a loop. A non-tail-recursive function is not called a loop because it cannot be translated directly to a loop in an imperative programming language like C.

<<< PreviousHomeNext >>>
Enumerative DatatypesUpExhaustiveness of Pattern-Matching