Re: [Haskell-cafe] A tale of Project Euler

On Nov 29, 2007 9:10 PM, Andrew Coppin wrote:

Sebastian Sylvan wrote:

...

On Nov 29, 2007 6:43 PM, Andrew Coppin wrote:

...

I don't understand the ST monad.

There's not a whole lot to understand if you just want to use it (though it's all very cool from a theoretical standpoint too).

From what I can tell, it's not definable without using strange language extensions. (I don't really like using things where it's unclear why it works.)

Yeah the magic happens in the type for runST: runST :: (forall s. ST s a) -> a That "s" variable there is created "fresh" for the first argument (and is *not* in scope for the second argument to the function). Notice that all the ST stuff (ST actions, STUArrays etc.) also carry along that "s" type variable? That's intentional. Because all the mutable stuff carries the "s", which is not in scope in the return type, it's impossible to accidentally leak side effects out of runST (try running runST on an ST action thar returns an STRef or STUArray or something, and you'll get a type error). That's pretty much all there is to it. A cool type for runST that guarantees that side effects won't leak.

How do you avoid accidentally recomputing the list multiple times?

What do you mean? It's exactly the same as your original program but with ST instead of IO? Why would it get accidentally recomputed in this scenario and not before?

I don't see Data.Array.Base documented anywhere. (How did you know it exists?)

Hmm.. I don't remember. But now you know too! :-) I think it may be a secret GHC library that you're not supposed to know about... -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862