# Introduction to Scheme Continued¶

## Let¶

Sometimes a Scheme function needs to re-do the same calculation, e.g.:

```
(define operator1
(lambda (e)
(cond
((equal? (car e) '+) 'addition)
((equal? (car e) '-) 'subtraction)
((equal? (car e) '*) 'multiplication)
((equal? (car e) '/) 'division)
(else 'unknown)
)
)
)
```

The expression `(car e)`

is repeated 4 times, making the code a little
longer and slower than it needs to be. Better would be to evaluate `(car e)`

once, save its value, and then use this saved value in place of repeated calls
to `(car e)`

.

Here’s a neat trick that does that for us:

```
(define operator2
(lambda (e)
(
(lambda (op)
(cond
((equal? op '+) 'addition)
((equal? op '-) 'subtraction)
((equal? op '*) 'multiplication)
((equal? op '/) 'division)
(else 'unknown)
) ;; cond
) ;; op
(car e) ;; bound to op
)
) ;; e
)
```

The idea here is to evaluate `(car e)`

one time and assign its value to
`op`

. Then we use `op`

wherever we wrote `(car e)`

. Notice how we are
taking advantage of the fact that a lambda function call binds the value of
the argument you pass it to `op`

.

Clearly, this is longer and harder to read than the code in `operator1`

, and
the distance between `op`

and the value it gets assigned is pretty big —
in practice one could easily not realize that `op`

is being assigned ```
(car
e)
```

.

So what Scheme does is provide some “syntactic sugar” to simplify this trick.
Here is a version that uses a `let`

expression:

```
(define operator3
(lambda (e)
(let ((op (car e))
)
(cond
((equal? op '+) 'addition)
((equal? op '-) 'subtraction)
((equal? op '*) 'multiplication)
((equal? op '/) 'division)
(else 'unknown)
)
)
)
)
```

This is much clearer! Now `op`

and its assigned value are right beside each
other. Plus the use of the `let`

keyword signals our intention much more
clearly than using the basic lambda trick.

In general, a Scheme `let`

expression allows you to define any number of
variables:

```
(let ((x1 val1)
(x2 val2)
...
(xn valn)
)
body ;; x1 ... xn can be used here
)
```

The entire expression returns the value of `body`

, so you can wrap any
expression in a `let`

if useful.

For example:

```
> (let ((a 1) (b 1) (c 2)) (+ a b c))
4
```

There is a subtlety here that is worth exploring a bit. The `let`

expression
in the example could be re-written like this:

```
> ((lambda (a b c) (+ a b c)) 1 1 2)
4
```

Indentation makes the scope clearer:

```
(
(lambda (a b c)
(+ a b c)
)
1 1 2 ;; a, b, c are not in scope here
)
```

The scope of the variables `a`

, `b`

, and `c`

is limited to the lambda
function they’re defined in and, in particular, they *cannot* be used in the
calculation of the parameters passed to it.

So, for example, this expression causes an error:

```
(
(lambda (a b c)
(+ a b c)
)
1 a 2 ;; error: a is not in scope
)
```

If you re-write this as an equivalent `let`

expression, you get this:

```
(let ((a 1)
(b a) ;; error: can't use a in let value expression!
(c 2)
)
(+ a b c)
)
```

This is an also an error, because `let`

does not let you use any of the
variables you are defining within the value expression for any other
variables.

While this limitation makes sense given what `let`

compiles to, it is
inconvenient in practice. And so Scheme provides `let*`

to remove this
restriction. This works as expected:

```
(let* ((a 1)
(b a) ;; okay: this is a let* environment
(c 2)
)
(+ a b c)
)
```

This `let*`

could be re-written as embedded `let`

environments:

```
(let ((a 1))
(let ((b a)) ;; ok: a is in scope
(let ((c 2))
(+ a b c)
)
)
)
```

Or even as plain lambdas:

```
(
(lambda (a)
(
(lambda (b)
(
(lambda (c)
(+ a b c)
)
2 ;; bound to c
)
)
a ;; bound to b
)
)
1 ;; bound to a
)
```

Here’s an example of a basic `let`

expression that evaluates numeric
expressions of the form `(left op right)`

:

```
(define eval-basic
(lambda (e)
(let ((left (car e))
(op (car (cdr e)))
(right (car (cdr (cdr e))))
)
(cond
((equal? op '+) (+ left right))
((equal? op '-) (- left right))
((equal? op '*) (* left right))
((equal? op '/) (/ left right))
(else 'err)
)
)
)
)
> (eval-basic '(1 + 2))
3
> (eval-basic '(1 - 2))
-1
```

Another example where a let-environment is useful is in the following
implementation of the `deep-map`

function. `deep-map`

is a variation of
`map`

that works like `map`

, except the passed-in mapping function is
applied to every non-list value in the list, even those nested inside lists.
For example:

```
> (deep-map1 1+ '(1 (2 (3) 4 5 (6))))
(2 (3 (4) 5 6 (7)))
```

Here’s the definition for `deep-map1`

:

```
(define deep-map1
(lambda (f lst)
(cond
((null? lst)
())
(else
(let* ((head (car lst))
(body (cdr lst))
(new_body (deep-map1 f body))
)
(cond
((list? head)
(cons (deep-map1 f head) new_body))
(else
(cons (f head) new_body))
)
)
)
)
)
)
```

Notice that this uses `let*`

instead of `let`

to make the definition of
`new_body`

easier.

An alternative implementation is to embed the conditional into `cons`

,
e.g.:

```
(define deep-map2
(lambda (f lst)
(cond
((null? lst)
())
(else
(let* ((head (car lst))
(body (cdr lst))
(new_body (deep-map2 f body))
)
(cons (if (list? head)
(deep-map2 f head)
(f head)
)
new_body
)
)
)
)
)
)
```

Yet another way to write it would be to use `my-fold`

from the previous notes. In this
version, there are no repeated computations in the body, so `let`

/`let*`

isn’t needed:

```
(define deep-map3
(lambda (f lst)
(my-fold (lambda (a rest)
(cons (if (list? a)
(deep-map3 f a)
(f a)
)
rest
)
)
'()
lst
)
)
)
```

In fact, it can be done even more simply just using `my-map`

from above,
e.g.:

```
(define deep-map4
(lambda (f lst)
(my-map (lambda (a)
(if (list? a)
(deep-map4 f a)
(f a)
)
)
lst
)
)
)
```

Again, no `let`

/`let*`

is needed here since there are no repeated
expressions.

## A Propositional Expression Evaluator¶

One of the applications that Scheme is good at is writing interpreters, compilers, and other programs that process programming languages. As long as we’re willing to stick languages with a Scheme-like syntax, then Scheme is often a great choice for at least prototyping such programs.

Lets write some functions that deal with literal boolean propositional
expressions like `(t and (not f))`

. The symbols `t`

and `f`

stand for
true and false respectively, and there are no variables allowed in the
expressions. We are not using the built-in Scheme boolean values (`#t`

and
`#f`

) since this is out own little language that we’re defining.

First, we define a series of functions to test if a value has a particular
*top-level* form:

```
(define is-true? (lambda (e) (equal? e 't)))
(define is-false? (lambda (e) (equal? e 'f)))
(define is-literal?
(lambda (e)
(or (is-false? e)
(is-true? e))
)
)
;; returns true iff lst is a list of length n
(define nlist?
(lambda (n lst)
(and (list? lst)
(= n (length lst))
)
)
)
;; (not expr)
(define is-not?
(lambda (e)
(and (nlist? 2 e)
(equal? 'not (car e))
)
)
)
;; (p op q)
(define is-bin-op?
(lambda (e op)
(and (nlist? 3 e)
(equal? op (second e))
)
)
)
(define is-and? (lambda (e) (is-bin-op? e 'and))) ;; (p and q)
(define is-or? (lambda (e) (is-bin-op? e 'or))) ;; (p or q)
```

These are all non-recursive functions that check that the top-level form of an expression. They don’t check if sub-expressions are valid. Also notice how we use lots of little functions to build more complex functions.

Next, lets write a recursive function that tests if an expression is a valid proposition:

```
;; Returns true iff e is a valid propositional expression.
(define is-expr?
(lambda (e)
(cond
((is-literal? e)
#t)
((is-not? e)
(is-expr? (second e)))
((is-and? e)
(and (is-expr? (first e))
(is-expr? (third e))))
((is-or? e)
(and (is-expr? (first e))
(is-expr? (third e))))
(else
#f)
)
)
)
```

The idea of this function is to first determine the top-level form of `e`

,
and then to recursively check that its sub-expressions are also valid.

Next, lets write an evaluator that calculates the value of a valid proposition:

```
(define eval-prop-bool
(lambda (e)
(cond
((is-literal? e)
(is-true? e))
((is-not? e)
(not (eval-prop-bool (second e))))
((is-and? e)
(and (eval-prop-bool (first e))
(eval-prop-bool (third e))))
((is-or? e)
(or (eval-prop-bool (first e))
(eval-prop-bool (third e))))
(else
#f)
)
)
)
(define eval-prop
(lambda (e)
(if (eval-prop-bool e) 't 'f)
)
)
```

For example:

```
> (eval-prop '((not t) and (t or (not f))))
f
```

We write the `-eval-prop`

function to be consistent, i.e. in our boolean
literal language `t`

means true and `f`

means false, and so we want those
values returned instead of `#t`

and `#f`

.

## EBNF: Extended Backus-Naur Notation¶

The `is-expr?`

function is a precise definition of what is, and isn’t, a
valid boolean literal expression. Another way to precisely specify a language
is to use Extended Backus-Naur Formalism, or EBNF
for short. EBNF is a a little language designed for precisely defining the
*syntax* (not semantics!) of programming languages.

An EBNF “program” consists of a series of named **productions**, i.e. rules
of this general form:

```
production-name = body .
```

The idea is that whenever you see `production-name`

in an EBNF rule, you
can replace that name with the `body`

of the corresponding rule. A set of
productions is called a **grammar**, and grammars are very useful for creating
things like lexers and parsers.

We’ll use the Go EBNF notation,
which, among other details given below, ends production rules with a `.`

.
For example, here is the production that Go uses to define an assignment
operator:

```
assign_op = [ add_op | mul_op ] "=" .
```

Anything in “”-marks is indicates a token/symbol that could appear as-is in a
Go program. So in this production, the `"="`

at the end means a `=`

character that appears in a Go program, while the `=`

that appears near the
start is part of the EBNF language that separates a production’s name from its
body.

Two other EBNF operators appear in this production. The `|`

is the
**alternation** operator, and indicates a choices between two, or more,
alternatives. So `add_op | mul_op`

means you can chose `add_op`

or
`mul_up`

(but not both). Here’s another example:

```
add_op = "+" | "-" | "|" | "^" .
```

This production, named `add_op`

, says that an `add_op`

is a `"+"`

,
`"-"`

, `"|"`

, or `"^"`

. This defines `add_op`

by simply listing all
the possible alternatives.

The `[]`

operator indicates an **optional** expression that can occur 0, or
1, times. So the expression `[ add_op | mul_op ]`

means that the entire
expression can appear, or not appear. If it does occur, then, because of the
`|`

, either `add_op`

or `mul_op`

is chosen.

Another EBNF operator is `{}`

, which indicates **repetition** of 0, or
more, times. For example:

```
identifier = letter { letter | unicode_digit } .
```

This describes legal identifiers in Go, i.e. the legal names for things like
variables, functions, structs, types, and packages. It says that an identifier
must start with a `letter`

