Remove unlawful alternative

[raveclassic]

This PR replaces Alternative instance with Plus instance because Observable does not always satisfy distributivity law. See test for more info.

[gcanti]

This is weird, all the following libraries define an Alternative instance:

• https://github.com/bodil/purescript-observable
• https://github.com/jasonzoladz/purescript-rxjs
• https://github.com/LukaJCB/purescript-rxps

[raveclassic]

Neither of them tests Alternative laws.

The test in this PR shows that distributivity of alt doesn't hold - is it correct or am I missing something?

[gcanti]

@raveclassic does the actual problem stem from the ap implementation which uses combineLatest? I guess should use zip instead

ap: (fab, fa) => zip(fab, fa).pipe(rxMap(([f, a]) => f(a)))

@mlegenhausen what do you think

[raveclassic]

@gcanti Exactly. But I'm not sure what will be the impact of this...

[raveclassic]

If combineLatest is changed to zip, ap test fails

[raveclassic]

Also the following fails:

it('array.sequence', () => {
    const timeline = {
      a: '--a--------|',
      b: '----b------|',
      c: 'c-----d----|',
      r: '----x-y----|'
    }
    new TestScheduler(assert.deepStrictEqual).run(({ cold, expectObservable }) => {
      const fa = cold(timeline.a)
      const fb = cold(timeline.b)
      const fc = cold(timeline.c)
      const fr = array.sequence(R.observable)([fa, fb, fc])
      expectObservable(fr).toBe(timeline.r, { x: ['a', 'b', 'c'], y: ['a', 'b', 'd'] })
    })
  })

And this is how sequence is mostly used for Observables, that's a massive break.

[gcanti]

@raveclassic never mind, zip doesn't behave like I thought

[mlegenhausen]

Definitly a massive break just from a practical standpoint in all the years I have used rxjs I have "almost" never used zip at all. combineLatest is the de facto default combinator in this case and it seems not to be trivial to change from combineLatest to zip.

[raveclassic]

So what is the decision, @gcanti? This is not a breaking change because we still have zero from Plus typeclass, we just relax constraint on alt to not be distributive. Something similar was done for Semigroup/Magma.

[gcanti]

@raveclassic this is a theoretical problem: what's the meaning of = in the Distributivity law?

A.ap(A.alt(fab, gab), fa) = A.alt(A.ap(fab, fa), A.ap(gab, fa))

or, in other words, given two Observable<A>s when we can say that they are equal?

or, in other words, is it possible to define Eq<Observable<A>>?

[mlegenhausen]

given two Observables when we can say that they are equal?

IMHO from a practical point of view it seems only to be relevant that two Oberservable<A>s are equal when the values A are equal at a certain point in time t. Looking at the whole sequence of As from t0 till tcomplete or any other partial sequence is uncommon (Sorry for my missing mathematical precision).

is it possible to define Eq<Observable>

Seems misleading as we can't define it for Task neither 😉 but I know what you meant.

we can't define it for Task

@mlegenhausen well, actually we can, the trivial one

import { Eq } from 'fp-ts/lib/Eq'
import { constTrue } from 'fp-ts/lib/function'
import { Task } from 'fp-ts/lib/Task'

export function getEq<A>(): Eq<Task<A>> {
  return { equals: constTrue }
}

[raveclassic]

I'd say that two observables are equal if values, time (discrete according to some virtual scheduler, like marbles) and order of their events are equal on a certain fixed time period of observation. The same applies for Task although we don't test the time of its value because we have no virtual scheduler.

[mlegenhausen]

@raveclassic so cold('-a--') != cold('--a-')?

[raveclassic]

If both are subscribed in a single moment (the first -), then yes, they are different in the way they produce values (being cold). The period of observation should be the same (no shifts) for all observables.

[gcanti]

The same applies for Task although we don't test the time of its value because we have no virtual scheduler

This doesn't seem right as equality, Task is useful precisely because may yield different values.

Let's say you define a Task<Weather> which fetches weather infos, and then you run it two times, today and tomorrow

const fetchWeather: Task<Weather> = ...

const today = fetchWeather
...
today()

// later...
const tomorrow = fetchWeather
...
tomorrow()

You likely get different data but how is it possible that tomorrow != today when tomorrow === today (i.e. they even relate to the same value in memory)? All Task<Weather> must be equal.

I'm not saying that is not useful to reason about what happens after you run a task (or subscribe to an observable), but that's a slippery slope. Is what actually happens at runtime related to the meaning of = and/or to the laws? This does seem arguable.

TLDR: IMO you can't define an Eq based on the runtime behavior

[raveclassic]

I'm not a pro in the field of FRP, but Task (and Observable) are time-dependent computations which means they may produce different values if run in different time. This explains why today === tomorrow but today() !== tomorrow(). The time is an implicit dependency. If it was explicit then we would define Task as type Task<A> = (t: number) => Promise<A>. Then it would totally make sense that

const today = Date.now();
const tomorrow = today + 1000 * 60 * 60 * 24;
fetchWeather(today) !== fetchWeather(tomorrow);

Related (but out of scope): I'm studying this paper and it introduces a so called "Now"-computation being essentially an explicit way to declare dependency on time. There's also a library implementing that concept: https://github.com/funkia/hareactive#now

