Monday, March 20, 2006


Monads in C

I'm trying really hard to get my head around monads, and I thought it might be a good idea to try and implement the array monad in C to solve a simple problem: initialise an array of 5 elements (say 5 down to 1), and calculate the sum. The C code for doing this directly is trivial:
void init( int a[ 5 ] )
  int i;
  for( i = 0 ; i < 5 ; ++i )
    a[ i ] = 5 - i;

int sum( int a[ 5 ] )
  int i, s;
  for( i = s = 0 ; i < 5 ; ++i )
    s += a[ i ];
  return s;
After two hours and over 200 lines of code I've now got a monad implementation that doesn't yet sum the array entries, and leaks memory like a sieve. You can find the C code here - any feedback is most welcome!

Updated: 21/March
Now have a working monad implementation that does sum the array entries! It is only 439 lines of code, and still leaks memory like a sieve. Actually, there is a full implementation of not one, but two monads in this code! Both the array transformer and array reader monads are implemented, along with the coercion operator for mapping a reader into a transformer. I apologise for using #include <stdio.h> instead of writing a monad for I/O, but I was keen to get this code out and didn't have time to write another 2000 lines of C code for the pure implementation. Otherwise the implementation is purely functional, with the entire computation being performed by

printf( "The sum is: %d\n", xblock( 0, xbind( build( ), summer( ) ) ) );
The function build() creates an array transformer monad that initialises the array, and the function summer() creates the object that performs the actual summation. These are combined using the binding xbind(), and finally the computation is performed using xblock(). Note that the actual array is not created until control is passed to xblock(), so one interpretation of the array transformer monad is that it is the intention to perform an action at a later stage, when xblock() is invoked.

There is also a cutdown implementation using just the array transformer monad. It is 'just' 347 lines of code ;-)

Updated: 22/March
Here is a Python implementation of the array transformer monad. The code is much simpler, given that python supports closures. All of the cruft that was necessary in the C implementation just disappears. The function summer() could be rewritten to use lambda functions (left as an exercise for the reader!).

Links to this post:

Create a Link

<< Home

This page is powered by Blogger. Isn't yours?