Saturday, March 03, 2007

Monads in C pt. III

OK, the last C monad example:


typedef struct {
char *string;
int value;
} WriterInt;

WriterInt returnWriter(int i)
{
WriterInt r;
r.string = "";
r.value = i;
return r;
}

WriterInt bind(WriterInt (*f)(int),WriterInt x)
{
WriterInt y = f(x.value);
WriterInt z;
z.value = y.value;
int len = strlen(x.string)+strlen(y.string);
z.string = malloc(len+1);
strcpy(z.string,x.string);
strcat(z.string,y.string);
return z;
}

WriterInt print(int i)
{
WriterInt x;
x.string = malloc(32);
x.value = sprintf(x.string,"%d\n",i);
return x;
}

WriterInt printplus_bad(int i)
{
WriterInt x = print(i);
return print(x.value); /* cheating! */
}

WriterInt printplus(int i)
{
WriterInt x = print(i);
return bind(print,x);
}


This time, instead of printing, we build up a string as a side effect. printplus() is implemented exactly as before, without knowledge of how to handle side effects, and yet it correctly handles strings returned as a side effect and concatenates them together. The magic is bind() which allows a function expecting an int input to be applied to a WriterInt.

I'm hoping that programmers of languages such as C can now begin to see the pattern shared by these examples.

Anyway, this is all just stalling for time while I try to get my quantum computation code working.

4 comments:

  1. If you were doing this in C++, you could just accomplish this by labeling a variable as private, right? Then you wouldn't need to wrap and unwrap it all the time.

    I keep looking at examples like this of monads, and I can't figure out what the excitement is.

    ReplyDelete
  2. Steven,

    Not sure what you're trying to achieve using a private member.

    My goal here isn't to do anything useful but to simply translate one of the simplest monads into C++ to make the way it works more apparent to people with a C++ background. It's not something that anyone would really write in C++, it's just a baby example in the hope that it illustrates the pattern. A more sophisticated monad like the list monad allows you to do things like logic programming in Haskell, something that is much more difficult to implement in C++ and really leverages the usefulness of monads. But it helps to understand these simple examples first.

    ReplyDelete
  3. Perhaps I misunderstood, but it looks like the wrapping and unwrapping is being done to hide data in these examples.

    I guess I need to see a more complex example where the pattern makes something easier/clearer to understand why I'd want to use it.

    I'm not trying to be difficult, I'm just slow (at least when it comes to monads). :)

    ReplyDelete
  4. Steven,

    In pure functional programming languages you aren't allowed to cause side effects. The only way a function can 'interact' with the outside world is to return something. So if you have a function that needs to return a number, but has a certain side effect, the only way to do this is to return the number and return some data 'containing' the side effect. But that's a pain in the ass - you have to write all of your code to return multiple values, and you have to write plumbing code to pass these side-effect containing values around. What monads can do is give a uniform API to side-effect containing data so you can just concentrate on the number that you want to return, and have the side-effect carried along automatically in the background. What's neat about monads is the same API can be used for many different problems, not just handling side-effects.

    So half the time when dealing with monads we're solving a problem that we've caused in the first place by using a pure functional language. (But sometimes it's worth using a pure functional language because of other benefits.) The other half of the time we're using monads because they provide facilities that are very hard to implement otherwise - such as logic programming or continuation passing style. I've not given C++ examples of the latter because it would be way too hard. So I've only given examples of things that you can easily implement already in C++.

    If you ever get a chance, check out the list monad in Haskell. It's beautifully simple, and yet it takes a considerable amount of work to implement the same thing in C++.

    ReplyDelete