[mlegenhausen]

type Task<A> = (t: number) => Promise<A>

Thats not the signature of Task what you mean is type Forecast = (t: number) => () => Promise<Weather>.

I think this is important, cause the computation behind it is the same Task<Weather>. So I currently don't know if we could decide if these computations are equal by just looking on its outcome (of type Task<Weather>, not the outcome of the Promise), cause my naive approach would be to use eqStrict but this will fail cause we create new references which could do logically the same?

[raveclassic]

Thats not the signature of Task

It doesn't really matter. We can describe type Task<A> = IO<Promise<A>> which tracks that the computation should be "invoked" (that () call). We can however say that the computation is "invokable" in a specific moment of time so that it produces a type Behavior<A> = (t: Time) => A: type Task<A> = Behavior<Promise<A>>. This reflects that starting in different moments in time the task produces different promises (different values). Finally we would declare type Forcast = Task<Weather>. But to run such computation we would need to find the current moment in time:

declare const forecast: Forecast<Weather>;
const nowForecast = forecast(performance.now());

The same as we would do for usual Task:

declare const forecast: IO<Promise<Weather>>;
const nowForecast = forecast(); // <-- time is implicit here

I do not insist on introducing these concepts but IMO they describe what happens in the most accurate way.

---

To be honest, eqStrict often fails. But I see what you mean, we cannot define an Eq for Promise. Specifically because it has implicit time dependency :) If it was smth like type Promise<A> = (t: Time) => Option<A> we would just memoize it with t argument. Then we would produce the same reference for equal time arguments (omitting memory). Going further if we had a scheduler virtualising time we would just instantly run the timeline of our observation period (subscribe/unsubscribe) with some discrete notion of time and check if occurrences of two promise results are equal.

---

Summing up, Task and Observable conceptually are the same. Even more, if underlying Promise (implementation detail actually) was lazy, they would even have the same signatures: Promise#then is Observable#subscribe.

[raveclassic]

Take a look at the Eq<Observable<A>> in the PR:

const liftE = <A>(E: Eq<A>): Eq<Observable<A>> => {
  const arrayE = getEq(E)
  return {
    equals: (x, y) => {
      const scheduler = new TestScheduler(assert.deepStrictEqual)
      const xas: Array<A> = []
      x.pipe(subscribeOn(scheduler)).subscribe(a => xas.push(a))
      const yas: Array<A> = []
      y.pipe(subscribeOn(scheduler)).subscribe(a => yas.push(a))
      scheduler.flush() // <-------- run the timeline
      assert.deepStrictEqual(xas, yas)
      return arrayE.equals(xas, yas)
    }
  }
}

The same could be done for Promise if we could change the underlying scheduling. Here we don't check the time of event occurrence because I haven't found the way to get it :D. Need to check what TestScheduler API provides once again.

[mlegenhausen]

Sorry my fault.

[gcanti]

@raveclassic you can't define an Eq instance based on side effect execution.

IO, Task, Observable... they are all just values, you can think of them as recipes for the runtime. And the runtime is something you must consider out of reach.

import { IO } from 'fp-ts/lib/IO'

let counter = 0

const increment: IO<number> = () => counter++

How can you define an Eq instance for IO<number>?

This is not possible:

import { Eq } from 'fp-ts/lib/Eq'

const eq: Eq<IO<number>> = {
  equals: (x, y) => x() === y() // <= you can't run the side effects here
}

Here's another possible implementation of increment as a simple value, a recipe for the runtime (i.e. The Great Interpreter Of All Side Effects)

class IO<A> {
  readonly A: A
  readonly type: 'IO'
}

class Increment extends IO<number> {
  readonly what_to_do = 'please increment the counter'
}

class Decrement extends IO<number> {
  readonly what_to_do = 'please decrement the counter'
}

// other IO recipes...

const increment: IO<number> = new Increment()

let counter = 0

function interpreter<A>(recipe: IO<A>) {
  if (recipe instanceof Increment) {
    counter++
  } else if ( ... ) {

  }
}

All Increment instances are equal.

You can consider fp-ts's IO

type IO<A> = () => A

as a recipe with its own little, specific interpreter packed together.

However only the runtime is allowed to execute these recipes.

[raveclassic]

@gcanti Well... Makes sense :/

Ok. How can we check the laws safely and correctly for #27 ?

[anilanar]

We cannot prove laws of observables (the way proofs work in category theory) if we don't lawfully implement the observables ourselves. We are choosing to not implement observables ourselves so we must assume that observables is a black box. Even if we implemented observables ourselves, proving laws can be quite challenging; depending on how complex the implementation is.

So because we cannot prove the laws, we can brute force it by using runtime equality and running it for infinite cases. Or we can use a heuristic to predict correctness of laws by using runtime equality for a few edge cases (that we think are edgy). When runtime equality is not an option (e.g. functions cannot have Eq), there isn't much to do but predict based on gut feelings?

Proving wrong is perhaps simpler. Find a counter example.

Note: Keep in mind that runtime equality can give false negatives/positives as @gcanti noted unless runtime equality is based on lossless serialization of the data, assuming the data is serializable.