Monday, February 19, 2007

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.

No comments: