{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}

-- |
-- Module      :   Grisette.Internal.Core.Data.MemoUtils
-- Copyright   :   (c) Sirui Lu 2021-2023
-- License     :   BSD-3-Clause (see the LICENSE file)
--
-- Maintainer  :   siruilu@cs.washington.edu
-- Stability   :   Experimental
-- Portability :   GHC only
module Grisette.Internal.Core.Data.MemoUtils
  ( -- * Memoization
    stableMemo,
    stableMemo2,
    stableMemo3,
    stableMup,
    stableMemoFix,
    weakStableMemo,
    weakStableMemo2,
    weakStableMemo3,
    weakStableMup,
    weakStableMemoFix,
    htmemo,
    htmemo2,
    htmemo3,
    htmemoFix,
    htmup,
  )
where

import Control.Applicative (Const (Const, getConst))
import Control.Monad.Fix (fix)
import Data.Atomics (atomicModifyIORefCAS_)
import qualified Data.HashMap.Strict as HM
import Data.Hashable (Hashable)
import Data.IORef (IORef, newIORef, readIORef)
import Data.Proxy (Proxy (Proxy))
import GHC.Base (Any, Type)
import System.IO.Unsafe (unsafePerformIO)
import System.Mem.StableName (StableName, makeStableName)
import System.Mem.Weak (Weak)
import qualified System.Mem.Weak as Weak
import Unsafe.Coerce (unsafeCoerce)

newtype (f <<< g) a = O {forall (f :: * -> *) (g :: * -> *) a. (<<<) f g a -> f (g a)
unO :: f (g a)}

-- Invariant: The type parameters for a key and its corresponding
-- value are the same.
type SNMap f g = IORef (HM.HashMap (StableName (f Any)) (g Any))

type MemoTable ref f g = SNMap f (ref <<< g)

class Ref ref where
  mkRef :: a -> b -> IO () -> IO (ref b)
  deRef :: ref a -> IO (Maybe a)
  finalize :: ref a -> IO ()
  tableFinalizer :: MemoTable ref f g -> IO ()
  tableFinalizer MemoTable ref f g
t = MemoTable ref f g
-> IO (HashMap (StableName (f Any)) ((<<<) ref g Any))
forall a. IORef a -> IO a
readIORef MemoTable ref f g
t IO (HashMap (StableName (f Any)) ((<<<) ref g Any))
-> (HashMap (StableName (f Any)) ((<<<) ref g Any) -> IO ())
-> IO ()
forall a b. IO a -> (a -> IO b) -> IO b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ((<<<) ref g Any -> IO ())
-> HashMap (StableName (f Any)) ((<<<) ref g Any) -> IO ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (ref (g Any) -> IO ()
forall a. ref a -> IO ()
forall (ref :: * -> *) a. Ref ref => ref a -> IO ()
finalize (ref (g Any) -> IO ())
-> ((<<<) ref g Any -> ref (g Any)) -> (<<<) ref g Any -> IO ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (<<<) ref g Any -> ref (g Any)
forall (f :: * -> *) (g :: * -> *) a. (<<<) f g a -> f (g a)
unO)

instance Ref Weak where
  mkRef :: forall a b. a -> b -> IO () -> IO (Weak b)
mkRef a
x b
y = a -> b -> Maybe (IO ()) -> IO (Weak b)
forall k v. k -> v -> Maybe (IO ()) -> IO (Weak v)
Weak.mkWeak a
x b
y (Maybe (IO ()) -> IO (Weak b))
-> (IO () -> Maybe (IO ())) -> IO () -> IO (Weak b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IO () -> Maybe (IO ())
forall a. a -> Maybe a
Just
  deRef :: forall a. Weak a -> IO (Maybe a)
deRef = Weak a -> IO (Maybe a)
forall a. Weak a -> IO (Maybe a)
Weak.deRefWeak
  finalize :: forall a. Weak a -> IO ()
finalize = Weak a -> IO ()
forall a. Weak a -> IO ()
Weak.finalize

newtype Strong a = Strong a

instance Ref Strong where
  mkRef :: forall a b. a -> b -> IO () -> IO (Strong b)
mkRef a
_ b
y IO ()
_ = Strong b -> IO (Strong b)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Strong b -> IO (Strong b)) -> Strong b -> IO (Strong b)
forall a b. (a -> b) -> a -> b
$ b -> Strong b
forall a. a -> Strong a
Strong b
y
  deRef :: forall a. Strong a -> IO (Maybe a)
