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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
