On Fri, Feb 27, 2009 at 6:31 PM, Brent Yorgey <byorgey@seas.upenn.edu> wrote:

The only disadvantage is that some things you might expect to be
constants will actually get recomputed every time they are used. For
example, suppose you define

foo = very expensive computation involving a bunch of numbers

You might think that foo will get computed just once, the first time
it is needed. However, if foo ends up with a polymorphic type, like,
say

foo :: Num a => a

then it is not actually a constant, but a function which takes a Num
dictionary (i.e. a record of the Num methods) as an argument. So it
will be recomputed every time it is used, since it might have
different values for different types.

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 7½ million years ;-)

import Debug.Trace

foo :: Num a => a

foo = trace "foo" $ 42

bar :: Int

bar = trace "bar" $ 42

When evaluating foo (e.g in GHCi) "foo" will be printed every time, bar only once.

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...

For example (just a quick hack)

import Data.Typeable

import Data.IORef

import qualified Data.IntMap as M

import System.IO.Unsafe

import Debug.Trace

fooCache :: IORef (M.IntMap a)

fooCache = unsafePerformIO $ newIORef M.empty

foo :: (Typeable a, Num a) => a

foo = unsafePerformIO $ do

key <- typeRepKey (typeOf value)

atomicModifyIORef fooCache (updateCache key)

where

value = trace "foo is computed" $ 42

updateCache key cache =

case key `M.lookup` cache of

Just n -> (cache, trace "foo is cached" n)

Nothing -> (M.insert key value cache, value)

Now, you might wonder why this is such a big deal. The answer is: it
isn't. I have the MR automatically turned off in my .ghci file, and
I've never missed it. Furthermore, the monomorphism restriction will
be removed in the next version of the Haskell language standard.

Cool. But I guess the next version of the standard will take a while? :)