[Haskell-beginners] I have created an ugly Haskell program..

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.


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.

More information about the Beginners mailing list