Is there any implicit-ish memoization in Haskell?
ghc, haskell, memoization
Solution
You're probably looking for pure memoisation, as implemented by data-memocombinators. Basically, it works by creating a (lazy, possibly infinite) tree structure with all the possible values of the function at each leaf, and then creating a new function that simply accesses the value at the relevant location. For instance, you can write a memoiser for functions `Bool -> a` like this:
memoBool :: (Bool -> a) -> (Bool -> a)
memoBool f =
let fTrue = f True
fFalse = f False
in \b -> if b then fTrue else fFalse
In this case, the "tree structure" is rather bonsai, having only two leaves.
data-memocombinators packages this up in the `Memo a` type, defined as `forall r. (a -> r) -> (a -> r)`, with useful combinators like `pair :: Memo a -> Memo b -> Memo (a, b)` (read: if you can memoise functions of argument type `a`, and memoise functions of argument type `b`, you can memoise functions of argument type `(a, b)`).
This is pure, and pretty elegant, relying on the sharing implemented by basically all Haskell implementations (which is the same thing that makes your record idea work). Unfortunately, it's also not very fast, so for practical use you might want to use uglymemo instead, which uses a mutable `Map` behind the scenes (but exposes an externally-pure interface).
Problem
Is there any way to force GHC to thunk a particular computation for the lifetime of a particular value? I could obviously place the value into a record, creating lazy record entries for the result of said computation, and create a maker function that builds the record and thunks the value into said entries. I'd hate needing to pull the original value out from the record every time I wanted it though. And Haskell has no adhocly polymorphic is-a relationships like C++ or Java. Are there any trick for memoizing values across multiple unrelated invocations of a function with identical parameters? I could vaguely imagine various tricks with forms of dependent types that'd effectively tell the compiler multiple usages were coming. There aren't any dependent types in Haskell but maybe something around implicit parameters? I suppose not, but I thought I'd ask. A pragma perhaps? Imagine I've a vector of `Necklace` data structures for which I need a resulting vector of rational numbers, stored as a common denominator and a vector of numerators. ``` {-# LANGUAGE ImplicitParams #-} import qualified Data.Vector as V data Necklace = Necklace { ... } necklace_length n = ... denominator :: (necklaces :: V.Vector Necklace) => Int denominator = V.foldl' lcm 30 $ V.map necklace_length ?necklaces numerators :: (necklaces :: V.Vector Necklace) => V.Vector Int numerators = V.map f ?necklaces where f x = ... denominator ... kittytoy :: (necklaces :: V.Vector Necklace) => Meow -> ... kittytoy = \meow -> ... numerators ... ``` A priori, I'd expect that, if I invoke `kittytoy` several million times, each with a different parameter `meow`, then GHC produces code that invokes `numerators` a million times, each with an identical implicit parameters `necklaces`. It's nevertheless obvious that `numerators` only needs to be invoked once though, the first time `?necklaces` gets assigned, meaning GHC could potentially notice this optimization. There should even be an explicit code refactoring approach using template haskell to explicitly pass the thunks by producing code like `?numerators = numerators` and adding `numerators :: V.Vector Int` to type constraints of functions that call it.