On Sun, Mar 11, 2012 at 8:38 PM, E R <span dir="ltr"><<a href="mailto:pc88mxer@gmail.com" target="_blank">pc88mxer@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
A pure function can allocate and modify memory as long as a) it never<br>
returns a reference to the memory or b) it never again modifies the<br>
memory once it returns (i.e. it returns an immutable object).<br></blockquote></div><div><br>That's a reasonable first approximation to the problem, yes. It gets a bit more complicated due to laziness (what if the mutation gets delayed until some later part of the output is examined?)<br>
<br></div><div class="im"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
So, again, what is the Haskell philosophy towards using mutable data<br>
structures in pure functions? Is it:<br>
<br>
1. leave it to the compiler to find these kinds of opportunities<br>
2. just use the immutable data structures - after all they are just as<br>
good (at least asymptotically)<br>
3. you don't want to use mutable data structures because of _____<br>
4. it does happen, and some examples are ______<br></blockquote></div><div><br>There are two ways in which Haskell encourages the use of mutable data structures in a pure way.<br><br>The first is in the inherent mutation caused by laziness. For example:<br>
<br>type Positive = Integer<br><br>-- trie of binary representation of positive number<br>-- [1] -> tOne<br>-- x ++ [0] -> lookup x . tEven<br>-- x ++ [1] -> lookup x . tOdd<br>data Trie a = Trie {<br> tOne :: a,<br>
tEven :: NatTrie a,<br>
tOdd :: NatTrie a<br>
}<br><br>lookupTrie :: Trie a -> Positive -> a<br>lookupTrie t 1 = tOne t<br>lookupTrie t n<br> | even n = lookupTrie (tEven t) (n `div` 2)<br> | otherwise = lookupTrie (tOdd t) (n `div` 2) -- div drops remainder<br>
<br>makeTrie :: (Positive -> a) -> Trie a<br>
makeTrie f = Trie (f 1) e o where<br> e = makeTrie $ \n -> f (2*n)<br> o = makeTrie $ \n -> f (2*n + 1)<br><br>memoize :: (Positive -> a) -> (Positive -> a)<br>memoize = lookupTrie . makeTrie<br><br>
collatz_rec :: (Positive -> Integer) -> Positive -> Integer<br>collatz_rec f 1 = 0<br>collatz_rec f n<br> | even n = 1 + f (n `div` 2)<br> | otherwise = 1 + f (3*n + 1)<br><br>collatz = memoize (collatz_rec collatz)<br>
<br>In this case, makeTrie creates a thunk, and it's only evaluated where requested by lookupTrie. You can call collatz at many different values and later calls will be much faster, as the mutation caused by lazy evaluation 'remembers' the values.<br>
<br>The second is by explicitly documenting that you are using a temporarily mutable structure, which is the ST monad:<br><br>instance Monad (ST s)<br>newSTRef :: a -> ST s (STRef s a)<br>readSTRef :: STRef s a -> ST s a<br>
writeSTRef :: STRef s a -> a -> ST s ()<br>-- and similar interface for mutable STArrays<br><br>runST :: (forall s. ST s a) -> a -- note higher rank type<br>
<br>A computation in the ST monad is an impure computation that can modify memory, but only memory allocated within that same computation. <br><br>The higher rank type in runST makes it safe to do so--references from one ST computation cannot escape to any other ST computation. So even though internally some pure value might rely on an impure computation, it's safe to do so in a pure context.<br>
<br>Here's a sample implementation of ST:<br><br>-- DO NOT EXPORT THESE CONSTRUCTORS<br>newtype ST s a = ST (IO a)<br>newtype STRef s a = STRef { getRef :: IORef a }<br><br>runST :: (forall s. ST s a) -> a<br>runST (ST act) = unsafePerformIO act -- Actually safe!<br>
<br>newSTRef :: a -> ST s (STRef s a)<br>newSTRef a = ST $ liftM STRef (newIORef a)<br><br>readSTRef :: STRef s a -> ST s a<br>readSTRef (STRef r) = ST $ readIORef r<br><br>writeSTRef :: STRef s a -> a -> ST s ()<br>
writeSTRef (STRef r) a = ST $ writeIORef r a<br><br>There's some usage examples at <a href="http://www.haskell.org/haskellwiki/Monad/ST" target="_blank">http://www.haskell.org/haskellwiki/Monad/ST</a><span class="HOEnZb"><font color="#888888"><br>
<br> -- ryan<br></font></span></div></div>
<br>
</div><br>