Purely Functional Data Structures: An F# Stack

One of the beauties of F# is that it doesn't force you to follow one programming technique. If you want to code with objects in an imperative style, you're free to. If you want to write strict functional code, you're free to do that as well.

I'm quite familiar with imperative modes of programming so I've been bending my mind in the functional direction by reading Purely Functional Data Structures. The book's examples are written in ML (with a Haskell appendix), so I'm re-writing them in F#. I'll post them here as I do in the hopes that it will help other .NET programmers bend their mind as well.

Here is the code for a Stack implementation from Chapter 2.1:

#light

exception Empty
exception Subscript

type 'a Stack = Nil | Cons of 'a * 'a Stack

let empty = Nil

let isEmpty = function
    | Nil -> true
    | _ -> false

let head = function
    | Nil -> raise Empty
    | Cons(x, s) -> x
    
let tail = function
    | Nil -> raise Empty
    | Cons(x, s) -> s

let rec (-||-) xs ys =
    if isEmpty xs then
        ys
    else
        Cons(head xs, tail xs -||- ys)

let rec update = function
    | Nil, i, y -> raise Subscript
    | xs, 0, y -> Cons(y, tail(xs))
    | xs, i, y -> Cons(head(xs), update(tail(xs), i-1, y))