Skip to content

Instantly share code, notes, and snippets.

@heyrutvik
Last active August 28, 2018 07:14
Show Gist options
  • Save heyrutvik/12bf34e6cfa040eb71a514140012ef25 to your computer and use it in GitHub Desktop.
Save heyrutvik/12bf34e6cfa040eb71a514140012ef25 to your computer and use it in GitHub Desktop.
Appendix A (Crash Course in F#) exercises from the book Programming Language Concepts by Peter Sestoft
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 []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment