StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Well, there's <code>Data.HashTable</code>. Hash tables don't tend to play nicely with immutable data and referential transparency, though, so I don't think it sees a lot of use.</p> <p>For a small number of values, stashing them in a search tree (such as <code>Data.Map</code>) would probably be fast enough. If you can put up with doing some mangling of your <code>Double</code>s, a more robust solution would be to use a trie-like structure, such as <code>Data.IntMap</code>; these have lookup times proportional primarily to key length, and roughly constant in collection size. If <code>Int</code> is too limiting, you can dig around on Hackage to find trie libraries that are more flexible in the type of key used.</p> <p>As for how to cache the results, I think what you want is usually called <a href="http://www.haskell.org/haskellwiki/Memoization" rel="noreferrer">"memoization"</a>. If you want to compute and memoize results on demand, the gist of the technique is to define an indexed data structure containing <em>all possible results</em>, in such a way that when you ask for a specific result it forces only the computations needed to get the answer you want. Common examples usually involve indexing into a list, but the same principle should apply for any non-strict data structure. As a rule of thumb, non-function values (including infinite recursive data structures) will often be cached by the runtime, but not function results, so the trick is to wrap all of your computations inside a top-level definition that doesn't depend on any arguments.</p> <p><strong>Edit:</strong> MemoTrie example ahoy!</p> <p>This is a quick and dirty proof of concept; better approaches may exist.</p> <pre><code>{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE TypeOperators #-} import Data.MemoTrie import Data.Binary import Data.ByteString.Lazy hiding (map) mangle :: Double -> [Int] mangle = map fromIntegral . unpack . encode unmangle :: [Int] -> Double unmangle = decode . pack . map fromIntegral instance HasTrie Double where data Double :->: a = DoubleTrie ([Int] :->: a) trie f = DoubleTrie $ trie $ f . unmangle untrie (DoubleTrie t) = untrie t . mangle slow x | x < 1 = 1 | otherwise = slow (x / 2) + slow (x / 3) memoSlow :: Double -> Integer memoSlow = memo slow </code></pre> <p>Do note the GHC extensions used by the MemoTrie package; hopefully that isn't a problem. Load it up in GHCi and try calling <code>slow</code> vs. <code>memoSlow</code> with something like (10^6) or (10^7) to see it in action.</p> <p>Generalizing this to functions taking multiple arguments or whatnot should be fairly straightforward. For further details on using MemoTrie, you might find <a href="http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/" rel="noreferrer">this blog post by its author</a> helpful.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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