Corentin Dupont | 19 Jun 17:17 2014
Picon

Do you recognize this type?

Hi guys,
I am making a DSL for event composition (inspired from digestive-functor & reactive-banana) and I find myself wanting a primitive like that:

-- given a list of events, evaluate the function on those that have already fired.
-- returns an event yelding the result when ready.
ListEvent  :: [Event a] -> ([a] -> Maybe b) -> Event b 


Does this type tell you something? Is there a better abstraction that can encompass it?
My DSL is like that:

-- | Composable events
data Event a where
   SumEvent   :: Event a -> Event a -> Event a        -- The first event to fire will be returned
   AppEvent   :: Event (a -> b) -> Event a -> Event b -- Both events should fire, and then the result is returned
   PureEvent  :: a -> Event a                         -- Create a fake event. The result is useable with no delay.
   EmptyEvent :: Event a                              -- An event that is never fired.
   BaseEvent  :: (Typeable a) => Field a -> Event a   -- Embed a base event


It's easy to define instances for Applicative and Alternative.
But then I have a use case that I cannot solve:
In the case of votations (which use this DSL), sometime you can end prematuraly the voting, even if not everybody voted yet: for example if the majority is already reached.
In this case no need to wait for everybody, we can end the vote.

This does not seem to be possible with Applicative or Monad interfaces: things have to be sequenced in a monad, they cannot be evaluated in parralel.
For example:

do
   v1 <- getVote1
   v2 <- getVote2
   v3 <- getVote3
   evalMajority(v1, v2, v3)

In this example I have to wait for all 3 votes to be completed, but in fact only two would suffice to achieve majority.
That's why I added "ListEvent" to the DSL above which allow to achieve that but I'm wondering if there is a better/bigger abstraction to put it in.

Thanks!!
Corentin

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Corentin Dupont | 20 Jun 14:59 2014
Picon

Re: Do you recognize this type?

Nobody on that?
What I really want is: a computation that can be interrupted if enough result is already there.
I would be surprise if that concept doesn't exist already somewhere :)


On Thu, Jun 19, 2014 at 5:17 PM, Corentin Dupont <corentin.dupont <at> gmail.com> wrote:
Hi guys,
I am making a DSL for event composition (inspired from digestive-functor & reactive-banana) and I find myself wanting a primitive like that:

-- given a list of events, evaluate the function on those that have already fired.
-- returns an event yelding the result when ready.
ListEvent  :: [Event a] -> ([a] -> Maybe b) -> Event b 


Does this type tell you something? Is there a better abstraction that can encompass it?
My DSL is like that:

-- | Composable events
data Event a where
   SumEvent   :: Event a -> Event a -> Event a        -- The first event to fire will be returned
   AppEvent   :: Event (a -> b) -> Event a -> Event b -- Both events should fire, and then the result is returned
   PureEvent  :: a -> Event a                         -- Create a fake event. The result is useable with no delay.
   EmptyEvent :: Event a                              -- An event that is never fired.
   BaseEvent  :: (Typeable a) => Field a -> Event a   -- Embed a base event


It's easy to define instances for Applicative and Alternative.
But then I have a use case that I cannot solve:
In the case of votations (which use this DSL), sometime you can end prematuraly the voting, even if not everybody voted yet: for example if the majority is already reached.
In this case no need to wait for everybody, we can end the vote.

This does not seem to be possible with Applicative or Monad interfaces: things have to be sequenced in a monad, they cannot be evaluated in parralel.
For example:

do
   v1 <- getVote1
   v2 <- getVote2
   v3 <- getVote3
   evalMajority(v1, v2, v3)

In this example I have to wait for all 3 votes to be completed, but in fact only two would suffice to achieve majority.
That's why I added "ListEvent" to the DSL above which allow to achieve that but I'm wondering if there is a better/bigger abstraction to put it in.

Thanks!!
Corentin


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Chris Warburton | 20 Jun 16:55 2014

Re: Do you recognize this type?

Corentin Dupont <corentin.dupont <at> gmail.com> writes:

> Nobody on that?
> What I really want is: a computation that can be interrupted if enough
> result is already there.
> I would be surprise if that concept doesn't exist already somewhere :)

I'd be surprised if this can be done with Applicative without some
hackery.

Very roughly, we can think of Functors as one-shot actions. For example,
the IO instance of Functor lets us perform exactly 1 side-effect; all we
can do with the result is map pure functions over it.

Applicatives are a static chain of actions. For example, the IO instance
of Applicative lets us chain together any number of side-effecting
actions, but those actions can't alter the chain itself.

Monads are a dynamic chain of actions. They're like Applicatives, but
each action can choose which action to perform next based on the
previous results.

From this perspective, the "shortcut" you're looking for requires the
ability to choose the next action (count another vote or finish
prematurely) based on the previous results (the running total). That's
what Monads are good for, but Applicatives can't do it by themselves.

There's probably an unsafe* way to do this, which will in fact be safe
due to your voting invariant ("if there aren't enough uncounted votes
to change the outcome, the outcome cannot change"). Maybe someone who's
performed similar optimisations can help.

Good luck!

Chris
Corentin Dupont | 20 Jun 17:10 2014
Picon

Re: Do you recognize this type?




On Fri, Jun 20, 2014 at 4:55 PM, Chris Warburton <chriswarbo <at> googlemail.com> wrote:
Corentin Dupont <corentin.dupont <at> gmail.com> writes:

> Nobody on that?
> What I really want is: a computation that can be interrupted if enough
> result is already there.
> I would be surprise if that concept doesn't exist already somewhere :)

I'd be surprised if this can be done with Applicative without some
hackery.

Very roughly, we can think of Functors as one-shot actions. For example,
the IO instance of Functor lets us perform exactly 1 side-effect; all we
can do with the result is map pure functions over it.

Applicatives are a static chain of actions. For example, the IO instance
of Applicative lets us chain together any number of side-effecting
actions, but those actions can't alter the chain itself.

Monads are a dynamic chain of actions. They're like Applicatives, but
each action can choose which action to perform next based on the
previous results.

wow, I *love* this summary! Thanks for that!
 

From this perspective, the "shortcut" you're looking for requires the
ability to choose the next action (count another vote or finish
prematurely) based on the previous results (the running total). That's
what Monads are good for, but Applicatives can't do it by themselves.

Indeed I could make my DSL a monad instance with some changes, that would
be easy to do. But even not a Monad cannot do the trick: imagine if in a country, you were asking
the people to vote one by one, only to interrupt them when the result is known. In fact they have to vote altogether,
in whatever order, and we count the votes as they arrive.

So I think what I need is a sort of Applicative++: not a chain of actions but a set of actions, all independent from each other (so no monad) and with no particular order.


 

There's probably an unsafe* way to do this, which will in fact be safe
due to your voting invariant ("if there aren't enough uncounted votes
to change the outcome, the outcome cannot change"). Maybe someone who's
performed similar optimisations can help.

Good luck!

Chris

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
satvik chauhan | 20 Jun 17:47 2014
Picon

Re: Do you recognize this type?

I might be wrong but what is the problem in folding with the `SumEvent` over all the events?


On Fri, Jun 20, 2014 at 8:40 PM, Corentin Dupont <corentin.dupont <at> gmail.com> wrote:



On Fri, Jun 20, 2014 at 4:55 PM, Chris Warburton <chriswarbo <at> googlemail.com> wrote:
Corentin Dupont <corentin.dupont <at> gmail.com> writes:

> Nobody on that?
> What I really want is: a computation that can be interrupted if enough
> result is already there.
> I would be surprise if that concept doesn't exist already somewhere :)

I'd be surprised if this can be done with Applicative without some
hackery.

Very roughly, we can think of Functors as one-shot actions. For example,
the IO instance of Functor lets us perform exactly 1 side-effect; all we
can do with the result is map pure functions over it.

Applicatives are a static chain of actions. For example, the IO instance
of Applicative lets us chain together any number of side-effecting
actions, but those actions can't alter the chain itself.

Monads are a dynamic chain of actions. They're like Applicatives, but
each action can choose which action to perform next based on the
previous results.

wow, I *love* this summary! Thanks for that!
 

From this perspective, the "shortcut" you're looking for requires the
ability to choose the next action (count another vote or finish
prematurely) based on the previous results (the running total). That's
what Monads are good for, but Applicatives can't do it by themselves.

Indeed I could make my DSL a monad instance with some changes, that would
be easy to do. But even not a Monad cannot do the trick: imagine if in a country, you were asking
the people to vote one by one, only to interrupt them when the result is known. In fact they have to vote altogether,
in whatever order, and we count the votes as they arrive.

So I think what I need is a sort of Applicative++: not a chain of actions but a set of actions, all independent from each other (so no monad) and with no particular order.


 

There's probably an unsafe* way to do this, which will in fact be safe
due to your voting invariant ("if there aren't enough uncounted votes
to change the outcome, the outcome cannot change"). Maybe someone who's
performed similar optimisations can help.

Good luck!

Chris


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Corentin Dupont | 20 Jun 18:11 2014
Picon

Re: Do you recognize this type?

I thinks that's the function asum:
What you obtain is an event that will yield the value of the first event to fire, effectively short-cutting the others!

firstVote = asum [getVote1, getVote2, getVote3]

I need something more or less similar but with a function that can tune exactly when the shortcut will happen.



On Fri, Jun 20, 2014 at 5:47 PM, satvik chauhan <mystic.satvik <at> gmail.com> wrote:
I might be wrong but what is the problem in folding with the `SumEvent` over all the events?


On Fri, Jun 20, 2014 at 8:40 PM, Corentin Dupont <corentin.dupont <at> gmail.com> wrote:



On Fri, Jun 20, 2014 at 4:55 PM, Chris Warburton <chriswarbo <at> googlemail.com> wrote:
Corentin Dupont <corentin.dupont <at> gmail.com> writes:

> Nobody on that?
> What I really want is: a computation that can be interrupted if enough
> result is already there.
> I would be surprise if that concept doesn't exist already somewhere :)

I'd be surprised if this can be done with Applicative without some
hackery.

Very roughly, we can think of Functors as one-shot actions. For example,
the IO instance of Functor lets us perform exactly 1 side-effect; all we
can do with the result is map pure functions over it.

Applicatives are a static chain of actions. For example, the IO instance
of Applicative lets us chain together any number of side-effecting
actions, but those actions can't alter the chain itself.

Monads are a dynamic chain of actions. They're like Applicatives, but
each action can choose which action to perform next based on the
previous results.

wow, I *love* this summary! Thanks for that!
 

From this perspective, the "shortcut" you're looking for requires the
ability to choose the next action (count another vote or finish
prematurely) based on the previous results (the running total). That's
what Monads are good for, but Applicatives can't do it by themselves.

Indeed I could make my DSL a monad instance with some changes, that would
be easy to do. But even not a Monad cannot do the trick: imagine if in a country, you were asking
the people to vote one by one, only to interrupt them when the result is known. In fact they have to vote altogether,
in whatever order, and we count the votes as they arrive.

So I think what I need is a sort of Applicative++: not a chain of actions but a set of actions, all independent from each other (so no monad) and with no particular order.


 

There's probably an unsafe* way to do this, which will in fact be safe
due to your voting invariant ("if there aren't enough uncounted votes
to change the outcome, the outcome cannot change"). Maybe someone who's
performed similar optimisations can help.

Good luck!

Chris


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
David Sorokin | 20 Jun 19:13 2014
Picon

Re: Do you recognize this type?

Hi Corentin,

If I undestand your idea, then it is possible to do with help of continuations wrapped in a monad computation, at least with help of two continuations: (1) the main branch of computation; (2) the immediate cancellation if the result is already known.

The approach is implemented in the F# async workflow (so called the asynchronous computation) and .. in my simulation library Aivika (to model the discontinuous process). Both are monads. Only like the F# developers, I use a plain cancellation without returning the meaningful result, but nothing prevents from returning some data. Also like F# my library supports the third continuation for handling exceptions, namely the IO exceptions in terms of Haskell.

So, the keywords are: canceling the F# asynchronous computation.

Best regards,
David Sorokin


20 июня 2014 г., в 16:59, Corentin Dupont <corentin.dupont <at> gmail.com> написал(а):

Nobody on that?
What I really want is: a computation that can be interrupted if enough result is already there.
I would be surprise if that concept doesn't exist already somewhere :)


On Thu, Jun 19, 2014 at 5:17 PM, Corentin Dupont <corentin.dupont <at> gmail.com> wrote:
Hi guys,
I am making a DSL for event composition (inspired from digestive-functor & reactive-banana) and I find myself wanting a primitive like that:

-- given a list of events, evaluate the function on those that have already fired.
-- returns an event yelding the result when ready.
ListEvent  :: [Event a] -> ([a] -> Maybe b) -> Event b 


Does this type tell you something? Is there a better abstraction that can encompass it?
My DSL is like that:

-- | Composable events
data Event a where
   SumEvent   :: Event a -> Event a -> Event a        -- The first event to fire will be returned
   AppEvent   :: Event (a -> b) -> Event a -> Event b -- Both events should fire, and then the result is returned
   PureEvent  :: a -> Event a                         -- Create a fake event. The result is useable with no delay.
   EmptyEvent :: Event a                              -- An event that is never fired.
   BaseEvent  :: (Typeable a) => Field a -> Event a   -- Embed a base event


It's easy to define instances for Applicative and Alternative.
But then I have a use case that I cannot solve:
In the case of votations (which use this DSL), sometime you can end prematuraly the voting, even if not everybody voted yet: for example if the majority is already reached.
In this case no need to wait for everybody, we can end the vote.

This does not seem to be possible with Applicative or Monad interfaces: things have to be sequenced in a monad, they cannot be evaluated in parralel.
For example:

do
   v1 <- getVote1
   v2 <- getVote2
   v3 <- getVote3
   evalMajority(v1, v2, v3)

In this example I have to wait for all 3 votes to be completed, but in fact only two would suffice to achieve majority.
That's why I added "ListEvent" to the DSL above which allow to achieve that but I'm wondering if there is a better/bigger abstraction to put it in.

Thanks!!
Corentin


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane