This is a quick post to show how easy (and beautiful) it is to implement a simple (not the best though) and elegant FIFOs and LIFOs in OCaml.
For the Stack (LIFO – Last In First Out), the source code is available in the core language in lib/stack.ml, and it uses Lists to save elements inside the Stack, the implementation is so easy :
- module Stack = struct
- type 'a t = { mutable c : 'a list }
- exception Empty
- let create () = { c = [] }
- let clear s = s.c <- []
- let copy s = { c = s.c }
- let push x s = s.c <- x :: s.c
- let pop s =
- match s.c with
- hd::tl -> s.c <- tl; hd
- | [] -> raise Empty
- let top s =
- match s.c with
- hd::_ -> hd
- | [] -> raise Empty
- let is_empty s = (s.c = [])
- let length s = List.length s.c
- let iter f s = List.iter f s.c
- end;;
For the Queue (FIFO), here is an elegant implementation using references on Lists:
- module Queue = struct
- type 'a t = ('a list * 'a list) ref
- exception Empty
- let create () = ref ([], [])
- let add x queue =
- let front, back = !queue in
- queue := (x::front, back)
- let rec take queue =
- match !queue with
- (front, x :: back) ->
- queue := (front, back);
- x
- | ([], []) ->
- raise Empty
- | (front, []) ->
- queue := ([], List.rev front);
- take queue
- end;;
The Queue is composed of 2 Lists holding the front elements (used for adding new elements to the Queue) and a back list holding elements when we call take (or dequeue).
The add function is simple, it just take an elements and put it at the beginning of the front list queue := (x::front, back)
The take function is the one that does all the work, it checks if the Queue is not empty (an empty queue is a queue that both front and back lists are empty), then it checks if the back list has at least one element, if this is the case, the element is deleted from the queue and then returned.
Otherwise the back list is empty, so we take elements from the front list (the one used to store elements when we call add), reverse them, and store them in the back list, then the function calls itself recursively to extract the new available elements.
And in case you didn’t notice, both the Stack and Queue are generics by nature, they accept any type for their elements.
