Archive for March 2010

Sunday, March 7, 2010 View Comments

OCaml Stack and Queue

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 :

  1. module Stack = struct
  2.     type 'a t = { mutable c : 'a list }
  3.     exception Empty
  4.  
  5.     let create () = { c = [] }
  6.     let clear s = s.c <- []
  7.     let copy s = { c = s.c }
  8.     let push x s = s.c <- x :: s.c
  9.  
  10.     let pop s =
  11.       match s.c with
  12.         hd::tl -> s.c <- tl; hd
  13.       | []     -> raise Empty
  14.  
  15.     let top s =
  16.       match s.c with
  17.         hd::_ -> hd
  18.       | []     -> raise Empty
  19.  
  20.     let is_empty s = (s.c = [])
  21.     let length s = List.length s.c
  22.     let iter f s = List.iter f s.c
  23. end;;

For the Queue (FIFO), here is an elegant implementation using references on Lists:

  1. module Queue = struct
  2.   type 'a t = ('a list * 'a list) ref
  3.   exception Empty
  4.   let create () = ref ([], [])
  5.   
  6.   let add x queue =
  7.     let front, back = !queue in
  8.         queue := (x::front, back)
  9.   
  10.   let rec take queue =
  11.     match !queue with
  12.         (front, x :: back) ->
  13.                     queue := (front, back);
  14.                     x
  15.         | ([], []) ->    
  16.                     raise Empty
  17.         | (front, []) ->
  18.                     queue := ([], List.rev front);
  19.                     take queue
  20. 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.

Posted in , |

Swedish Greys - a WordPress theme from Nordic Themepark. Converted by LiteThemes.com.