Static Land interop `Observable` definition is wrong

[polytypic]

Like a comment in the current definition says, the definition is wrong:

  // This ap strictly speaking incompatible with chain. If we derive ap from chain we get
  // different (not very useful) behavior. But spec requires that if method can be derived
  // it must have the same behavior as hand-written method. We intentionally violate the spec
  // in hope that it won't cause many troubles in practice. And in return we have more useful type.
  ap(obsFn, obsVal) {
    return combine([obsFn, obsVal], (fn, val) => fn(val))
  },

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:

• We can implement many modules for one type, therefore we can have more than one instance of the same Algebra for a single type. For example, we can implement two Monoids for numbers: Addition and Multiplication.

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 applicative sequence 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.

[rpominov]

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.

[hallettj]

@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.

https://www.reddit.com/r/haskell/comments/381o9y/does_applicative_have_an_inherent_notion_of_order/crrmnmr/

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.

[polytypic]

@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.)

[polytypic]

@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.

[rpominov]

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?