[Haskell-cafe] A tale of Project Euler

[Sebastian Sylvan]

On Nov 29, 2007 9:10 PM, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
> Sebastian Sylvan wrote:
> > On Nov 29, 2007 6:43 PM, Andrew Coppin <andrewcoppin at btinternet.com> 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