Michael Mossey mpm at alumni.caltech.edu
Tue Nov 3 21:26:17 EST 2009

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

```