deRef (Strong a
x) = Maybe a -> IO (Maybe a)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe a -> IO (Maybe a)) -> Maybe a -> IO (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
x
  finalize :: forall a. Strong a -> IO ()
finalize (Strong a
_) = () -> IO ()
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
  tableFinalizer :: forall (f :: * -> *) (g :: * -> *). MemoTable Strong f g -> IO ()
tableFinalizer MemoTable Strong f g
_ = () -> IO ()
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ()

finalizer :: StableName (f Any) -> Weak (MemoTable ref f g) -> IO ()
finalizer :: forall (f :: * -> *) (ref :: * -> *) (g :: * -> *).
StableName (f Any) -> Weak (MemoTable ref f g) -> IO ()
finalizer StableName (f Any)
sn Weak (MemoTable ref f g)
weakTbl = do
  r <- Weak (MemoTable ref f g) -> IO (Maybe (MemoTable ref f g))
forall a. Weak a -> IO (Maybe a)
Weak.deRefWeak Weak (MemoTable ref f g)
weakTbl
  case r of
    Maybe (MemoTable ref f g)
Nothing -> () -> IO ()
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    Just MemoTable ref f g
tbl -> do
      MemoTable ref f g
-> (HashMap (StableName (f Any)) ((<<<) ref g Any)
    -> HashMap (StableName (f Any)) ((<<<) ref g Any))
-> IO ()
forall t. IORef t -> (t -> t) -> IO ()
atomicModifyIORefCAS_ MemoTable ref f g
tbl ((HashMap (StableName (f Any)) ((<<<) ref g Any)
  -> HashMap (StableName (f Any)) ((<<<) ref g Any))
 -> IO ())
-> (HashMap (StableName (f Any)) ((<<<) ref g Any)
    -> HashMap (StableName (f Any)) ((<<<) ref g Any))
-> IO ()
forall a b. (a -> b) -> a -> b
$ StableName (f Any)
-> HashMap (StableName (f Any)) ((<<<) ref g Any)
-> HashMap (StableName (f Any)) ((<<<) ref g Any)
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
HM.delete StableName (f Any)
sn

unsafeToAny :: f a -> f Any
unsafeToAny :: forall (f :: * -> *) a. f a -> f Any
unsafeToAny = f a -> f Any
forall a b. a -> b
unsafeCoerce

unsafeFromAny :: f Any -> f a
unsafeFromAny :: forall (f :: * -> *) a. f Any -> f a
unsafeFromAny = f Any -> f a
forall a b. a -> b
unsafeCoerce

{-# NOINLINE memo' #-}
memo' ::
  (Ref ref) =>
  Proxy ref ->
  (forall a. f a -> g a) ->
  MemoTable ref f g ->
  Weak (MemoTable ref f g) ->
  f b ->
  g b
memo' :: forall (ref :: * -> *) (f :: * -> *) (g :: * -> *) b.
Ref ref =>
Proxy ref
-> (forall a. f a -> g a)
-> MemoTable ref f g
-> Weak (MemoTable ref f g)
-> f b
-> g b
memo' Proxy ref
_ forall a. f a -> g a
f MemoTable ref f g
tbl Weak (MemoTable ref f g)
weakTbl !f b
x = IO (g b) -> g b
forall a. IO a -> a
unsafePerformIO (IO (g b) -> g b) -> IO (g b) -> g b
forall a b. (a -> b) -> a -> b
$ do
  sn <- f Any -> IO (StableName (f Any))
forall a. a -> IO (StableName a)
makeStableName (f Any -> IO (StableName (f Any)))
-> f Any -> IO (StableName (f Any))
forall a b. (a -> b) -> a -> b
$ f b -> f Any
forall (f :: * -> *) a. f a -> f Any
unsafeToAny f b
x
  lkp <- HM.lookup sn <$> readIORef tbl
  case lkp of
    Maybe ((<<<) ref g Any)
Nothing -> StableName (f Any) -> IO (g b)
notFound StableName (f Any)
sn
    Just (O ref (g Any)
w) -> do
      maybeVal <- ref (g Any) -> IO (Maybe (g Any))
forall a. ref a -> IO (Maybe a)
forall (ref :: * -> *) a. Ref ref => ref a -> IO (Maybe a)
deRef ref (g Any)
w
      case maybeVal of
        Maybe (g Any)
Nothing -> StableName (f Any) -> IO (g b)
notFound StableName (f Any)
sn
        Just g Any
val -> do
          g b -> IO (g b)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (g b -> IO (g b)) -> g b -> IO (g b)
forall a b. (a -> b) -> a -> b
$ g Any -> g b
forall (f :: * -> *) a. f Any -> f a
unsafeFromAny g Any
val
  where
    notFound :: StableName (f Any) -> IO (g b)
notFound StableName (f Any)
sn = do
      let !y :: g b
y = f b -> g b
forall a. f a -> g a
f f b
x
      weak <- f b -> g Any -> IO () -> IO (ref (g Any))
forall a b. a -> b -> IO () -> IO (ref b)
forall (ref :: * -> *) a b.
Ref ref =>
a -> b -> IO () -> IO (ref b)
mkRef f b
x (g b -> g Any
forall (f :: * -> *) a. f a -> f Any
unsafeToAny g b
y) (IO () -> IO (ref (g Any))) -> IO () -> IO (ref (g Any))
forall a b. (a -> b) -> a -> b
$ StableName (f Any) -> Weak (MemoTable ref f g) -> IO ()
forall (f :: * -> *) (ref :: * -> *) (g :: * -> *).
StableName (f Any) -> Weak (MemoTable ref f g) -> IO ()
finalizer StableName (f Any)
sn Weak (MemoTable ref f g)
weakTbl
      atomicModifyIORefCAS_ tbl $ HM.insert sn $ O weak
      return y

{-# NOINLINE memo0 #-}
memo0 ::
  (Ref ref) =>
  Proxy (ref :: Type -> Type) ->
  (forall a. f a -> g a) ->
  f b ->
  g b
memo0 :: forall (ref :: * -> *) (f :: * -> *) (g :: * -> *) b.
Ref ref =>
Proxy ref -> (forall a. f a -> g a) -> f b -> g b
memo0 Proxy ref
p forall a. f a -> g a
f =
  let (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))
tbl, Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)))
weak) = IO
  (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
   Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))))
-> (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
    Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))))
forall a. IO a -> a
unsafePerformIO (IO
   (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
    Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))))
 -> (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
     Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)))))
-> IO
     (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
      Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))))
-> (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)),
    Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))))
forall a b. (a -> b) -> a -> b
$ do
        tbl' <- HashMap (StableName (f Any)) ((<<<) ref g Any)
-> IO (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)))
forall a. a -> IO (IORef a)
newIORef HashMap (StableName (f Any)) ((<<<) ref g Any)
forall k v. HashMap k v
HM.empty
        weak' <- Weak.mkWeakPtr tbl . Just $ tableFinalizer tbl
        return (tbl', weak')
   in Proxy ref
-> (forall a. f a -> g a)
-> MemoTable ref f g
-> Weak (MemoTable ref f g)
-> f b
-> g b
forall (ref :: * -> *) (f :: * -> *) (g :: * -> *) b.
Ref ref =>
Proxy ref
-> (forall a. f a -> g a)
-> MemoTable ref f g
-> Weak (MemoTable ref f g)
-> f b
-> g b
memo' Proxy ref
p f a -> g a
forall a. f a -> g a
f MemoTable ref f g
forall {f :: * -> *} {g :: * -> *}.
IORef (HashMap (StableName (f Any)) ((<<<) ref g Any))
tbl Weak (MemoTable ref f g)
forall {f :: * -> *} {g :: * -> *}.
Weak (IORef (HashMap (StableName (f Any)) ((<<<) ref g Any)))
weak

