CODEWITHSUNDEEP
haskellghcmemoization
Jeff Burdges
Jeff Burdges

Reputation: 4251

Is there any implicit-ish memoization in Haskell?

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.

Upvotes: 7

Views: 718

Answers (2)

Jeff Burdges
Jeff Burdges

Reputation: 4251

There is another plausible approach arising from the fact that type now defined synonyms for type constrains, as noted in Philip JF's answer here.

You could probably create a synonym for a type constraint that created implicit parameters for all the various derived values :

type Necklaces = (necklaces :: V.Vector Necklace,
                  denominator :: Int,
                  numerators :: V.Vector Int)

kittytoy :: (Necklaces) => Meow -> ...

You'd initially assign all the values like ?numerators using a template Haskell construction of some form. I'll play with it to see if it works.

Upvotes: 0

ehird
ehird

Reputation: 40787

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

Upvotes: 7

Related Questions