04 Functional Stacks

The stack data structure is like a stack of cafeteria trays. Items get pushed onto the top, and off.

module MyStack = struct
	type 'a stack =
		| Empty
		| Entry of 'a * 'a stack

	let empty = Empty
	
	let push x s = Entry (x, s)
	
	let peek = function
		| Empty -> failwith "Empty"
		| Entry (x, _) -> x
		
	let pop = function
		| Empty -> failwith "Empty"
		| Entry (_, x) -> x
end

module MyStack :
  sig
    type 'a stack = Empty | Entry of 'a * 'a stack
    val empty : 'a stack
    val push : 'a -> 'a stack -> 'a stack
    val peek : 'a stack -> 'a
    val pop : 'a stack -> 'a stack
  end

Let's talk about this

• empty is a variable representing the empty stack.
• To push an item on the stack, we add the stack to the bottom of an Entry
• peek gives us a value, while pop returns an item.

This is essentially the same as a list.

module ListStack = struct
	type 'a stack = 'a list
	
	let empty = []
	
	let push x s = x :: s
	
	let peek = function
		| [] -> failwith "Empty"
		| x :: _ -> x
	
	let pop = function
		| [] -> failwith "Empty"
		| _ :: s -> s
	
end

module ListStack :
  sig
    type 'a stack = 'a list
    val empty : 'a list
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

Now we have the same thing, but implemented with lists!

let s = ListStack.empty

val s : 'a list = []

let s' = ListStack.push 1 s

val s' : int list = [1]

ListStack.peek s'

- : int = 1

s'

- : int list = [1]

ListStack.pop s'

- : int list = []

Let's compare Java and OCaml:

Stack s = new Stack();
s.push(1);

let s = MyStack.empty;;
let s' = MyStack.push 1 s;;

Note here that when we create the stack, we don't use the new keyword. Also, we don't write s.push, we put s as a parameter. What's interesting, is the Java Compiler will actually change s.push(1) to push(1, s), or something similar, so under the hood, it's not that different.