Open polytypic opened 5 years ago
Yeah, I'm still not sure what is the right call here. I don't use Static or Fantasy Land in anything real, it always was experimental/academic for me. So it's hard to tell what is the best solution from the practical point of view.
We could expose two modules, but that would complicate things. On the other hand, the single module is not quite correct.
One of the reasons why I did a single module initially is that the sequential ap
(based on flatMap
) seems pretty useless in the case of streams. It would spawn a second stream for each event in the first, and third for each event in a second, and so on. Basically, you get a lot of duplicate events, and the number of duplicates will grow after each event from the first stream. I can't imagine an example where this could be useful.
@polytypic I'm not sure I agree that ap
should have sequential semantics. Part of the purpose of Apply
is to have an option for parallel operations. I don't know what would be the right authoritative source to cite so I will cite a few sources:
Monads describe dependent computations and Applicatives describe independent computations.
https://typelevel.org/cats/typeclasses/parallel.html
Or, if you prefer — [monads] can work in series, whereas applicatives work in parallel.
https://hackernoon.com/functors-and-applicatives-b9af535b1440
Applicative functors provide a way to take two computations and join them together using a function. The Traversable example highlights how two collections can be parallelized into pairs. Applicative functors and parallel processing go together like bread and butter.
That's a quote from "Scala in Depth" by Josh Suereth, discussed here: https://stackoverflow.com/questions/12184373/how-do-applicative-functors-tie-in-with-parallelizing-algorithms-scala-and-sca
On the other hand I found this comment on Reddit that argues that an implementer should maybe consider making an Apply
instance sequential for types that implement Monad
:
If you have an Applicative, you shouldn’t assume anything about the order of effects. If you are defining an Applicative (instance), you are free to perform effects in whatever order you want because no client can assume an order.
However, if you are planning on writing a Monad instance for the type for which you are writing an Applicative instance, then you need to think carefully. The effects associated with Monads do have an order that a client can depend on (due to the possibility of data dependence), and making Applicative and Monad instances for the same type agree on effect ordering is customary.
This reasoning wraps back around at this point. If you have a particular Applicative for which you know there is a Monad (such as IO), custom lets you assume the effects will be evaluated left-to-right so as to be compatible with the Monad instance.
In summary, you should think of any Applicative you are given as potentially evaluating effects in parallel, but if you’re on the other side of the implementation and want effects to actually run in parallel, you should reconsider defining a Monad instance for the same type so that clients can reason about effects based on the concrete type.
Replies to that comment point out some counterexamples.
There is also a discussion of "sequencing of effects" in Haskell on Wikibooks that sheds some light on the issue. The gist is that the result of ap
in a case where inputs may represent multiple values (as is the case with Observable) is implementation-dependent.
https://en.wikibooks.org/wiki/Haskell/Applicative_functors#Sequencing_of_effects
My interpretation of what I have read is that there is no absolute rule about the relationship between ap
and chain
. I think that the implementation of ap
should be determined by use cases that are likely to be most useful, and results that are likely to be least surprising.
@rpominov
I don't use Static or Fantasy Land in anything real, it always was experimental/academic for me.
That is entirely acceptable. I do use Static Land in real projects that are in production.
We could expose two modules, but that would complicate things. On the other hand, the single module is not quite correct.
Yes, having more modules is more complex in a sense. However, sometimes there is essential complexity that must not go away.
I can't imagine an example where this could be useful.
I'll give you a pair of interconnected examples. First of all, according to the laws, the functions (written in naïve style for clarity)
const sequenceA = (A, ops) =>
A.ap(A.map(R.prepend, R.head(ops)), sequenceA(A, R.tail(ops)))
const sequenceM = (M, ops) =>
M.chain(
h => M.map(R.prepend(h), sequenceM(M, R.tail(ops)),
R.head(ops)
)
are equivalent (with respect to sequencing of effects) for every Monad M
:
sequenceA(M, ops) === sequenceM(M, ops)
An application of the laws that relate algebraic structure to each other is the ability to refactor expressions between various equivalent forms. Of the above two definitions for sequencing, the former is preferable, because it is more polymorphic. It works not just for every applicative, but for every monad as well, while the latter version only works for monads.
Now, let's think of a more concrete example: simple sequential asynchronous programming. As hinted in those slides, observables can be used for such programming. The gist is that each observable in such a "mode of use of observables" emits at most one value. (This way the duplication of events does not happen.) However, if you'd use the law-breaking Observable
instance with sequenceA
to sequence an array of asynchronous effects, you'd get (the wrong) parallel behavior instead of the desired sequential behavior. (This isn't just academic, a colleague recently mentioned using some async (Task/Future) library (I think it was Fantasy Land based) where the ap
definition was changed from sequential to parallel (I suppose to "make it more practical") and that broke their use of sequence
.)
@hallettj
I'm not sure I agree that ap should have sequential semantics.
Note that my point isn't that ap
should have sequential semantics—quite the contrary actually. My point is that in the definition of a monad, the semantics of ap
should agree with the semantics of chain
as specified in the Static Land spec. The Static Land specification is based on corresponding specifications of monads and applicatives found in other libraries, languages, and literature.
So, instead of having one broken Observable
module, I'm suggesting that there should rather be multiple correct modules corresponding to different ways to compose (or different modes of use of) observables. And, indeed, there are many fundamentally different ways to use observables.
My interpretation of what I have read is that there is no absolute rule about the relationship between ap and chain.
As mentioned above, the Static Land spec gives such a rule.
One basis for the rule is simply that every monad gives rise to an applicative via the definition given e.g. in Joseph Abrahamson's SO answer:
ap :: Monad m => m (a -> b) -> m a -> m b
ap mf ma = do
f <- mf
a <- ma
return (f a)
As also discussed in Abrahamson's answer, there are cases where an applicative instance cannot have a corresponding monad instance.
Another basis is given in a discussions on sequencing of effects, which boils down to:
The convention in Haskell is to always implement (<*>) and other applicative operators using left-to-right sequencing.
Hm, right, in the case of one-value observables sequential ap
might make sense indeed.
Let's discuss how exactly we could fix this. I think we shouldn't change Kefir.staticLand.Observable
, maybe just add a note in the documentation about its flaw. Instead we could add new modules, say Kefir.staticLand.ObservableMonad
and Kefir.staticLand.ObservableApplicative
. Not sure about the names, and what exactly we should do about the methods: should we just omit ap
in ObservableMonad
, omit chain
in ObservableApplicative
, and copy all the rest from Observable
?
Like a comment in the current definition says, the definition is wrong:
I can see the "good intention" behind the above definition, but a major advantage of Static Land is precisely the fact that for a single type you can simply have as many different algebra module instances as needed:
Observables support multiple different algebras. For example, basically every
flatMapXXX
operation induces a Monad with different semantics. With Static Land, each of those can be supported as different algebra modules (all of them fully correct) from which the user can then pick and choose the appropriate one depending on which semantics are needed.So, why is the above definition wrong? Because it breaks the sequential semantics of the chain. Let's say that you wish to perform a sequence of, say, database operations using the
Observable
definition. You should be able to do that with an applicativesequence
function, but now you cannot, because the above definition executes the operations in parallel, rather than sequentially.Of course, another major advantage of Static Land is that this issue can be worked around simply by providing the proper algebra modules outside of the library core.