CODEWITHSUNDEEP
haskell
Skirmantas Kligys
Skirmantas Kligys

Reputation: 826

Haskell data structure with efficient inexact lookup by key?

I have data keyed by Data.Time.Calendar.Day and need to efficiently look it up. Some dates are missing, when I try to look up by a missing key, I want to get data attached to the closest existing key, somewhat like std::map::lower_bound.

Any suggestions for existing libraries that can do this? I searched around for a while and only found maps supporting exact key lookups.

Thanks.

Upvotes: 0

Views: 181

Answers (2)

user3402224
user3402224

Reputation:

Did you check Data.Map.Lazy? In particular, I guess you could use the functions lookupLE and lookupGT, or similar. The complexity of these functions is O(log n), and similar functions exist in Data.Map.Strict.

Upvotes: 5

luqui
luqui

Reputation: 60533

A suitable combination of Data.Map's splitLookup and findMin/findMax will do the trick.

Upvotes: 2

Related Questions