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

[Heinrich Apfelmus]

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.
> [...]
>
> 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
>
> [...]
>
> Now, you might object that this is much more inefficient than the
> other solutions put forth.  That is very true. [...]
>
> However, I still find it very helpful to think about the essence
> of the problem like this: elegant yet inefficient code is a much
> better starting place than the other way around! [...]
>
> You can also try to optimize, taking advantage of the fact that we
> always call the functions built by asFunc with a sequence of strictly
> increasing inputs.

I am with Brent and Conal here. Now, to continue, ask yourself: What
Would Conal Do Next (WWCDN)?

What are we really trying to do here? What is this function, really,
considering that we are only evaluating it at a strictly increasing
sequence of inputs? Well, it seems to me that it is some special kind of
function, best captured as an *abstract data type*.


In particular, the function is something which I will call a "time
series". In other words, the input is to be thought of as time.

    data Time t = Moment t | Infinity
                deriving (Eq,Ord,Show)

The inclusion of infinity will turn out to be very convenient.

Now, the time series is a function that has a value  x1  in the distant
past, until a time  t1  where it begins to have the value  x2 , again
until a time  t2  where it switches to  x3  and so on, until a value  xn
 that is kept until infinity. In Haskell, this looks like this

  function t
     | -Infinity <= t && t < t1       = x1
     |        t1 <= t && t < t2       = x2
     |        t2 <= t && t < t3       = x3
     | ...
     |        t1 <= t && t < Infinity = xn

and pictorially, something like this:

                                                 ____ xn _____
                ____ x2 ____                    |
               |            |____ x3 ____ ...   |
  _____ x1 ____|

 -Inf          t1            t2           ...   tn          Inf


Of course, we can implement this abstract data type with a list of pairs
 (tk,xk)

    newtype TimeSeries t a = TS { unTS :: [(a,Time t)] }
                           deriving (Show)

and our goal is to equip this data type with a few natural operations
that can be used to implement Philip's zip-like function.


The first two operations are

    progenitor :: TimeSeries t a -> a
    progenitor = fst . head . unTS

which returns the value from the distant past and

    beginning :: TimeSeries t a -> Time t
    beginning = snd . head . unTS

which returns the first point in time when the function changes its
value. These correspond to the operation  head  on lists.


The next operation is called  `forgetTo` t  and will throw away all
values and changes before and including a given time  t .

    forgetTo :: Ord t => TimeSeries t a -> Time t -> TimeSeries t a
    forgetTo (TS xs) Infinity = TS [last xs]
    forgetTo (TS xs) t        = TS $ dropWhile ((<= t) . snd) xs

This roughly corresponds to  tail , but takes advantage of the time
being continuous.


Last but not least, we need a way to create a time series

    forever :: a -> TimeSeries t a
    forever x = TS [(x,Infinity)]

and we need to add values to a time series, which can be done with an
operation called  prepend  that adds a new  beginning  and  replaces the
 progenitor .

        -- We assume that  t < beginning xs
    prepend :: a -> Time t -> TimeSeries t a -> TimeSeries t a
    prepend x Infinity _       = TS [(x,Infinity)]
    prepend x t        (TS xs) = TS $ (x,t) : xs

These operations correspond to [] and (:) for lists.


The key about these operations is that they have a description /
intuition that is *independent* of the implementation of times series.
At no point do we need to know how exactly  TimeSeries  is implemented
to understand what these five operations do.

Now, Philip's desired zip-like function is straightforward to implement:

    zipSeries :: Ord t => TimeSeries t a -> TimeSeries t b
                          -> TimeSeries t (a,b)
    zipSeries xs ys = prepend (progenitor xs, progenitor ys) t $
        zipSeries (xs `forgetTo` t) (ys `forgetTo` t)
        where t = min (beginning xs) (beginning ys)

and you may want to convince yourself of its correctness by appealing to
the intuition behind time series.


Regards,
apfelmus

--
http://apfelmus.nfshost.com