<div class="gmail_quote">On Fri, Feb 27, 2009 at 6:31 PM, Brent Yorgey <span dir="ltr"><<a href="mailto:byorgey@seas.upenn.edu">byorgey@seas.upenn.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
The only disadvantage is that some things you might expect to be<br>
constants will actually get recomputed every time they are used. For<br>
example, suppose you define<br>
<br>
foo = very expensive computation involving a bunch of numbers<br>
<br>
You might think that foo will get computed just once, the first time<br>
it is needed. However, if foo ends up with a polymorphic type, like,<br>
say<br>
<br>
foo :: Num a => a<br>
<br>
then it is not actually a constant, but a function which takes a Num<br>
dictionary (i.e. a record of the Num methods) as an argument. So it<br>
will be recomputed every time it is used, since it might have<br>
different values for different types.</blockquote><div><br></div><div>Yes indeed. Beginners might want to verify this with the following little program (just assume 42 takes a very long to compute, on some alien computer this took <span class="Apple-style-span" style="font-family: -webkit-sans-serif; line-height: 19px; ">7½ million years ;-)</span></div>
<div><br></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">import Debug.Trace</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"><br>
</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">foo :: Num a => a</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">foo = trace "foo" $ 42</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"><br></span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">bar :: Int</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">bar = trace "bar" $ 42</span></div><div> </div><div>When evaluating foo (e.g in GHCi) "foo" will be printed every time, bar only once.</div>
<div><br></div><div>I guess a clever implementation would only compute foo once for each different type of a? But then of course you'll hit a runtime performance penalty every time when accessing foo since this will require a lookup... Mmm, this feels as a case where you can't determine at compile time if a function - in this case a polymorphic CAF - will need memoization or not...<br>
</div><div><br></div><div>For example (just a quick hack)</div><div><br></div><div><div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">import Data.Typeable</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">import Data.IORef</span></div><div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">import qualified Data.IntMap as M</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">import System.IO.Unsafe</span></div><div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">import Debug.Trace</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">fooCache :: IORef (M.IntMap a)</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">fooCache = unsafePerformIO $ newIORef M.empty</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"><br>
</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">foo :: (Typeable a, Num a) => a</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">foo = unsafePerformIO $ do</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> key <- typeRepKey (typeOf value)</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> atomicModifyIORef fooCache (updateCache key)</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> where</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> value = trace "foo is computed" $ 42</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> updateCache key cache = </span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> case key `M.lookup` cache of</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> Just n -> (cache, trace "foo is cached" n)</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> Nothing -> (M.insert key value cache, value)</span></div>
<div><br></div></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Now, you might wonder why this is such a big deal. The answer is: it<br>
isn't. I have the MR automatically turned off in my .ghci file, and<br>
I've never missed it. Furthermore, the monomorphism restriction will<br>
be removed in the next version of the Haskell language standard.</blockquote><div><br></div><div>Cool. But I guess the next version of the standard will take a while? :)</div><div><br></div></div>