`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:

Post a Comment