EOPL - 1.1 - Recursive Sets of Data

The ML languages, unlike Scheme, don't have a "cons pair" type. For pairs one can use tuples, and for proper lists there are lists. This means it is not possible to build an improper list in ML. So it is with F#, and this implies a simple change to the definition of lists of numbers (Definition 1.1.2, page 2).

Definition 1.1.2 The set list-of-numbers is the smallest set of values satisfying the two properties:

1. The empty list is a list-of-numbers, and
2. If l is a list-of-numbers and n is a number, then the cons expression (n :: l) is a list-of-numbers

Another point of difference is that F# lacks a native symbol type. Regarding the examples in the book, it seems we can safely use strings in place of symbols, although I don't know if later chapters make use of the fact that the symbols may have associated values. Regarding types, we can use a simple type synonym:


type Symbol = string


Or a tagged type:


type Symbol = Symbol of string


The latter will be more useful when defining other types of expressions, like the examples for the lambda-calculus. In this case there will be symbols, applications and abstractions, and not only a single variant.

With this in mind, it's easy to define a list-of-symbols type. At this point in the book, though, there's not much attention to representation of the data types, as the goal is to become familiar with recursive definitions. It uses the lisp pair notation, however, and lisp symbols, and these dependencies would be thus represented in F#. The same would hold for Standard ML or OCaml, of course.