Nicollet.Net

Imperative Elegance

Imperative programming has some elegant aspects to it. When representing a sequence of operations, as often happens for instance when drawing vectorial elements one by one, the “recipe” feel of imperative code can appear better than manually folding a concatenation operator of a list of operations.

Of course, achieving the same elegance without mutable state is possible. The basic idea is to use a value to represent the state, and create mutator functions which represent the state changes, and which return a new state based on an old one. For instance, in the example below, the state is represented by type op, and all mutator functions have a noticeable -> mutator type (instead of the -> unit type in true imperative functions).

module Graphics :
sig
  type op
  type mutator = op -> op
  val apply       : op -> unit
  val nil         : op
  val draw_rect   : vect -> vect  -> mutator
  val draw_circle : vect -> int   -> mutator
  val draw_line   : vect -> vect  -> mutator
  val draw_pixel  : vect          -> mutator
  val draw        : vect -> op    -> mutator
end

Keeping the state as the last argument of every mutator allows a fairly standard set of manipulations.

Mutator lists

The first possibility is to store all mutators in a list, and to concatenate them together with a folding operation:

let small_cross =
  List.fold_left (fun x f -> f x) nil
  [
    draw_line (-1,-1) ( 1, 1) ;
    draw_line (-1, 1) ( 1,-1)
  ] 

let four_crosses =
  List.fold_left (fun x f -> f x) nil
  [
    draw ( 2, 0) small_cross ;
    draw (-2, 0) small_cross ;
    draw ( 0, 2) small_cross ;
    draw ( 0,-2) small_cross
  ]

Using this approach, one comes closer to the imperative style of specification, while keeping the ability to manipulate the objects freely (for instance, in this case, to reuse the small cross drawing four times as part of a larger one).

Piping operator

A commonly found improvement in functional language is a piping operator, which replaces the (fun x f -> f x) of the above folding operations, and which can then be used in infix position to separate the statements. Explicitly unrolling the folding operation yields:

let (|>) x f = f x  

let small_cross =
  nil
  |> draw_line (-1,-1) ( 1, 1)
  |> draw_line (-1, 1) ( 1,-1) 

let four_crosses =
  nil
  |> draw ( 2, 0) small_cross
  |> draw (-2, 0) small_cross
  |> draw ( 0, 2) small_cross
  |> draw ( 0,-2) small_cross

The piping operator can be found in languages such as F#. Objective Caml does not provide it by default, but it can be rewritten as above.

Control structures

Using the piping operator, one can implement the classic imperative control structures in a purely functional way. The loop will keep the state as an accumulator, and the body of the loop will be a mutator:

let rec _while cond iter init =
  if cond init
  then _while cond iter (iter init)
  else init 

let rec _for s n iter init =
  if s > n
  then init
  else _for (s+1) n iter (iter init s) 

let drawing =
  nil
  |> draw_rectangle (0,0) (10,10)
  |> _for 0 10
     (fun i -> draw_line (0,i) (10-i,0))

As a consequence, every imperative construct can easily be converted to a purely functional approach using mutators and explicit state representation. Even better, the fact that state is explicit allows simple referencing of a previously manipulated state, and makes implementing undo functionality or simply reusing operations much easier.