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 Steelemdste...@alum.mit.edu 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 Sun, Jun 5, 2011 at 12:51 PM, KC kc1...@gmail.com 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 Mon, Jun 6, 2011 at 4:05 PM, Casey McCann syntaxgli...@gmail.com 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 Tue, Jun 7, 2011 at 6:14 AM, Casey McCann syntaxgli...@gmail.com wrote: On Mon, Jun 6, 2011 at 7:55 PM, David Barbour dmbarb...@gmail.com 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 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 Mon, Jun 6, 2011 at 9:19 AM, Brent Yorgey byor...@seas.upenn.edu 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 Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey byor...@seas.upenn.edu 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 3:39 PM, Casey McCann syntaxgli...@gmail.com wrote: On Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey byor...@seas.upenn.edu 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 5:32 PM, Matthew Steele mdste...@alum.mit.edu 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
[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
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
