Code Samples

Breadth-first Tree Traversal

This F# function implements the general purpose Breadth-first Tree traversal algorithm. Note that we are working with trees where the number of children at each point can vary.

type ListTree<'a> = Node of 'a * (ListTree<'a> list)

let bfIter f ltr =
  let queueTree = Queue<ListTree<'a>>()
  queueTree.Enqueue ltr
  while(queueTree.Count <> 0) do
    let temp = queueTree.Dequeue()
    match temp with
    | Node (i,lst) -> List.iter(queueTree.Enqueue) lst; f i

type Cell = { data : int; next : RList}
and RList = Cell option ref
let reverse (lst: RList) =
  let rec helper(lst: RList, revlst:RList) =
    match !lst with
    | None -> revlst
    | Some {data = d; next = tail} ->
      let newCell = Some {data = d; next = ref(!revlst)} in revlst := newCell; helper(tail, revlst)
  helper(lst, ref None)
  

Low-level Pointer Manipulation

Here, I've implemented an F# function reverse which implements in-place reverse of a list by changing the pointers. Notice that the type definition is mutually recursive. Each type mentions the other one.

Mergesort

Here is the implementation of the mergesort algorithm in F# which is a recursive algorithm for sorting lists that runs in time O(nlogn). The idea is as follows: the given list l is split into two equal (if the length of l is odd then one of the “halves” is one item longer than the other) lists l1 and l2. These lists are sorted recursively and then the results are merged back to give a single sorted list.

let rec split l =
  match l with
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x::y::ys -> let (A,B) = split ys
                (x::A, y::B)

let rec merge twolists =
  match twolists with
  | (xs, []) -> xs
  | ([], ys) -> ys
  | (x::xs, y::ys) -> if x < y then x :: merge (xs, y::ys) else y :: merge (x::xs, ys)

let rec mergesort l =
  match l with
  | [] -> []
  | (a::[]) -> a::[] (* Without this you will go into an infinite loop. *)
  | n::ns -> let (x, y) = split l
             merge (mergesort x, mergesort y)