How to do range searches?

[syaiful6]

Hi, it's maybe my ignorance. since this library implements map using Binary Tree, i guess it can do range searches, right? To illustrate, i have a Map that key are numbers and the values are just a string, since i need efficient ranges searches, i need to take all tree (Map k v) where the key between for example 0-50. is it possible? i found fromZipper function, but i don't know how to use it. 😄

[paf31]

Are you looking for functions like lookupLT?

[syaiful6]

@paf31 looking on the lookupLT i fear it's not what i mean.lookupLT only return single key value pair, right? i need all keys-values pair which least than specifix key. if i compare my key with the map directly, is it i just need to pick the left node? right now, i am using naive filter which i believe not so efficient since i traverse all of them, btw the map already sorted, so i want to take advantage of it.

[hdgarrood]

I guess we want something like this?

subMap :: forall k v. (Ord k) => { min :: k, max :: k } -> Map k v -> Map k v

with the following property:

forall m :: Map k v, min :: k, max :: k, key :: k,
  let m' = subMap { min, max } m in
    if (min <= key && key <= max)
      then lookup key m == lookup key m'
      else not (member key m')

[hdgarrood]

Or perhaps it should take a { min :: Maybe k, max :: Maybe k } where supplying Nothing for one of the parameters means that it's not bounded on that side. So subMap { min: Just x, max: Nothing } gives you everything greater than or equal to x.

[syaiful6]

@hdgarrood yes, something like that.

[hdgarrood]

This was addressed by #114.