Databases
StackOverflow2013
Postsdbo
POMemoizing IO Computations in Haskell
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMemoizing IO Computations in Haskell
    primarykey
    data
    text
    <p>I have a function</p> <pre><code>f :: MonadIO m =&gt; a -&gt; m b </code></pre> <p>which takes some input and returns an IO computation that will yield output. I want to "memoize" <code>f</code> so that I only ever perform these computations once for each input. For example, if</p> <pre><code>f :: String -&gt; IO String f s = putStrLn ("hello " ++ s) &gt;&gt; return s </code></pre> <p>then I want a function <code>memoize</code> such that</p> <pre><code>do mf &lt;- memoize f s &lt;- mf "world" t &lt;- mf "world" return (s,t) </code></pre> <p>prints <code>"hello world"</code> exactly once and returns <code>("world", "world")</code>. The program I'm writing is multi-threaded, so this property should hold even if different threads are all calling <code>mf</code>.</p> <p>Below is the (terrible) solution I've come up with so far. My question is whether and how it can be improved.</p> <pre><code>memoize :: (MonadIO m, Ord a) =&gt; (a -&gt; m b) -&gt; m (a -&gt; m b) memoize f = do cache &lt;- liftIO $ newTVarIO Map.empty return $ \a -&gt; do v &lt;- liftIO $ atomically $ lookupInsert cache a b &lt;- maybe (f a) return =&lt;&lt; liftIO (atomically $ takeTMVar v) liftIO $ atomically $ putTMVar v $ Just b return b where lookupInsert :: Ord a =&gt; TVar (Map a (TMVar (Maybe b))) -&gt; a -&gt; STM (TMVar (Maybe b)) lookupInsert cache a = do mv &lt;- Map.lookup a &lt;$&gt; readTVar cache case mv of Just v -&gt; return v Nothing -&gt; do v &lt;- newTMVar Nothing modifyTVar cache (Map.insert a v) return v </code></pre> <p>There are a few things going on here: </p> <p>1) <code>cache</code> has type <code>TVar (Map a (TMVar (Maybe b)))</code>. It maps inputs to <code>TMVar</code>'s that contain either a computed value, or <code>Nothing</code> (which indicates that a value hasn't been computed yet). The function <code>lookupInsert</code> inspects <code>cache</code>, and inserts a new <code>TMVar</code> initialized to <code>Nothing</code> if none is present already.</p> <p>2) The returned action first obtains the <code>v :: TMVar (Maybe b)</code> associated to <code>a</code>, then takes it, and either performs the computation <code>f a</code> to obtain a result or returns the value stored in the <code>Maybe</code> if it's available. This <code>take</code> and <code>put</code> pattern is so that two different threads don't both run the computation <code>f a</code> after seeing that it hasn't been run yet.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdavidsd
    1. USdavidsd
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMemoizing IO Computations in Haskell
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMemoizing IO Computations in Haskell
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POMemoizing IO Computations in Haskell
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think you want the values in the map to be either `TVar (Maybe a)` or `TMVar b` (which is equivalent to `TVar (Maybe b)` under the hood). You have two layers of emptiness when it seems like you only need one. Second, you should combine all of your `atomically` actions into a single transaction to avoid race conditions.
      singulars
      1. POMemoizing IO Computations in Haskell
      1. USGabriel Gonzalez
    2. COI'm not sure how to combine the `atomically` actions since we might have to do the computation `f a` in the middle. The latter exists in the monad `m`, so it seems like the `take` and `put` must be lifted to `m`.
      singulars
      1. POMemoizing IO Computations in Haskell
      1. USdavidsd
    3. COLooks a bit like you're in the wrong monad to me.
      singulars
      1. POMemoizing IO Computations in Haskell
      1. USleftaroundabout
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload