4 ms·

Memoization isn't a new thing. It's available in Haskell as a first class citizen. This benchmark explicitly targets popular languages, and it happens to inclu

• harpocrates 8y ago
  > It's available in Haskell as a first class citizen. Not really. Haskell's laziness makes it easier to write functions that are memoized, but it does not automagically memoize functions. And how could it without incurring a non-trivial runtime space/time cost? Haskell's purity is what makes it easier to write libraries that facilitate building memoized versions of functions in a transparent way (and that are obviously correct). For instance, I usually reach for [data-memocombinators][0], which happens to have a fibonacci example at the top of the docs: import qualified Data.MemoCombinators as Memo fib = Memo.integral fib' where fib' 0 = 0 fib' 1 = 1 fib' x = fib (x-1) + fib (x-2) [0]: http://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html
  • Symmetry 8y ago
    But is there any reason the Haskell compiler couldn't decide to memoize a function call itself if it determined that it would speed things up? To me that sounds hard for the compiler to do heuristically but a Haskell compiler should still have more scope to do optimizations like that than a C compiler has.
  • vmchale 8y ago
    Haskell is call-by-need so you get guarantees you wouldn't otherwise. It's not the same as memoization but it gives you what you want in any case.