Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Tue, Jun 7, 2011 at 6:14 AM, Casey McCann wrote: > On Mon, Jun 6, 2011 at 7:55 PM, David Barbour wrote: > > Earlier forms of my reactive demand programming model [1] - before I > > switched to arrows - would qualify. The model has limited side-effects > (e.g. > > power a camera on only when someone is observing it) so we cannot use > > branchApplicative. The reactivity requires continuously weaving the two > > branches over time and recombining the results, which is distinct from > > branchMonad. > > Oh, very nice, thank you. I'd actually suspected that models of > reactive behavior might be a case where the distinction is meaningful. > I do still wonder if there's something roughly equivalent to the > (grossly inefficient and unusable, but producing the same results > otherwise) monad instance for zipping infinite streams, but I don't > have time to work through it right now to be sure... > The main trouble with using monads directly is that they're simply too powerful. Monads allow ad-hoc joins and loops based on data. The number of reactive relationships during any given instant can vary widely and unpredictably based on data. This makes it difficult to maintain stable relationships over continuous time. Looping and Branching must be carefully managed in my reactive model in order to gain stability over time that Monads do not possess. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Mon, Jun 6, 2011 at 4:05 PM, Casey McCann wrote: > ArrowChoice and ArrowApply are conceptually distinct and I expect > there are instances of the former that have no possible instance for > the latter. Branching vs. Monad I am much less certain of. > For a real-time or embedded DSL, or hardware modeling, you could easily desire 'Branching' and limited 'Loop' classes while rejecting the full power of Monads. > some type that's not obviously equivalent to one of these definitions: > branchMonad mb t f = do { b <- mb; if b then t else f } > branchApplicative = liftA3 (\b t f -> if b then t else f) > Earlier forms of my reactive demand programming model [1] - before I switched to arrows - would qualify. The model has limited side-effects (e.g. power a camera on only when someone is observing it) so we cannot use branchApplicative. The reactivity requires continuously weaving the two branches over time and recombining the results, which is distinct from branchMonad. [1] http://awelonblue.wordpress.com/2011/05/21/comparing-frp-to-rdp/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Sun, Jun 5, 2011 at 12:51 PM, KC wrote: > If new intermediate classes crop up then there would be no point in fixing > > class (Applicative m) => Monad m where > > since it would have to be changed if new intermediate classes are found. > You might check out a few articles regarding Kleisli arrows [1][2] for possibilities that live between applicative and monad. Applicative itself is also a little on the strong side. I had to reject Applicative for one model of signal transformers because 'pure' was not a legal constructor, even though 'fmap . const' and '<*>' were okay. And even Functor is too strong if you want effective linearity. I've found Adam Megacz's Generalized Arrows [3] to be a suitable chassis for weaker models. [1] http://www.haskell.org/haskellwiki/Arrow_tutorial#Kleisli_Arrows [2] http://lambda-the-ultimate.org/node/4273 [3] http://www.cs.berkeley.edu/~megacz/garrows/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On 6/6/11 7:05 PM, Casey McCann wrote: On Mon, Jun 6, 2011 at 5:32 PM, Matthew Steele wrote: branchApplicative = liftA3 (\b t f -> if b then t else f) This definition doesn't satisfy the laws given for the Branching class; it will execute the effects of both branches regardless of which is chosen. How would it violate the laws for Identity or Reader? It wouldn't violate the laws for those (or other benign effects, given a suitable definition of "benign"), but it'd clearly violate the laws for things like Writer, ST, IO,... -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Mon, Jun 6, 2011 at 5:32 PM, Matthew Steele wrote: > I think Branching is to Monad what ArrowChoice is to ArrowApply. > Branching allows the shape of the computation to depend on run-time > values (which you can't do with Applicative), but still allows only a > finite number of computation paths. By purposely making a functor an > instance of Branching but _not_ of Monad, you allow it to have some > amount of run-time flexibility while still retaining the ability to > "statically" analyze the effects of a computation in that functor. Yes, that's what I gathered as well. It's a straightforward concept. My question is whether there exist instances of Branching that are distinct in results from an implementation in terms of a Monad instance, rather than merely allowing a more efficient implementation. Not that the latter isn't worthwhile, but to make a case for something like Branching as an intermediate between Applicative and Monad one would expect it to differ from both in what types have possible instances. ArrowChoice and ArrowApply are conceptually distinct and I expect there are instances of the former that have no possible instance for the latter. Branching vs. Monad I am much less certain of. >> branchApplicative = liftA3 (\b t f -> if b then t else f) > > This definition doesn't satisfy the laws given for the Branching > class; it will execute the effects of both branches regardless of > which is chosen. How would it violate the laws for Identity or Reader? - C. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Mon, Jun 6, 2011 at 3:39 PM, Casey McCann wrote: > On Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey wrote: >> The idea is that Applicative computations >> have a fixed structure which is independent of intermediate results; >> Monad computations correspond to (potentially) infinitely branching >> trees, since intermediate results (which could be of an infinite-sized >> type) can be used to compute the next action; but Branching >> computations correspond to *finitely* branching trees, since future >> computation can depend on intermediate results, but only one binary >> choice at a time. > > Is this truly an intermediate variety of structure, though? Or just > different operations on existing structures? With Applicative, there > are examples of useful structures that truly can't work as a Monad, > the usual example being arbitrary lists with liftA2 (,) giving zip, > not the cartesian product. Do you know any examples of both: > > 1) Something with a viable instance for Branching, but either no Monad > instance, or multiple distinct Monad instances compatible with the > Branching instance I think Branching is to Monad what ArrowChoice is to ArrowApply. Branching allows the shape of the computation to depend on run-time values (which you can't do with Applicative), but still allows only a finite number of computation paths. By purposely making a functor an instance of Branching but _not_ of Monad, you allow it to have some amount of run-time flexibility while still retaining the ability to "statically" analyze the effects of a computation in that functor. > branchApplicative = liftA3 (\b t f -> if b then t else f) This definition doesn't satisfy the laws given for the Branching class; it will execute the effects of both branches regardless of which is chosen. Cheers, -Matt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey wrote: > The idea is that Applicative computations > have a fixed structure which is independent of intermediate results; > Monad computations correspond to (potentially) infinitely branching > trees, since intermediate results (which could be of an infinite-sized > type) can be used to compute the next action; but Branching > computations correspond to *finitely* branching trees, since future > computation can depend on intermediate results, but only one binary > choice at a time. Is this truly an intermediate variety of structure, though? Or just different operations on existing structures? With Applicative, there are examples of useful structures that truly can't work as a Monad, the usual example being arbitrary lists with liftA2 (,) giving zip, not the cartesian product. Do you know any examples of both: 1) Something with a viable instance for Branching, but either no Monad instance, or multiple distinct Monad instances compatible with the Branching instance 2) Same as above, except for a viable Applicative instance without a single obvious Branching instance In other words, an implementation of branch for some type that's not obviously equivalent to one of these definitions: branchMonad mb t f = do { b <- mb; if b then t else f } branchApplicative = liftA3 (\b t f -> if b then t else f) I can certainly believe that such an example exists, but I can't think of one. In particular, it doesn't seem to be possible for ZipList (the obvious almost-instance does not quite do what you may think it does). If memory serves me, sometimes the limited nature of Applicative allows a more efficient implementation than Monad, and in such cases I can easily believe that branch could be made more efficient than the generic form based on Monad. But that's not terribly persuasive for creating a type class, I don't think. - C. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Mon, Jun 6, 2011 at 9:19 AM, Brent Yorgey wrote: > On Sun, Jun 05, 2011 at 12:51:47PM -0700, KC wrote: >> If new intermediate classes crop up then there would be no point in fixing >> >> class (Applicative m) => Monad m where >> >> since it would have to be changed if new intermediate classes are >> found. > > There actually is at least one intermediate class that I know of, > > class Applicative m => Branching m where > branch :: m Bool -> m a -> m a -> m a > > subject to the laws > > branch (m *> pure True) t f == m *> t > branch (m *> pure False) t f == m *> f > > or something like that. The idea is that Applicative computations > have a fixed structure which is independent of intermediate results; > Monad computations correspond to (potentially) infinitely branching > trees, since intermediate results (which could be of an infinite-sized > type) can be used to compute the next action; but Branching > computations correspond to *finitely* branching trees, since future > computation can depend on intermediate results, but only one binary > choice at a time. > > However, I doubt this qualifies as "useful" no matter how you define > it, although I would not be sad to be proven wrong. In any case, I > think it is ethically indefensible to procrastinate in doing something > good just in case you might miss an opportunity to do something > perfect later. > > -Brent > I take it you would prefer the following signature class (Applicative m) => Monad m where -- -- Regards, KC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On Sun, Jun 05, 2011 at 12:51:47PM -0700, KC wrote: > If new intermediate classes crop up then there would be no point in fixing > > class (Applicative m) => Monad m where > > since it would have to be changed if new intermediate classes are > found. There actually is at least one intermediate class that I know of, class Applicative m => Branching m where branch :: m Bool -> m a -> m a -> m a subject to the laws branch (m *> pure True) t f == m *> t branch (m *> pure False) t f == m *> f or something like that. The idea is that Applicative computations have a fixed structure which is independent of intermediate results; Monad computations correspond to (potentially) infinitely branching trees, since intermediate results (which could be of an infinite-sized type) can be used to compute the next action; but Branching computations correspond to *finitely* branching trees, since future computation can depend on intermediate results, but only one binary choice at a time. However, I doubt this qualifies as "useful" no matter how you define it, although I would not be sad to be proven wrong. In any case, I think it is ethically indefensible to procrastinate in doing something good just in case you might miss an opportunity to do something perfect later. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
On 06/06/2011, at 5:51 , KC wrote: > If new intermediate classes crop up then there would be no point in fixing > > class (Applicative m) => Monad m where > > since it would have to be changed if new intermediate classes are found. > > I realize non-existence proofs are hard. Not as hard as formalising "useful". Ben. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?
If new intermediate classes crop up then there would be no point in fixing class (Applicative m) => Monad m where since it would have to be changed if new intermediate classes are found. I realize non-existence proofs are hard. -- -- Regards, KC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe