EOPL - 1.2 - Recursively Specified Programs

The first program is easy enough:

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 count-nodes:

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 (cadr and caddr are 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.