[Haskell-cafe] Data.Map - visiting tree nodes withi a given key range ?
compl.yue at icloud.com
Mon Mar 16 06:02:40 UTC 2020
Thanks so much Olaf!
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
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.
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
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.
A bit context for clarity: an Object value is identified by an embedded
Data.Unique field, and has a mutable Control.Concurrent.STM.*TVar*
pointer to its attributes.
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.
I still need to finish PoC of the dababase first, no hurry for
performance improvement atm, as long as it's working correctly.
On 2020/3/16 上午2:42, Olaf Klinke wrote:
> 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
>>>> let m = fromList $ zip [1..] [undefined,"bar","baz",undefined]
>>>> foldRange (\a -> [a]) (2,3) m
>> Am 15.03.2020 um 18:30 schrieb Compl Yue <compl.yue at icloud.com>:
>> 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,
>> On 2020/3/15 下午9:37, Olaf Klinke wrote:
>>> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe