Thanks, Brent, for this way of looking at it. If you want n log n behavior you could write asFunc to use a Map for lookup. -Mike Brent Yorgey wrote:
Ask yourself: What Would Conal Do (WWCD)? Conal Elliott is always trying to get people to think about the semantic essence of their problems, so let's try it.
What are we REALLY trying to do here? What are those lists of tuples, REALLY? Well, it seems to me that the lists of tuples are really just representing *functions* on some totally ordered domain. The list-of-pairs representation takes advantage of the fact that these functions tend to be constant on whole intervals of the domain; we only need a tuple to mark the *beginning* of a constant interval. The fact that we want to take a value from the last old timestamp when we don't have a certain timestamp in the list reflects the fact that the function takes on that value over the whole *interval* from the timestamp when it occurred to whenever the next timestamp is.
So, let's try converting these lists of pairs to actual functions:
asFunc :: (Ord a) => [(a,b)] -> (a -> Maybe b) asFunc is a = fmap snd . listToMaybe . reverse . takeWhile ((<=a) . fst) $ is
Simple -- we just scan through the list looking for the right interval.