EOPL - 1.2.2 - Some Important Examples

The first 2 chapters of the book are quite basic, but in this section we get some interesting tidbits regarding static versus dynamic typing.

Beginning with two easy functions, remove and remove-first. The type definition for a list of symbols is

<list-of-symbols> ::= [] | <symbol> :: <list_of_symbols>

And the implementation of the functions are:

let rec remove_first s los =
   match los with
     [] -> []
   | (smb :: los') when smb = s -> los'
   | (smb :: los') -> smb :: (remove_first s los')
  
let rec remove s los =
   match los with
     [] -> []
   | (smb :: los') when smb = s -> remove s los'
   | (smb :: los') -> smb :: (remove s los')

Of course, the structural equality operator (=) here implies that these functions work not only with lists of symbols, but lists of any type. The type checker correctly infers the type 'a -> 'a list -> 'a list for both lists. In Scheme too it's possible to get generic functions using the structural equality function equal? -- and as it is the function is guaranteed to work with symbols, numbers and characters because it uses eqv? -- but the authors probably didn't want to talk about parametric polymorphism at this point in the discussion.

Now to two more functions, subst and notate-depth, that work on symbol expressions. A symbol expression is either a symbol or a list of symbol expressions, called an slist:

<s-list>            ::= [] | <symbol-expression> :: <s-list>
<symbol-expression> ::= <symbol> | <s-list>

So now we can't directly define in F# functions that work either on a symbol or a list of similar data. We must define a new type that is a disjoint union of symbols and lists of symbol expressions:

type SymbolExp = Symbol of string | SList of SymbolExp list

And now define the function subst as in the book:

let rec subst n old slist =
   match slist with
     [] -> []
   | (s :: sls) -> (subst_in_symbol_expression n old s) ::
                   (subst n old sls)
and subst_in_symbol_expression n old sexp =
   match sexp with
     Symbol s when s = old -> Symbol n
   | Symbol s -> Symbol s
   | SList sl -> SList (subst n old sl)

Note that subst receives plain strings as the new and old parameters, not a Symbol str where str is a string. Also, the list that subst receives is a SymbolExp list and not a SymbolExp that is a SList. The former fact is a difference in relation to the Scheme version (but could easily be changed) and the latter is consistent with the Scheme version; both may seem a bit confusing.

For notate-depth there's still another problem: the values returned by it are not really slists. While in Scheme this causes no problem, in F# we have to define a new type that includes the depth information with every symbol. So we get

type NotatedSymbolExp = NSymbol of string * int 
                      | NSList of NotatedSymbolExp list

And finally, the function:

let rec notate_depth_in_slist slist n =
   match slist with
     [] -> []
   | (s :: sls) -> (notate_depth_in_symbol_expression s n) ::
                   (notate_depth_in_slist sls n)
and notate_depth_in_symbol_expression sexp n =
   match sexp with
     Symbol s -> NSymbol (s, n)
   | SList sl -> NSList (notate_depth_in_slist sl (n + 1))
  
let notate_depth slist = notate_depth_in_slist slist 0

The rest of the code are solutions to the exercises that require coding.

Exercise 1.11

let rec subst n o slist =
   match slist with
     [] -> []
   | ((Symbol s)::sls) when s=old -> ((Symbol n)::subst n o sls)
   | ((SList sl)::sls) -> ((SList (subst n o sl))::subst n o sls)
   | (s::sls) -> s :: subst n o sls

Exercise 1.12

let rec subst_in_symbol_expression n old sexp =
   match sexp with
     Symbol s when s = old -> Symbol n
   | Symbol s -> Symbol s
   | SList sl -> SList (subst3 n old sl)
and subst n old slist =
   List.map (subst_in_symbol_expression n old) slist

Exercise 1.13

let rec notate_depth_in_slist slist n =
   List.map (notate_depth_in_symbol_expression n) slist
and notate_depth_in_symbol_expression n sexp =
   match sexp with
     Symbol s -> NSymbol (s, n)
   | SList sl -> NSList (notate_depth_in_slist sl (n + 1))