27 Nov'09
Custom Stack

This post describes the F# implementation of the custom stack from Chris Okasaki’s “Purely functional data structures”.

namespace PurelyFunctionalDataStructures

module CustomStack =

  type t<'a> =
    | Nil
    | Cons of ('a * t<'a>)

  let empty = Nil

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

  let cons x cs = Cons(x, cs)

  let singleton x = cons x empty

  let head = function
    | Nil -> raise Empty
    | Cons (hd, tl) -> hd

  let tail = function
    | Nil -> raise Empty
    | Cons (hd, tl) -> tl

  let rec append x y =
    match x with
    | Nil -> y
    | Cons (hd, tl) -> Cons (hd, append tl y)

  let rec set xs i x =
    match xs, i with
    | Nil, _ -> raise Subscript
    | Cons (hd, tl), 0 -> Cons(x, tl)
    | Cons(hd, tl), n -> Cons(hd, set tl (i-1) x)

Comments are closed.