Hello Daniel, Thursday, December 11, 2008, 11:49:40 PM, you wrote:
sorry fo r noise, it seems that i know ghc worse than you > Am Donnerstag, 11. Dezember 2008 21:11 schrieb Bulat Ziganshin: >> Hello Daniel, >> >> Thursday, December 11, 2008, 11:09:46 PM, you wrote: >> >> you is almost right. but ghc don't share results of function calls >> despite their type. it just assumes that value of any type may use a >> lot of memory even if this type is trivial :) > I may misunderstand you here. But if you give a type signature specifying a > nice known type, I'm pretty sure ghc _does_ sharing (tried with Int -> Int and Integer ->> Integer, g 200 instantaneous), at least with -O2. Without > sharing, it would require 2^(n+1) - 1 calls to evaluate g n, that wouldn't be > nearly as fast. Without the type signature, it must assume the worst, so it > doesn't share. >> >> example when automatic sharing is very bad idea is: >> >> main = print (sum[1..10^10] + sum[1..10^10]) > Depends on what is shared. Sharing the list would be a very bad idea, sharing > sum [1 .. 10^10] would probably be a good idea. >> >> > Am Donnerstag, 11. Dezember 2008 16:18 schrieb Mattias Bengtsson: >> >> The program below computes (f 27) almost instantly but if i replace the >> >> definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it >> >> takes around 12s to terminate. I realize this is because the original >> >> version caches results and only has to calculate, for example, (f 25) >> >> once instead of (i guess) four times. >> >> There is probably a good reason why this isn't caught by the compiler. >> >> But I'm interested in why. Anyone care to explain? >> >> >> >> > main = print (f 27) >> >> > >> >> > f 0 = 1 >> >> > f n = let f' = f (n-1) >> >> > in f' * f' >> >> >> >> (compiled with ghc --make -O2) >> >> >> >> Mattias >> > >> > Not an expert, so I may be wrong. >> > The way you wrote your function, you made it clear to the compiler that >> > you want sharing, so it shares. >> > With >> > >> > g 0 = 1 >> > g n = g (n-1)*g (n-1) >> > >> > it doesn't, because the type of g is Num t => t -> t, and you might call >> > it with whatever weird Num type, for which sharing might be a bad idea >> > (okay, for this specific function I don't see how I would define a Num >> > type where sharing would be bad). >> > If you give g a signature like >> >> g :: Int ->> Int, >> >> > the compiler knows that sharing is a good idea and does it (cool thing >> > aside: with >> > module Main where >> > >> > f 0 = 1 >> > f n = let a = f (n-1) in a*a >> > >> > main = do >> > print (f 27) >> > print (g 30) >> > >> > g 0 = 1 >> > g n = g (n-1)*g (n-1) >> > >> > main still runs instantaneously, but g n takes exponential time at the >> > ghci prompt. That's because in main the argument of g is defaulted to >> > Integer, so it's shared.) >> > _______________________________________________ >> > Haskell-Cafe mailing list >> > [email protected] >> > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Best regards, Bulat mailto:[email protected] _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
