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 `slist`

s. 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))