Seq issues on left associated chains

[safareli]

Current Is stack safe test assocaites chain to right, which in general, has good performance, and as ChainRec is used to fold we don't have stack issue. But if we associate chain to left then:

1. As we use function for composition (kcompose) and the stack overflows
2. if we decrease number of chains to MAX_STACK/2 for example, it takes 32s to compute result, i.e. complexity is quadratic

References for possible fix:

• Relection without Remorse as in purescript-free
• My article Stack safe Function composition is also related.

In general we need some efficient sequence structure to collect kleisli arrows, and do something like Par.fold here as well.

test('Is stack safe left associated', t => {
  const runTimes = (n) => {
    let acc = Seq.lift(0)
    for (let i = 0; i < n; i++) {
      acc = acc.chain(Seq.lift)
    }
    return acc
  }
  runTimes(MAX_STACK).foldSeq(Future.of, Future).fork(t.error, (v) => t.equals(v, 0, 'Works with Future'))
  t.equals(runTimes(MAX_STACK).hoistSeq(id).foldSeq(Identity.of, Identity).get(), 0, 'is Seq stack safe')
  t.equals(runTimes(MAX_STACK).foldSeq(Identity.of, Identity).get(), 0, 'Works with Identity')

  t.end()
})

[safareli]

This we can refactor fold this way but laws fail as we use equals which checks structural equality, if we change it to something which checks if result of fold on a and b is equal then we can use this diff

diff --git a/src/seq.js b/src/seq.js
index f229d07..f7c5c89 100644
--- a/src/seq.js
+++ b/src/seq.js
@@ -41,31 +41,29 @@ Object.assign(Seq.prototype, patch({
   },
   // :: Seq f a ~> (a -> Seq f b) -> Seq f b
   chain(f) {
-    // this way in Roll.x we don't have any `Pure` node
-    if (Pure.is(this)) {
-      return f(this.a)
-    }
     return Roll(this, f)
   },
   // :: (Monad m, ChainRec m) => Seq f a ~> (Ɐ x. f x -> m x, TypeRep m) -> m a
   foldSeq(f, T) {
     return chainRec(T, (next, done, { focus, stack }) => {
-      while (Pure.is(focus) && stack.length) {
-        const fn = stack.pop()
-        focus = fn(focus.a)
-      }
-      if (Pure.is(focus)) {
-        return of(T, done(focus.a))
-      }
-      while (Roll.is(focus)) {
-        // We are mutating `stack` for performance reasons but it's not
-        // an issue as it's not an observable side effects 8-)
-        // If we wanted to do same in a staticly typed language,
-        // some kind of efficient type aligned sequnce should be used.
-        stack.push(focus.y)
-        focus = focus.x
+      // We are mutating `stack` for performance reasons but it's not
+      // an issue as it's not an observable side effects 8-)
+      // If we wanted to do same in a pure and staticly typed language,
+      // some kind of efficient type aligned sequnce should be used.
+      while (!Lift.is(focus)) {
+        if (Pure.is(focus)) {
+          if (stack.length) {
+            const fn = stack.pop()
+            focus = fn(focus.a)
+          } else {
+            return of(T, done(focus.a))
+          }
+        }
+        if (Roll.is(focus)) {
+          stack.push(focus.y)
+          focus = focus.x
+        }
       }
-      // here `focus` must be `Lift`
       return map((v) => {
         if (stack.length === 0) {
           return done(v)