, and then be followed by 0 or more letters or
digits:

```
letter = unicode_letter | "_" .
decimal_digit = "0" ... "9" .
```

In the Go EBNF notation, `...`

is
an informal short-hand that is used to indicate an obvious pattern. So the
`decimal_digit`

production is understood to be equivalent to this:

```
decimal_digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
```

The `identifier`

rule lets us check if a sequence of characters is a legal
identifier name. For example, `up2`

is a legal Go identifier. We can check
this by tracing the `identifier`

production. The first character, `u`

, is
a valid `letter`

, and the next character is a valid `letter`

. The 2 is a
valid digit, and so the entire identifier is valid.

Now consider `4xyz`

, which is *not* a valid Go identifier. It starts with
`4`

, but according to the `letter`

production `4`

is *not* a valid
letter. So we know `4xyz`

cannot be an `identifier`

, because a valid
`identifier`

must start with a letter.

The `unicode_letter`

production allows all characters marked as “Letter” by
Unicode. There are thousands of such characters, so they are not listed
explicitly.

## Example: EBNF Rules for Literal Propositional Expressions¶

Now lets write an EBNF grammar, using the Go EBNF notation, to describe the valid boolean
literal expressions that `(is-expr? e)`

returns true for.

Here are the productions:

```
expr = bool-literal | not-expr | and-expr | or-expr .
bool-literal = "t" | "f" .
not-expr = "(" "not" expr ")" .
and-expr = "(" expr "and" expr ")" .
or-expr = "(" expr "or" expr ")" .
```

Note that EBNF does not require the productions to appear in any particular order. But, for humans, we usually group related productions, and often put them in the order either from most general to specific, or more specific to general.

We should point out that the syntax of this little language is specifically designed to be Scheme-like, and so every expression is fully-bracketed. This means we don’t need to define the precedence of operators, since the brackets always make that explicit. This makes the parsing much simpler, in fact almost trivial.

Consider the `not-expr`

production. It is recursive because it expands into
an expression involving `expr`

, which could expand into `not-expr`

. This
allows us to show that an expression like “(not (not t))” is valid as
follows:

```
expr = not-expr
= "(" "not" expr ")"
= "(" "not" not-expr ")"
= "(" "not" "(" "not" expr ")" ")"
= "(" "not" "(" "not" bool-literal ")" ")"
= "(" "not" "(" "not" "t" ")" ")"
```

Each step expands one part of the expression, and, by making the right choice
of rules, eventually we get the exact expression we want. If you want to
automate this process, you could write a **parser** to do this.

Comparing this EBNF grammar to the implementation of `is-expr?`

, you can
see that it shares some direct similarities. Each of the productions
corresponds to a Scheme function, and those functions essentially mimic
the recursive structure of the productions.

## Simplifying a Propositional Expression¶

Some propositional expressions can be simplified into logically equivalent
expressions. For example, an expression of the form `(not (not p))`

simplifies to the logically equivalent expression `p`

.

Lets write an *expression simplifier* that applies this one particular rule to
expressions:

```
;; double negation elimination
;; (not (not expr)) <==> expr
(define simplify
(lambda (e)
(cond
((is-literal? e)
e)
((and (is-not? e) (is-not? (second e))) ;; (not (not e))
(simplify (second (second e))))
((is-not? e)
(list 'not (simplify (second e))))
((is-and? e)
(list (simplify (first e)) 'and (simplify (third e))))
((is-or? e)
(list (simplify (first e)) 'or (simplify (third e))))
(else
(error "invalid expression"))
)
)
)
```

`simplify`

first checks if `e`

is of the form `(not (not X))`

. If so,
then it extracts the `X`

(using `(second (second e))`

) and returns the
simplification of it. Otherwise, it tries to simplify the parts of the sub-
expressions (if any) of `e`

.

For example:

```
> (simplify '((not (not t)) and (not (not t))))
(t and t)
```

## Rewriting an Expression with Only nand¶

An interesting and useful fact about propositional logic is that any
expression can be re-written as a logically equivalent expression that uses
onle the `nand`

operator. The expression `(p nand q)`

is true just when
either `p`

, or `q`

, or both, are false. In other words, `(p nand q)`

is
equivalent to `(not (p and q))`

.

Here are the rules for writing the other propositional operators in terms of
`nand`

:

`(not p)`

is logically equivalent to`(p nand p)`

`(p and q)`

is logically equivalent to`((p nand q) nand (p nand q))`

`(p or q)`

is logically equivalent to`((p nand p) nand (q nand q))`

With these rules we can transform any propositional expression into a
logically equivalent one using only `nand`

.

Note here that we are allow variables, like `p`

or `q`

, in the expressions
we want to simplify. However, we don’t make any assumptions about value these
variables represent.

Here’s some code that does the transformation:

```
(define is-prop-literal?
(lambda (x)
(symbol? x)
)
)
(define make-nand
(lambda (p q)
(list p 'nand q)
)
)
;; Returns an expression logically equivalent to e that uses
;; "nand" as the only operator.
(define nand-rewrite
(lambda (e)
(cond
((is-prop-literal? e)
e)
((is-not? e)
(let ((np (nand-rewrite (second e)))
)
(make-nand np np)))
((is-and? e)
(let* ((p (nand-rewrite (first e)))
(q (nand-rewrite (third e)))
(pnq (make-nand p q))
)
(make-nand pnq pnq)))
((is-or? e)
(let* ((p (nand-rewrite (first e)))
(q (nand-rewrite (third e)))
(pnp (make-nand p p))
(qnq (make-nand q q))
)
(make-nand pnp qnq)))
)
)
)
> (pp (nand-rewrite '((p and q) or ((not p) or q))))
((((p nand q) nand (p nand q)) nand ((p nand q) nand (p nand q)))
nand
((((p nand p) nand (p nand p)) nand (q nand q))
nand
(((p nand p) nand (p nand p)) nand (q nand q))))
```

Note the use of the `pp`

function: it “pretty prints” a Scheme expression,
making it is easier for humans to read.

## Example: Rewriting Scheme Code¶

After you’ve written some Scheme code, you may have noticed that these two expressions evaluate to the same thing:

```
(cond (test val1)
(else val2))
;; same as
(if test val1 val2)
```

The if-expression is a little simpler and easier to read, so it’s often the
preferred form. But when writing code you don’t always know for sure if you
have only one test, and so it’s wise to use `cond`

everywhere. After your
program is done you could go back and re-write any single-condition `cond`

expressions as an equivalent if-expression, but that is tedious and
error-prone.

What we could do instead is write a Scheme function to automatically replace
occurrences of a simple `cond`

with an equivalent `if`

.

To do this, we first, we define a few helper functions:

```
;; returns true iff lst is a list of length n
(define nlist?
(lambda (n lst)
(and (list? lst)
(= n (length lst))
)
)
)
;; returns true iff the first element of lst equals x
(define starts-with
(lambda (x lst)
(equal? x (car lst))
)
)
```

Next, we’ll write a function that recognizes simple `cond`

expressions:

```
;; Returns true for cond expressions of this form:
;;
;; (cond (test val1)
;; (else val2) ;; else could be #f instead
;; )
;;
(define is-simple-cond?
(lambda (lst)
(and (nlist? 3 lst)
(starts-with 'cond lst)
(nlist? 2 (second lst))
(nlist? 2 (third lst))
(member (car (third lst)) '(else #t))
)
)
)
```

Notice that the last expression of the `and`

conveniently lets use use
either `else`

or `#t`

.

Now, we write a function that re-writes a simple `cond`

as an equivalent
`if`

:

```
;; (cond (test val1)
;; (else val2))
;;
;; same as
;;
;; (if test val1 val2)
;;
;; Pre-condition:
;; (is-simple-cond? lst)
(define rewrite-simple-cond-top-level
(lambda (lst)
(list 'if (car (second lst))
(second (second lst))
(second (third lst)))
)
)
```

It’s called `top-level`

because it does *not* recursively rewrite any sub-
expressions.

Next, we define a general-purpose rewriting function that replaces one expression with another:

```
(define rewrite
(lambda (is-expr? rewrite-top-level lst)
(cond ((is-expr? lst)
(rewrite is-expr? rewrite-top-level (rewrite-top-level lst)))
((list? lst)
(map (lambda (x) (rewrite is-expr? rewrite-top-level x))
lst))
(else
lst)
)
)
)
```

Here, `is-expr?`

is function (such as `is-simple-cond?`

) that tests if a
value matches an expression, and `rewrite-top-level`

is a function that,
given an expression that satisfies `is-expr?`

, returns a new expression.
`rewrite`

is a *deep* function, i.e. it recursively rewrites all
sub-expression of the passed-in list.

Finally, we use `rewrite`

to create a simple-cond-to-if function like this:

```
(define rewrite-simple-cond
(lambda (x)
(rewrite is-simple-cond? rewrite-simple-cond-top-level x)
)
)
```

You can use it as follows:

```
(define test
'(define my-length
(lambda (lst)
(cond
((null? lst)
0)
(else
(+ 1 (my-length (cdr lst))))
)
)
)
)
;;;
> (pp (rewrite-simple-cond test))
(define my-length
(lambda (lst)
(if (null? lst)
0
(+ 1 (my-length (cdr lst))))))
```

Many kinds of useful code transformations can be implemented in the same way, i.e. by providing a recognizer function, and a top-level rewriting function.

If you write a number of these transformations, you will most likely find that
writing the specific recognizer and re-write functions are usually simple but
tedious. While we won’t go into the details here, it is possible to use
`unify`

(see below) to implement a function called `make-rewriter`

that
lets us implement `rewrite-simple-cond`

like this:

```
(define rewrite-simple-cond
(make-rewriter '(cond (?test ?val1) ;; input pattern
(else ?val2))
'(if ?test ?val1 ?val2) ;; output patten
)
)
```

The implementation of `make-rewriter`

takes a bit of work, but once you have
it then many transformations can be described simply by writing the input
pattern and the output pattern.

Here’s the source code for these two different implementations of these re-writers:

## Pattern Matching with Unification¶

If you do a lot of Scheme programming, you soon discover that you need a lot
of code that splits lists up into pieces using functions like `car`

,
`cdr`

, `cadr`

, `cddr`

, and so on. While this code isn’t hard to write,
it does get pretty tedious and cluttered.

An alternative to writing this sort of code by hand is to use **pattern
matching**. Here, we will use the simple pattern matching code in the file
`unify.scm`

. It implements **unification**
through the use of the function `(unify expr1 expr2)`

. It is easiest to
understand through some examples.

`unify.scm`

provides one main function called
`unify`

that can be called like this:

```
=> (unify 'a 'b)
#f
```

This returns `#f`

(false) because `'a`

and `'b`

are not the same, i.e.
they *don’t* unify. However:

```
=> (unify 'a 'a)
()
```

`'a`

and `'a`

*do* unify, because they are the same. `(unify 'a 'a)`

returns the empty list, `'()`

, which might seem a bit odd. It will make more
sense after seeing some more examples.

Symbols that begin with a `?`

are variables from the point of view of
`unify`

, and they are can be bound to other expressions. For example:

```
=> (unify '?x 'a)
((?x . a))
```

The return value is `((?x . a))`

, which is list of pairs (i.e. an
association list), where each pair is a variable and its value. `unify`

promises that these if you replace the variables in the input expressions with
their corresponding values, then the two expressions will be the same.

In other words, `(unify expr1 expr2)`

returns a list of variable/value pairs
that, when the variables in `expr1`

and `expr2`

are replaced by their
values, the resulting expressions will be the same.

More examples should make this clear:

```
=> (unify '(?x b c) '(a b c))
((?x . a))
=> (unify '(?x b c) '(a b ?y))
((?y . c) (?x . a))
=> (unify '(?x ?x ?x) '(?y 2 ?y))
((?y . 2) (?x . ?y))
=> (unify '(?left ?op ?right) '(5 + x))
((?right . x) (?op . +) (?left . 5))
=> (unify '(?left ?op ?right) '((2 * a) - (16 / 4)))
((?right 16 / 4) (?op . -) (?left 2 * a))
```

If there are no assignments of values to the variables in an expression that
will make them equal, then `#f`

is returned:

```
=> (unify '(?s 1) '(2 ?s))
#f
=> (unify '(?s ?t) '(?s ?t ?t))
#f
```

If you try to unify two expressions that are the same and have no variables,
or the variables can be any value, then `unify`

returns an empty list:

```
=> (unify '(2 (a b)) '(2 (a b)))
()
=> (unify '(?x ?x) '(?x ?x))
()
```

The practical value of unification is that it’s often a short and easy way to chop up lists into smaller parts.

For example, suppose we want to check that the top-level of a list is a propositional expression:

```
(define make-recognizer
(lambda (e1)
(lambda (e2)
(if (unify e1 e2)
#t
#f
)
)
)
)
(define is-and? (make-recognizer '(?x and ?y)))
(define is-or? (make-recognizer '(?x or ?y)))
(define is-not? (make-recognizer '(not ?x)))
```

The `is-and?`

, `is-or?`

, and `is-not?`

functions are quite are short and
readable.

## Example: Binary Search Trees¶

The following is a sample Scheme implementation of a basic binary search tree. It’s provided as an example of straightforward Scheme implementation of a standard program.

```
;;; bst.scm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; An implementation of a binary search tree (BST). Nodes are lists of the
;; form (value left-tree right-tree).
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; '() is the empty tree
(define is-empty? (lambda (t) (null? t)))
;; getters
(define value (lambda (node) (first node)))
(define left (lambda (node) (second node)))
(define right (lambda (node) (third node)))
;; insert value x into tree t
(define insert
(lambda (x t)
(if (is-empty? t)
(list x '() '())
(let ((V (value t))
(L (left t))
(R (right t))
)
(cond
((is-empty? t)
(list x '() '()))
((= x V) ;; x already in the tree, so do nothing
t)
((< x V)
(list V (insert x L) R))
(else
(list V L (insert x R)))
)
)
)
)
)
;; convert a list of things into a tree
(define make-tree
(lambda (lst)
(if (null? lst)
'()
(insert (car lst) (make-tree (cdr lst))))))
;; return a list of the values of tree in "inorder" order, i.e. for
;; a BST the list of values will be in ascending sorted order
(define list-inorder
(lambda (t)
(cond
((is-empty? t) '())
(else (append (list-inorder (left t))
(list (value t))
(list-inorder (right t))))
)
)
)
(define tree-sort
(lambda (lst)
(list-inorder (make-tree lst))
)
)
;; Returns the depth of a tree
(define depth
(lambda (t)
(cond
((is-empty? t)
0)
(else
(+ 1 (max (depth (left t)) (depth (right t))))
)
)
)
)
;; return the max value in a tree
(define tree-max
(lambda (t)
(cond
((is-empty? t)
'error)
((is-empty? (right t))
(value t))
(else
(tree-max (right t)))
)
)
)
;; test if x is a value in tree t
(define contains
(lambda (x t)
(cond
((is-empty? t)
#f)
((= x (value t))
#t)
((< x (value t))
(contains x (left t)))
(else
(contains x (right t)))
)
)
)
```