LensMemoTraverse.hs

--
import Data.Map.Lazy
import Control.Lens

-- We wanted to traverse a structure, but not recompute the function for duplicate keys. And then we also needed cache.
-- It's probably tricky to unlens this.

traverseMemoOf :: (Ord a, Monad f) => Traversal s t a b -> (a -> f b) -> s -> f (t, ML.Map a b)
traverseMemoOf l f z =
  runStateT (traverseOf l g z) ML.empty
  where g dt = do r <- gets (ML.lookup dt)
                  case r of
                    Nothing -> do r' <- lift $ f dt
                                  modify $ ML.insert dt r'
                                  return $! r'
                    Just v -> return $! v