performance of monads
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
(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.