performance of monads

Jorge Adriano
Thu, 24 Jan 2002 12:33:27 +0000

> I agree with others who mentioned that viewing monads as simply
> providing a way to sequentialize things or to program imperatively is
> the wrong way to look at them.  
Yes, Lists are the classical example.

> That said, the EFFICIENCY of monads is often poorly understood.  To
> state the obvious, just because you program something in a monad doesn't
> make it efficient.  In particular, a state monad does not guarantee that
> the state will actually be updated "in place".  The monad only hides the
> state, and creates an OPPORTUNITY for it to be updated in place.  But,
> for example, if you add an operation that returns the entire state as a
> value, then the "single-threadedness" property is in fact lost, and
> in-place update becomes as problematical as it always is.
Well... I'm having *lots* of problems here. :-)

I've felt need to use State monads in two distinct situations:
(A) Keep track of data,
- Genetic Algorithms
how many crossovers, mutations, etc
best (or average) individual fitness in each generation
some schemata evolution
- Neural Networks
Weights evolution
Error evolution

(B) Acessing state
There are some situation where you'll probably rather hide some 
implementation details in some state monad instead of passing around lots of 
- Genetic Algorithms:
Getting Rand. Numbers (instead of passing around all the StdGens you need)

And I've seen two distict aproaches. Using a State monad like one provided 
with GHC (1), or a state monad like the one defined in the paper "Moands for 
the Working Haskell Programmer" (2).

In (1), I can see how I can take advantage of the monad and make updates in 
place using referencies. But then you'll have to either:
- pass the referencies as a parameter to the functions where you use them
(needless too say that this defeats the (my) main purpose of using a state 
monad which is in case A, keep track of data with minimal signature change )

- encapsulate all the functions in the monad.
I don't really like this solution... you won't be even able to test the 
functions in the interpreter...

- using implicit referencies (?)
Haven't thought that much about this one yet

In (2), I can't really see how to make updates in place... I still didn't 
figure out how to make my own State monad and use updates in place.
What I did was 
- Define my state as some record (datatype with field labels)
- Create functions to get and update state...

This is doomed to fail!
Even if I only want to update the state (like adding values to lists of 
values or incrementing some counters), I'll have to access that same state.
So I'll have to make my own getStateField functions and updateStateField 
functions for every single field.
Using datatypes with field labels makes it easy to define functions to get 
State fields (you get the would state then use the projection function)... 
but to update some field state it gets more complicated, if you got 6 
counters, you'll have to write similar code 6 times...
Damn, I seem to be waisting more time and writing more lines of code than if 
I was doing it in Pascal!! All just to keep track of some data, it is not 
even really 'part of the algorithm', I just want to evaluate how it is 
Efficiency wise it seems pretty bad, no updates in place, and I'm expecting 
lots of stack overflows unless I take special care dealing with laziness.

My problem with this is that I'm trying to do something trivial here..., 
forget about (B) (accessing state), I just want to keep track of data, any 
newbie can do that in the imperative world, and it seems like some pretty 
advanced stuff in here!!
Programmers need to do this all the time, there should be some simple, well 
documented, way to do it. I don't want to be a monads expert to be able to do 
this kind of thing... (and I'm the kind of guy that wants to, eventually, 
become an monad expert... just not now... imagine how some other guy that has 
no interest in monads feels when he has the same problem.)

IMO (and maybe I'm wrong... this is just the way I feel right now) either we 
are missing some simple aproach here, or at least we do not have at all the 
adequate documentation about it, at all.

Another state issue, sometimes I have some values that I want to keep 
constant through the whole algorithm.
(some very simple NNs for instance)
- learning rate
- activation function 
- maximum number of steps
- minimum error required

So I'll just declare them as 'constants'. But what if I decide I want the 
user to be able to chose? Now I got two options:
- pass them around as values to all the functions - And signatures get HUGE
- just pass them to a higher level function that will encapsulate the 
functions that use them... which is ugly and complicates everything because 
you can't test the lower level functions in the interpreter. 

Am I missing something here or is this really the best you can do?

> This is an issue that I and my student (Chih-Ping Chen) studied a few
> years ago, culminating in his PhD thesis and the paper:
>   Chih-Ping Chen and Paul Hudak, "Rolling Your Own Mutable ADT --
>   A Connection between Linear Types and Monads", Proceedings of 24th
>   ACM Symposium on Principles of Programming Languages, ACM Press,
>   1997, pp. 54-66.

Interesting got to check it out... my main problem is that *I don't have the 
time* right now... sometimes you just want to get the job done.