[Haskell-cafe] Data.Map - visiting tree nodes withi a given key range ?

[Compl Yue]

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 
reasonably efficient.

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* 
<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> 
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.

Best regards,

Compl


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
> ["bar","baz"]
>
>> 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,
>>
>> Compl
>>
>>
>> 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
>>>
>>> Olaf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20200316/f231e092/attachment.html>