Appendix A (Crash Course in F#) exercises from the book Programming Language Concepts by Peter Sestoft

AppendixA.fs

module AppendixA

// Programming Language Concepts by Peter Sestoft

// $ fsharpi
// > #load "AppendixA.fs";;
// > open AppendixA;;
// > let t = Br (1, Br (2, Lf, Lf), Br (3, Lf, Lf));;

// Exercise A.1
let max2 (x: int, y: int): int = if x < y then y else x

let max3 (x: int, y: int, z: int) = 
    if x > y && x > z then x
    else
        if y > x && y > z then y
        else z

let rec isPositive xs =
    match xs with
    | [] -> true
    | x :: rest -> if x > 0 then true else false && isPositive rest

let rec isSorted xs = 
    match xs with
    | [] -> true
    | x :: [] -> true
    | x :: y :: rest -> if x < y then true else false && isSorted (y :: rest)

type 'a tree =
    | Lf 
    | Br of 'a * 'a tree * 'a tree
let rec count ts =
    match ts with
    | Lf -> 0
    | Br (_, l, r) -> 1 + count l + count r

let rec depth ts =
    match ts with
    | Lf -> 0
    | Br (_, l, r) -> 1 + max2 (depth l, depth r)

// Exercise A.2
let rec linear (n: int): int tree =
    match n with
    | 0 -> Lf
    | n -> Br (n, linear 0, linear (n-1))

// Exercise A.3
let rec preorder xs = 
    match xs with 
    | Lf -> []
    | Br (x, l, r) -> x :: preorder l @ preorder r

let preorder' xs =
    let rec preo xs acc =
        match xs with
        | Lf -> acc
        | Br (x, l, r) -> x :: preo l (preo r acc)
    preo xs []

let rec inorder xs =
    match xs with
    | Lf -> []
    | Br (x, l, r) -> inorder l @ [x] @ inorder r

let inorder' xs =
    let rec ino xs acc =
        match xs with
        | Lf -> acc
        | Br (x, l, r) -> ino l (x :: ino r acc)
    ino xs []

let rec postorder xs =
    match xs with
    | Lf -> []
    | Br (x, l ,r) -> postorder l @ postorder r @ [x]

let postorder' xs =
    let rec posto xs acc =
        match xs with
        | Lf -> acc
        | Br (x, l, r) -> posto l (posto r (x :: acc))
    posto xs []