let rec e n x =
if n = 0 then 1 else x * (e (n-1) x)
But the second one uses the definition of bintrees from section 1.1. I should have noted there that some differences are caused because of static vs. dynamic typing. Scheme is "dynamically typed" (that's the usual term, anyway -- maybe it should be called "dynamically checked"), so it can define a bintree data type that may be a number or a list. Parts of the program that use this type must check if it received a number or a list, and act accordingly. But F# is statically typed, so we can't do it like this, because a number is a member of a type and a list is from another one. The way to solve this in F# is by creating a disjoint union data type that includes numbers and lists; well, as we know the second possibility has only 3 components, we'll do this as a tuple. So we get
type Bintree = Leaf of int | Node of string * Bintree * Bintree
With this definition, and some pattern matching, it's easy to write
let rec count_nodes s =
match s with
Leaf _ -> 1
| Node (_, bt1, bt2) -> (count_nodes bt1) + (count_nodes bt2)
The program still follows the same structure as the proof given earlier for the property.
It's interesting to note that we have to define a type, where in Scheme it wouldn't need any definition. Of course, the Scheme program is harder to understand because of the use of implicit list structure (
caddrare used to decompose the list). But in F# we have to define a representation in terms of a tagged union type, and to hide the representation we would have to define an interface with an opaque type. A bit more of work but we get static checking and better runtime performance.