[Haskell-cafe] Unambiguous choice implementation

[Bartosz Milewski]

I see. So you're current implementation is not push, is it? The original
pull implementation in Fran also used Maybe events, but that was considered
inefficient. How is Reactive Banana better then Fran then?

--Bartosz

On Tue, Jun 26, 2012 at 1:40 AM, Heinrich Apfelmus <
apfelmus at quantentunnel.de> wrote:

> 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<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 at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Haskell-cafe" group.
> To post to this group, send email to haskell-cafe at googlegroups.com.
> To unsubscribe from this group, send email to haskell-cafe+unsubscribe@**
> googlegroups.com <haskell-cafe%2Bunsubscribe at googlegroups.com>.
> For more options, visit this group at http://groups.google.com/**
> group/haskell-cafe?hl=en<http://groups.google.com/group/haskell-cafe?hl=en>
> .
>
>


-- 
[:Bartosz:]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120626/a092df52/attachment.htm>