[Haskell-cafe] Unambiguous choice implementation

[Heinrich Apfelmus]

Bartosz Milewski wrote:
> Thanks, Heinrich. I looked at the examples and at the references you
> provided. I understand the semantic model, so I guess I'm mostly trying to
> understand the implementation.

Ok. As I mentioned, if you just want to use the library there is no need 
to understand the implementation.

> Conal's paper was mostly about refining data
> structures in order to provide better implementation. It's all beautiful up
> to the point where he introduces the unamb hack. How did you manage to work
> around this problem and implement event merging efficiently?

Essentially, Conal implements events as

     type Event a = [(Time,a)]

The trouble is that when merging events, this representation forces you 
to wait for both events. In other words, the pattern match

     union ((t1,x1):e1) ((t2,x2):e2) = ...

needs to know the times of occurrences of both events before it can 
return the earlier one. The trouble is that the  merge  function should 
have returned the earlier one right away, before knowing exactly when 
the later one happens. The purpose of the  unamb  hack is circumvent 
that problem.


Reactive-banana's very simple solution to this problem is to represent 
events as

     type Event a = [(Time, Maybe a)]

and impose the additional invariant that all events in your program are 
"synchronized", in the sense that they indicate their occurrences at the 
same times^1. If they don't occur at that time, they use  Nothing . 
Then, you can implement  merge  simply as

     union ((t1,x1):e1) ((t2,x2):e2) = -- we always have  t1 = t2
         (t1, combine x1 x2) : union e1 e2
         where
         combine (Just x) Nothing  = Just x   -- only left occurs
         combine Nothing  (Just y) = Just y   -- only right occurs
         combine (Just x) (Just y) = Just x   -- simultaneous occurrence
         combine Nothing  Nothing  = Nothing  -- neither occurs

Since the times are given globally, we can also remove them and obtain

     type Event a = [Maybe a]

This is how  Reactive.Banana.Model  does it.


Of course, keeping track of a lot of  Nothing  is something that can be 
optimized. The optimization to apply here is to transform the 
implementation into a push-driven style. I haven't published the details 
yet, but some design notes can be found here.

http://apfelmus.nfshost.com/blog/2011/04/24-frp-push-driven-sharing.html


^1: Note that the times do not need to follow a uniform time step.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com