<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Thanks so much Olaf!</p>
<p>I think `foldRange` should already work for my case without
concerns. And more importantly this example builds the intuition
to get me started in touching Map internals, I was hesitating with
fear before :p</p>
<p>That said, I have another improvement postponed, which I assumed
much tougher. That is fast re-indexing at the time some of a
business object's key attributes change.</p>
<p> I currently use another HashMap to associate the old IndexKey of
an Object with itself, on re-indexing , I just lookup the old
IndexKey from the HashMap, and delete the resulted key from the
tree Map, before putting the Object with new IndexKey into tree
Map. This works but not reasonably efficient.</p>
<p>I have an idea in my mind that insertion operation into the tree
Map could return a fast-entry-remover function with sufficient
internal structure captured, so instead of going the O(log n)
deletion by old key (also re-balancing effort to be added), this
remover function can be reverse-lookup'ed by Object, then applied
to have its rival entry removed from a later version of the tree
Map. Yet better to upgrade the remover into a replacer, that
inserts an entry with the new IndexKey of the Object in a single
pass. Changing a later field on a multi-field index should produce
the new IndexKey sufficiently nearer to the old key in tree Map's
respect, so I expect amortized complexity to be greatly reduced,
especially when the number of indexed objects is very large.<br>
</p>
<p>A bit context for clarity: an Object value is identified by an
embedded Data.Unique field, and has a mutable <a
href="http://localhost:8080/file/home/cyue/.stack/programs/x86_64-linux/ghc-8.6.5/share/doc/ghc-8.6.5/html/libraries/stm-2.5.0.0/Control-Concurrent-STM-TVar.html"
style="color: black; text-decoration: none; background-color:
rgb(255, 255, 187); font-family: sans-serif; font-size: 16px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 400; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;">Control.Concurrent.STM.<span
class="name" style="color: rgb(196, 69, 29);"><b>TVar</b></span></a>
pointer to its attributes.<br>
</p>
<p>I'm not aware of existing codebase doing that, maybe I'll be
extending Data.Map to do that, but it'll be excellent to hear
about your insights about tackling this improvement.</p>
<p>I still need to finish PoC of the dababase first, no hurry for
performance improvement atm, as long as it's working correctly.<br>
</p>
<p>Best regards,</p>
<p>Compl</p>
<p><br>
</p>
<div class="moz-cite-prefix">On 2020/3/16 上午2:42, Olaf Klinke wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CFE3A829-2CBB-45C8-935D-3F16312D0B80@aatal-apotheke.de">
<pre class="moz-quote-pre" wrap="">Dear Compl,
there is no such function in the Data.Map.Internal module. You have to decompose the map structure yourself.
import Data.Map.Internal
-- name clash with Control.Monad
when :: (Monoid b) => Bool -> b -> b
when t b = if t then b else mempty
contains :: Ord k => (k,k) -> k -> Bool
contains (lbound,ubound) k = lbound <= k && k <= ubound
foldRange :: (Monoid b, Ord k) => (a -> b) -> (k,k) -> Map k a -> b
foldRange f range@(lbound,ubound) m = case m of
Tip -> mempty
(Bin _ k a left right) -> foldLeft <> this <> foldRight where
foldLeft = when (lbound < k) (foldRange f range left)
this = when (range `contains` k) (f a)
foldRight = when (k < ubound) (foldRange f range right)
-- verify that only the range is processed
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">let m = fromList $ zip [1..] [undefined,"bar","baz",undefined]
foldRange (\a -> [a]) (2,3) m
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">["bar","baz"]
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">Am 15.03.2020 um 18:30 schrieb Compl Yue <a class="moz-txt-link-rfc2396E" href="mailto:compl.yue@icloud.com"><compl.yue@icloud.com></a>:
Thanks Olaf,
Can you point me to the specific function for key range traversal? I went over the module doc for Data.Map.Internal and Data.Map.Strict.Internal twice, yet still don't get which one supposed to work for me, or I should ignore doc and look at the code instead ?
And the values to be scanned in specific key range are going to be consumed by some CPS mutual iterator, so fold can't be used as I see it.
Best regards,
Compl
On 2020/3/15 下午9:37, Olaf Klinke wrote:
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">You can roll your own indexKeyRange using the Data.Map.Internal module which exposes the (currently used) Map implementation. Also note that if the list of values in range is to be consumed immediately, you might want to go for a fold-based function:
foldlWithRange :: (a -> k -> b -> a) -> (a,a) -> b -> Map k a -> b
Olaf
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">
</pre>
</blockquote>
</body>
</html>