-- | Memoize a unary function.
stableMemo :: (a -> b) -> (a -> b)
stableMemo :: forall a b. (a -> b) -> a -> b
stableMemo a -> b
f = Const b Any -> b
forall {k} a (b :: k). Const a b -> a
getConst (Const b Any -> b) -> (a -> Const b Any) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Proxy Strong
-> (forall a. Const a a -> Const b a) -> Const a Any -> Const b Any
forall (ref :: * -> *) (f :: * -> *) (g :: * -> *) b.
Ref ref =>
Proxy ref -> (forall a. f a -> g a) -> f b -> g b
memo0 (Proxy Strong
forall {k} (t :: k). Proxy t
Proxy :: Proxy Strong) (b -> Const b a
forall {k} a (b :: k). a -> Const a b
Const (b -> Const b a) -> (Const a a -> b) -> Const a a -> Const b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f (a -> b) -> (Const a a -> a) -> Const a a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Const a a -> a
forall {k} a (b :: k). Const a b -> a
getConst) (Const a Any -> Const b Any)
-> (a -> Const a Any) -> a -> Const b Any
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Const a Any
forall {k} a (b :: k). a -> Const a b
Const

-- | Lift a memoizer to work with one more argument.
stableMup :: (b -> c) -> (a -> b) -> (a -> c)
stableMup :: forall b c a. (b -> c) -> (a -> b) -> a -> c
stableMup b -> c
mem a -> b
f = (a -> c) -> a -> c
forall a b. (a -> b) -> a -> b
stableMemo (b -> c
mem (b -> c) -> (a -> b) -> a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f)

-- | Curried memoization to share partial evaluation
stableMemo2 :: (a -> b -> c) -> (a -> b -> c)
stableMemo2 :: forall a b c. (a -> b -> c) -> a -> b -> c
stableMemo2 = ((b -> c) -> b -> c) -> (a -> b -> c) -> a -> b -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
stableMup (b -> c) -> b -> c
forall a b. (a -> b) -> a -> b
stableMemo

-- | Curried memoization to share partial evaluation
stableMemo3 :: (a -> b -> c -> d) -> (a -> b -> c -> d)
stableMemo3 :: forall a b c d. (a -> b -> c -> d) -> a -> b -> c -> d
stableMemo3 = ((b -> c -> d) -> b -> c -> d)
-> (a -> b -> c -> d) -> a -> b -> c -> d
forall b c a. (b -> c) -> (a -> b) -> a -> c
stableMup (b -> c -> d) -> b -> c -> d
forall a b c. (a -> b -> c) -> a -> b -> c
stableMemo2

-- | Memoizing recursion. Use like 'fix'.
stableMemoFix :: ((a -> b) -> (a -> b)) -> a -> b
stableMemoFix :: forall a b. ((a -> b) -> a -> b) -> a -> b
stableMemoFix (a -> b) -> a -> b
h = ((a -> b) -> a -> b) -> a -> b
forall a. (a -> a) -> a
fix ((a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
stableMemo ((a -> b) -> a -> b) -> ((a -> b) -> a -> b) -> (a -> b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> a -> b
h)

-- | Memoize a unary function.
weakStableMemo :: (a -> b) -> (a -> b)
weakStableMemo :: forall a b. (a -> b) -> a -> b
weakStableMemo a -> b
f = Const b Any -> b
forall {k} a (b :: k). Const a b -> a
getConst (Const b Any -> b) -> (a -> Const b Any) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Proxy Weak
-> (forall a. Const a a -> Const b a) -> Const a Any -> Const b Any
forall (ref :: * -> *) (f :: * -> *) (g :: * -> *) b.
Ref ref =>
Proxy ref -> (forall a. f a -> g a) -> f b -> g b
memo0 (Proxy Weak
forall {k} (t :: k). Proxy t
Proxy :: Proxy Weak) (b -> Const b a
forall {k} a (b :: k). a -> Const a b
Const (b -> Const b a) -> (Const a a -> b) -> Const a a -> Const b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f (a -> b) -> (Const a a -> a) -> Const a a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Const a a -> a
forall {k} a (b :: k). Const a b -> a
getConst) (Const a Any -> Const b Any)
-> (a -> Const a Any) -> a -> Const b Any
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Const a Any
forall {k} a (b :: k). a -> Const a b
Const

-- | Lift a memoizer to work with one more argument.
weakStableMup :: (b -> c) -> (a -> b) -> (a -> c)
weakStableMup :: forall b c a. (b -> c) -> (a -> b) -> a -> c
weakStableMup b -> c
mem a -> b
f = (a -> c) -> a -> c
forall a b. (a -> b) -> a -> b
weakStableMemo (b -> c
mem (b -> c) -> (a -> b) -> a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f)

-- | Curried memoization to share partial evaluation
weakStableMemo2 :: (a -> b -> c) -> (a -> b -> c)
weakStableMemo2 :: forall a b c. (a -> b -> c) -> a -> b -> c
weakStableMemo2 = ((b -> c) -> b -> c) -> (a -> b -> c) -> a -> b -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
weakStableMup (b -> c) -> b -> c
forall a b. (a -> b) -> a -> b
weakStableMemo

-- | Curried memoization to share partial evaluation
weakStableMemo3 :: (a -> b -> c -> d) -> (a -> b -> c -> d)
weakStableMemo3 :: forall a b c d. (a -> b -> c -> d) -> a -> b -> c -> d
weakStableMemo3 = ((b -> c -> d) -> b -> c -> d)
-> (a -> b -> c -> d) -> a -> b -> c -> d
forall b c a. (b -> c) -> (a -> b) -> a -> c
weakStableMup (b -> c -> d) -> b -> c -> d
forall a b c. (a -> b -> c) -> a -> b -> c
weakStableMemo2

-- | Memoizing recursion. Use like 'fix'.
weakStableMemoFix :: ((a -> b) -> (a -> b)) -> a -> b
weakStableMemoFix :: forall a b. ((a -> b) -> a -> b) -> a -> b
weakStableMemoFix (a -> b) -> a -> b
h = ((a -> b) -> a -> b) -> a -> b
forall a. (a -> a) -> a
fix ((a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
weakStableMemo ((a -> b) -> a -> b) -> ((a -> b) -> a -> b) -> (a -> b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> a -> b
h)

-- | Function memoizer with mutable hash table.
{-# NOINLINE htmemo #-}
htmemo :: (Eq k, Hashable k) => (k -> a) -> k -> a
htmemo :: forall k a. (Eq k, Hashable k) => (k -> a) -> k -> a
htmemo k -> a
f = IO (k -> a) -> k -> a
forall a. IO a -> a
unsafePerformIO (IO (k -> a) -> k -> a) -> IO (k -> a) -> k -> a
forall a b. (a -> b) -> a -> b
$ do
  cache <- HashMap k a -> IO (IORef (HashMap k a))
forall a. a -> IO (IORef a)
newIORef HashMap k a
forall k v. HashMap k v
HM.empty
  return $ \(!k
x) -> IO a -> a
forall a. IO a -> a
unsafePerformIO (IO a -> a) -> IO a -> a
forall a b. (a -> b) -> a -> b
$ do
    tryV <- k -> HashMap k a -> Maybe a
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
x (HashMap k a -> Maybe a) -> IO (HashMap k a) -> IO (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IORef (HashMap k a) -> IO (HashMap k a)
forall a. IORef a -> IO a
readIORef IORef (HashMap k a)
cache
    case tryV of
      Maybe a
Nothing -> do
        let !v :: a
v = k -> a
f k
x
        IORef (HashMap k a) -> (HashMap k a -> HashMap k a) -> IO ()
forall t. IORef t -> (t -> t) -> IO ()
atomicModifyIORefCAS_ IORef (HashMap k a)
cache ((HashMap k a -> HashMap k a) -> IO ())
-> (HashMap k a -> HashMap k a) -> IO ()
forall a b. (a -> b) -> a -> b
$ \HashMap k a
old -> k -> a -> HashMap k a -> HashMap k a
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.insert k
x a
v HashMap k a
old
        a -> IO a
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return a
v
      Just a
v -> a -> IO a
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return a
v

-- | Lift a memoizer to work with one more argument.
htmup :: (Eq k, Hashable k) => (b -> c) -> (k -> b) -> (k -> c)
htmup :: forall k b c. (Eq k, Hashable k) => (b -> c) -> (k -> b) -> k -> c
htmup b -> c
mem k -> b
f = (k -> c) -> k -> c
forall k a. (Eq k, Hashable k) => (k -> a) -> k -> a
htmemo (b -> c
mem (b -> c) -> (k -> b) -> k -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> b
f)

-- | Function memoizer with mutable hash table. Works on binary functions.
htmemo2 :: (Eq k1, Hashable k1, Eq k2, Hashable k2) => (k1 -> k2 -> a) -> (k1 -> k2 -> a)
htmemo2 :: forall k1 k2 a.
(Eq k1, Hashable k1, Eq k2, Hashable k2) =>
(k1 -> k2 -> a) -> k1 -> k2 -> a
htmemo2 = ((k2 -> a) -> k2 -> a) -> (k1 -> k2 -> a) -> k1 -> k2 -> a
forall k b c. (Eq k, Hashable k) => (b -> c) -> (k -> b) -> k -> c
htmup (k2 -> a) -> k2 -> a
forall k a. (Eq k, Hashable k) => (k -> a) -> k -> a
htmemo

-- | Function memoizer with mutable hash table. Works on ternary functions.
htmemo3 ::
  (Eq k1, Hashable k1, Eq k2, Hashable k2, Eq k3, Hashable k3) =>
  (k1 -> k2 -> k3 -> a) ->
  (k1 -> k2 -> k3 -> a)
htmemo3 :: forall k1 k2 k3 a.
(Eq k1, Hashable k1, Eq k2, Hashable k2, Eq k3, Hashable k3) =>
(k1 -> k2 -> k3 -> a) -> k1 -> k2 -> k3 -> a
htmemo3 = ((k2 -> k3 -> a) -> k2 -> k3 -> a)
-> (k1 -> k2 -> k3 -> a) -> k1 -> k2 -> k3 -> a
forall k b c. (Eq k, Hashable k) => (b -> c) -> (k -> b) -> k -> c
htmup (k2 -> k3 -> a) -> k2 -> k3 -> a
forall k1 k2 a.
(Eq k1, Hashable k1, Eq k2, Hashable k2) =>
(k1 -> k2 -> a) -> k1 -> k2 -> a
htmemo2

-- | Memoizing recursion. Use like 'fix'.
htmemoFix :: (Eq k, Hashable k) => ((k -> a) -> (k -> a)) -> k -> a
htmemoFix :: forall k a. (Eq k, Hashable k) => ((k -> a) -> k -> a) -> k -> a
htmemoFix (k -> a) -> k -> a
h = ((k -> a) -> k -> a) -> k -> a
forall a. (a -> a) -> a
fix ((k -> a) -> k -> a
forall k a. (Eq k, Hashable k) => (k -> a) -> k -> a
htmemo ((k -> a) -> k -> a) -> ((k -> a) -> k -> a) -> (k -> a) -> k -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a) -> k -> a
h)