Lennart Augustsson wrote:
> > Can anyone think of an efficient method. Monads?
>
> accumArray?
>
> Whic, admittedly, is hard to implement efficiently in a purely functional way.
True.
But it could still be implemented efficiently with support from the
interpreter or compiler, right? I mean - no function can get hold of the
accumulated array while it is being built, so internally in the
implementation they can use imperative updates - it's transparent to us.
Am I not right?
Is it how it is implemented in GHC and Hugs - with type 'Array a b'
having special meaning to the system (like IO has)?
Has anyone made a generalization of accumArray, which allows users to
implement a pure function using imperative features? Once in a while
(like, for implementing accumArray), a pure function is best implemented
using some state updates. So we would need a kind of "box", that gets
some input (the input of the function), creates a state, and which
cannot "leak" that state before finishing the calculation, at which
point some part of the state is returned as output. The boxed state
should be able to expand dynamically ("malloc") and contain
non-transparent references.
One obvious use for this is efficient implementations of graph
algorithms, like "shortest path". Of course, the shortest path is a pure
function of the input graph.
This not in conflict with making "local state" updates while calculating
that pure function, I guess. To prove this absurdly true, we can just
look at how the pure function '+' is evaluated using some very
imperative features of the state in the CPU ALU ;-)
Bjarke
--
IRISA-INRIA, Campus de Beaulieu, 35042 Rennes cedex, France
Home page: http://www.irisa.fr/compose/ebert/
