Implement a function `memoize : (a - b) - (a - b)`

Question

Implement a function `memoize : (a -> b) -> (a -> b)`

Anonymous · Accepted Answer

I got stuck a bit before I figured out that I cannot do it in Haskell easily and safely and I was unsure about using unsafe features or monads. So I just switched to JavaScript. I coded my memoization function to set up a lexically scoped hash-based cache of function results plus an inner closure using this cache.

Alec Theriault · Answer

So. Here is a Haskell answer which works for me. I think adding the Ord constraint is relatively minor. This ought to be a correct use of unsafePerformIO...

import Data.Map
import Data.IORef
import System.IO.Unsafe

memoize :: Ord a => (a -> b) -> (a -> b)
memoize f = \x -> unsafePerformIO $ do
      table  return y
        Nothing  -> do
          let y = f x
          modifyIORef dict (insert x y)
          return y 
  where
    dict :: IORef (Map a b)
    {-# NOINLINE dict #-}
    dict = unsafePerformIO $ newIORef empty

Jane Street

Jane Street Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches