pelotom/burrido

Do-notation for JavaScript

burrido's Issues

this works well only for small subset of effects for monads like rx observable

Here is a pretty typical and simple example, say, we need to update DB before some further actions, this is HTTP POST running using promises. Promises may be turned into observable, and JS has no its own side effects:

doMerge(function*() {
  const m = yield fromPromise(updateDb())
  const x = yield from([1,2])
  return `${x} ${m}`
}).subscribe(function(res) {
  console.log(res)
})

This updates DB 4 times!

More details in this gist.
And it is even theoretically not possible, arbitrary monad requires first class continuations, just coroutines are not enough.

There is in fact my tools (sorry for promoting it in this issue, but I suppose it may be interesting) may use same generators syntax for arbitrary monad.

Modeling applicative do

This is really nice, but one thing it leaves to be desired is the ability to applicatively do over independent stages. E.g. if I have:

const t = Fluture.delay(1000).map(_ => 1)
const x = yield t;
const y = yield t;
return x + y

Neither of the expressions bound to x and y are dependent on each other; thus we can use t.map(x => y => x + y).ap(t) rather than t.chain(x => t.chain(y => x + y)), resulting in the whole thing finishing in 1 second rather than 2. In Haskell (which obviously doesn't have to work under the same constraints as this library), do notation now desugars to the former rather than the latter where possible.

I can't see a way of modeling this with generators, thought maybe you might have some ideas.

Typescript definitions

Not an issue per se, I was trying to do the same proof of concept as you did, but for TypeScript.

Wondering how could the generators work so well for Promises (async/await in TS transpiles into generators), but not for any object that has map/flatmap methods. So I encountered the need for cloneable generators, and when googled it, found your project!

Have you ever tried to check if this could work with types?

Complexity of current implementation is too high

@safareli commented on Wed Feb 01 2017

Doing concat on normal js Array has quadratic complexity, plus doing map on the history is linear.
So I belive complexity this far is O(n^2 + n). but this is for nth yield, if i'm correct, using this for some program With n yield, will have complexity of O(n * (n^2 + n)) i.e. O(n^3+n^2). and I think this should be at least noted in readme.

btw the O(n^2 + n) part could be optimised to O(n) by using some some sequence structure which has constant time push (as you push one element only), you could even use normal Lined list for it (List = Nil | Cons a (List a)). this way complexity for some program With n yield will be O(n * n) i.e. O(n^2).

---

@pelotom commented on Wed Feb 01 2017

Doing concat on normal js Array has quadratic complexity,

Hm, I don't think you're right about that. Concatenating 2 arrays of length n and m would be O(n + m), but appending a single element to the end of an array, as we're doing here, is just O(n). Using a cons-list for the history would make appending an element constant time, but because of the map the overall complexity of a single yield would remain O(n).

---

@safareli commented on Wed Feb 01 2017

Correct, so concat will be O(n) + map O(n) so single yield will stay O(n), i.e. we can't fix it.

But I still think that, it should be noted in readme, as users of immutagen and burrido might not be aware of this.

---

@pelotom commented on Wed Feb 01 2017

Quoting from the current README:

Note also that there is inherent inefficiency in this technique, because every yield expression requires replaying the entire history up to that point. For this reason it's advisable to keep expensive computations to a minimum inside immutable generators, particularly as the number of yield expressions in the generator grows. Even if there isn't a lot of expensive computation, the runtime complexity will be quadratic in the number of yield expressions to be evaluated, so be careful.

Is that not sufficiently clear?

---

@safareli commented on Wed Feb 01 2017

didn't saw that in "burrido"

---

@pelotom commented on Wed Feb 01 2017

I'd be happy to review a PR on the burrido repo that adds wording to that effect.