5 ms·
> 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 auto
by 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 agoBut 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 agoHaskell 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.