[Haskell-cafe] Fun with the ST monad

[Andrew Coppin]

On 25/02/2011 02:16 AM, wren ng thornton wrote:

> Given only this specification, the problem is overconstrained, which is
> why you get too much strictness. That is, your types are too general to
> allow you to do what you want (e.g., they allow the first Word16 to
> depend on the last Word8).

Hmm, true I suppose.

> What is it that transform is supposed to do?

Data compression. The input list is raw data, the output list is 
compressed data.

Of course, I *could* just sink the whole thing into the IO monad. But 
that seems a pitty...

> As for figuring out how to do it, first consider the following:

Ow, my head! >_<

> You can't do that in ST, since allowing this would mean that multiple
> evaluations of the (ST s a) embedded in the result could return
> different answers and communicate with one another[1].

Yeah, that's the essential conclusion I came to.

> But you're probably better off using State[2] instead of ST.

I'm using ST because I want mutable arrays. It's more efficient.

> Or
> converting the whole thing to an iteratee-style computation which is
> more explicit about the type of stream processing involved and thus what
> kinds of laziness are possible.

I've heard much about this "iteratee" things, but I've never looked into 
what the hell it actually is.

Today I had a look at TMR #16, which is an explanation which I can just 
about follow. It seems that it's actually a kind of fold - not unlike 
the "streams" of the stream-fusion library (which is something like what 
I thought I might end up needing). It seems to handle *input* very 
nicely, but I don't see much in the way of handling *output* well. (Then 
again, iteratee is just too complex to really comprehend properly.)

The other thing that suggests itself to me: Maybe what I want is not so 
much an ST *monad*, but rather an ST *arrow*. (Isn't one of the 
properties of arrows that the _output_ as well as the input is 
parameterised?)