EOPL - Chapter 2, Exercise 2.5

Chapter 2 is about data abstraction. Section 2.1 describes the concepts of interface, representation and implementation, and how a single interface may be implemented by different representations. Not much code there. Section 2.2 presents the constructions define-datatype and cases, to define and pattern-match over variant data types (or disjoint unions, or sum types, choose your preferred terminology). That is roughly equivalent to facilities already present in F#, so there's not much new here.

Exercise 2.5 is a simple pattern-matching exercise to work with the definition of a binary tree data type, expressed in F# as

type BinTree = Leaf of int | Interior of string * BinTree * BinTree

Then we can define max-interior using pattern guards, which aren't available in the Scheme cases construct:

let max_interior bt = 
    let rec maxint t = 
        match t with
          Leaf _ -> failwith "Shouldn't get here"
        | Interior (tag, Leaf l1, Leaf l2) -> (tag, l1 + l2)
        | Interior (tag, Leaf l1, t2) -> 
            let tg, s = maxint t2 in 
            if s > s + l1 then (tg, s) else (tag, s+l1)
        | Interior (tag, t1, Leaf l2) -> 
            let tg, s = maxint t1 in 
            if s > s + l2 then (tg, s) else (tag, s+l2)
        | Interior (tag, t1, t2) -> 
            let tg1, s1 = maxint t1 in
            let tg2, s2 = maxint t2 in
            if s1 > s2 then 
                if s1 > s1 + s2 then (tg1, s1) else (tag, s1+s2)
            else
                if s2 > s1 + s2 then (tg2, s2) else (tag, s1+s2) in
    fst (maxint bt)

But this is a case where it's actually shorter to just use a single pattern match and a conditional, instead of pattern guards:

let max_interior bt = 
    let rec maxint t = 
        match t with
          Leaf i -> (None, i)
        | Interior (tag, t1, t2) -> 
            let tg1, s1 = maxint t1 in
            let tg2, s2 = maxint t2 in
            if tg1 = None && tg2 = None then
                (Some tag, s1 + s2)
            elif s1 > s2 || tg2 = None then
                if s1 > s1+s2 then (tg1, s1) 
                else (Some tag, s1+s2)
            else
                if s2 > s1+s2 then (tg2, s2) 
                else (Some tag, s1+s2) in
    match bt with
      Leaf _ -> failwith "Shouldn't happen"
    | t -> maxint t |> fst |> Option.get

Even so, the function is somewhat big, and could be broken in two, but we'll let it as it is.