[Haskell-beginners] I have created an ugly Haskell program..
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.
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
More information about the Beginners