text: "use strict";
  var __createBinding = (this && this.__createBinding) || (Object.create ? (function(o, m, k, k2) {
      if (k2 === undefined) k2 = k;
      Object.defineProperty(o, k2, { enumerable: true, get: function() { return m[k]; } });
  }) : (function(o, m, k, k2) {
      if (k2 === undefined) k2 = k;
      o[k2] = m[k];
  }));
  var __setModuleDefault = (this && this.__setModuleDefault) || (Object.create ? (function(o, v) {
      Object.defineProperty(o, "default", { enumerable: true, value: v });
  }) : function(o, v) {
      o["default"] = v;
  });
  var __importStar = (this && this.__importStar) || function (mod) {
      if (mod && mod.__esModule) return mod;
      var result = {};
      if (mod != null) for (var k in mod) if (k !== "default" && Object.prototype.hasOwnProperty.call(mod, k)) __createBinding(result, mod, k);
      __setModuleDefault(result, mod);
      return result;
  };
  Object.defineProperty(exports, "__esModule", { value: true });
  exports.intersperse = exports.prependToAll = exports.unzip = exports.zip = exports.zipWith = exports.sort = exports.lefts = exports.rights = exports.reverse = exports.modifyAt = exports.deleteAt = exports.updateAt = exports.insertAt = exports.findLastIndex = exports.findLastMap = exports.findLast = exports.findFirstMap = exports.findFirst = exports.findIndex = exports.dropLeftWhile = exports.dropRight = exports.dropLeft = exports.spanLeft = exports.takeLeftWhile = exports.takeRight = exports.takeLeft = exports.init = exports.tail = exports.last = exports.head = exports.snoc = exports.cons = exports.lookup = exports.isOutOfBound = exports.isNonEmpty = exports.isEmpty = exports.scanRight = exports.scanLeft = exports.foldRight = exports.foldLeft = exports.flatten = exports.replicate = exports.range = exports.makeBy = exports.getOrd = exports.getEq = exports.getMonoid = exports.getShow = exports.toArray = exports.fromArray = void 0;
  exports.FunctorWithIndex = exports.Functor = exports.URI = exports.unfold = exports.wilt = exports.wither = exports.traverseWithIndex = exports.sequence = exports.traverse = exports.reduceRightWithIndex = exports.reduceRight = exports.reduceWithIndex = exports.foldMap = exports.reduce = exports.foldMapWithIndex = exports.duplicate = exports.extend = exports.filterWithIndex = exports.partitionMapWithIndex = exports.partitionMap = exports.partitionWithIndex = exports.partition = exports.compact = exports.filterMap = exports.filterMapWithIndex = exports.filter = exports.separate = exports.mapWithIndex = exports.map = exports.chainFirst = exports.chainWithIndex = exports.chain = exports.apSecond = exports.apFirst = exports.ap = exports.alt = exports.altW = exports.zero = exports.of = exports.difference = exports.intersection = exports.union = exports.comprehension = exports.chunksOf = exports.splitAt = exports.chop = exports.sortBy = exports.uniq = exports.elem = exports.rotate = void 0;
  exports.apS = exports.bind = exports.bindTo = exports.Do = exports.some = exports.every = exports.empty = exports.unsafeDeleteAt = exports.unsafeUpdateAt = exports.unsafeInsertAt = exports.readonlyArray = exports.Witherable = exports.TraversableWithIndex = exports.Traversable = exports.FoldableWithIndex = exports.Foldable = exports.FilterableWithIndex = exports.Filterable = exports.Compactable = exports.Extend = exports.Alternative = exports.Alt = exports.Unfoldable = exports.Monad = exports.Applicative = void 0;
  var function_1 = require("./function");
  var O = __importStar(require("./Option"));
  var Ord_1 = require("./Ord");
  // -------------------------------------------------------------------------------------
  // model
  // -------------------------------------------------------------------------------------
  /**
   * @category constructors
   * @since 2.5.0
   */
  // tslint:disable-next-line: readonly-array
  function fromArray(as) {
      var l = as.length;
      if (l === 0) {
          return exports.empty;
      }
      var ras = Array(l);
      for (var i = 0; i < l; i++) {
          ras[i] = as[i];
      }
      return ras;
  }
  exports.fromArray = fromArray;
  /**
   * @category destructors
   * @since 2.5.0
   */
  // tslint:disable-next-line: readonly-array
  function toArray(ras) {
      var l = ras.length;
      var as = Array(l);
      for (var i = 0; i < l; i++) {
          as[i] = ras[i];
      }
      return as;
  }
  exports.toArray = toArray;
  /**
   * @category instances
   * @since 2.5.0
   */
  function getShow(S) {
      return {
          show: function (as) { return "[" + as.map(S.show).join(', ') + "]"; }
      };
  }
  exports.getShow = getShow;
  var concat = function (x, y) {
      var lenx = x.length;
      if (lenx === 0) {
          return y;
      }
      var leny = y.length;
      if (leny === 0) {
          return x;
      }
      var r = Array(lenx + leny);
      for (var i = 0; i < lenx; i++) {
          r[i] = x[i];
      }
      for (var i = 0; i < leny; i++) {
          r[i + lenx] = y[i];
      }
      return r;
  };
  /**
   * Returns a `Monoid` for `ReadonlyArray<A>`
   *
   * @example
   * import { getMonoid } from 'fp-ts/ReadonlyArray'
   *
   * const M = getMonoid<number>()
   * assert.deepStrictEqual(M.concat([1, 2], [3, 4]), [1, 2, 3, 4])
   *
   * @category instances
   * @since 2.5.0
   */
  function getMonoid() {
      return {
          concat: concat,
          empty: exports.empty
      };
  }
  exports.getMonoid = getMonoid;
  /**
   * Derives an `Eq` over the `ReadonlyArray` of a given element type from the `Eq` of that type. The derived `Eq` defines two
   * arrays as equal if all elements of both arrays are compared equal pairwise with the given `E`. In case of arrays of
   * different lengths, the result is non equality.
   *
   * @example
   * import { eqString } from 'fp-ts/Eq'
   * import { getEq } from 'fp-ts/ReadonlyArray'
   *
   * const E = getEq(eqString)
   * assert.strictEqual(E.equals(['a', 'b'], ['a', 'b']), true)
   * assert.strictEqual(E.equals(['a'], []), false)
   *
   * @category instances
   * @since 2.5.0
   */
  function getEq(E) {
      return {
          equals: function (xs, ys) { return xs === ys || (xs.length === ys.length && xs.every(function (x, i) { return E.equals(x, ys[i]); })); }
      };
  }
  exports.getEq = getEq;
  /**
   * Derives an `Ord` over the `ReadonlyArray` of a given element type from the `Ord` of that type. The ordering between two such
   * arrays is equal to: the first non equal comparison of each arrays elements taken pairwise in increasing order, in
   * case of equality over all the pairwise elements; the longest array is considered the greatest, if both arrays have
   * the same length, the result is equality.
   *
   * @example
   * import { getOrd } from 'fp-ts/ReadonlyArray'
   * import { ordString } from 'fp-ts/Ord'
   *
   * const O = getOrd(ordString)
   * assert.strictEqual(O.compare(['b'], ['a']), 1)
   * assert.strictEqual(O.compare(['a'], ['a']), 0)
   * assert.strictEqual(O.compare(['a'], ['b']), -1)
   *
   *
   * @category instances
   * @since 2.5.0
   */
  function getOrd(O) {
      return Ord_1.fromCompare(function (a, b) {
          var aLen = a.length;
          var bLen = b.length;
          var len = Math.min(aLen, bLen);
          for (var i = 0; i < len; i++) {
              var ordering = O.compare(a[i], b[i]);
              if (ordering !== 0) {
                  return ordering;
              }
          }
          return Ord_1.ordNumber.compare(aLen, bLen);
      });
  }
  exports.getOrd = getOrd;
  /**
   * Return a list of length `n` with element `i` initialized with `f(i)`
   *
   * @example
   * import { makeBy } from 'fp-ts/ReadonlyArray'
   *
   * const double = (n: number): number => n * 2
   * assert.deepStrictEqual(makeBy(5, double), [0, 2, 4, 6, 8])
   *
   * @category constructors
   * @since 2.5.0
   */
  function makeBy(n, f) {
      // tslint:disable-next-line: readonly-array
      var r = [];
      for (var i = 0; i < n; i++) {
          r.push(f(i));
      }
      return r;
  }
  exports.makeBy = makeBy;
  /**
   * Create an array containing a range of integers, including both endpoints
   *
   * @example
   * import { range } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(range(1, 5), [1, 2, 3, 4, 5])
   *
   * @category constructors
   * @since 2.5.0
   */
  function range(start, end) {
      return makeBy(end - start + 1, function (i) { return start + i; });
  }
  exports.range = range;
  /**
   * Create an array containing a value repeated the specified number of times
   *
   * @example
   * import { replicate } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(replicate(3, 'a'), ['a', 'a', 'a'])
   *
   * @category constructors
   * @since 2.5.0
   */
  function replicate(n, a) {
      return makeBy(n, function () { return a; });
  }
  exports.replicate = replicate;
  /**
   * Removes one level of nesting
   *
   * Derivable from `Monad`.
   *
   * @example
   * import { flatten } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(flatten([[1], [2], [3]]), [1, 2, 3])
   *
   * @category combinators
   * @since 2.5.0
   */
  function flatten(mma) {
      var rLen = 0;
      var len = mma.length;
      for (var i = 0; i < len; i++) {
          rLen += mma[i].length;
      }
      var r = Array(rLen);
      var start = 0;
      for (var i = 0; i < len; i++) {
          var arr = mma[i];
          var l = arr.length;
          for (var j = 0; j < l; j++) {
              r[j + start] = arr[j];
          }
          start += l;
      }
      return r;
  }
  exports.flatten = flatten;
  /**
   * Break an array into its first element and remaining elements
   *
   * @example
   * import { foldLeft } from 'fp-ts/ReadonlyArray'
   *
   * const len: <A>(as: ReadonlyArray<A>) => number = foldLeft(() => 0, (_, tail) => 1 + len(tail))
   * assert.strictEqual(len([1, 2, 3]), 3)
   *
   * @category destructors
   * @since 2.5.0
   */
  function foldLeft(onEmpty, onCons) {
      return function (as) { return (isEmpty(as) ? onEmpty() : onCons(as[0], as.slice(1))); };
  }
  exports.foldLeft = foldLeft;
  /**
   * Break an array into its initial elements and the last element
   *
   * @category destructors
   * @since 2.5.0
   */
  function foldRight(onEmpty, onCons) {
      return function (as) { return (isEmpty(as) ? onEmpty() : onCons(as.slice(0, as.length - 1), as[as.length - 1])); };
  }
  exports.foldRight = foldRight;
  /**
   * Same as `reduce` but it carries over the intermediate steps
   *
   * @example
   * import { scanLeft } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(scanLeft(10, (b, a: number) => b - a)([1, 2, 3]), [10, 9, 7, 4])
   *
   * @category combinators
   * @since 2.5.0
   */
  function scanLeft(b, f) {
      return function (as) {
          var l = as.length;
          var r = new Array(l + 1);
          r[0] = b;
          for (var i = 0; i < l; i++) {
              r[i + 1] = f(r[i], as[i]);
          }
          return r;
      };
  }
  exports.scanLeft = scanLeft;
  /**
   * Fold an array from the right, keeping all intermediate results instead of only the final result
   *
   * @example
   * import { scanRight } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(scanRight(10, (a: number, b) => b - a)([1, 2, 3]), [4, 5, 7, 10])
   *
   * @category combinators
   * @since 2.5.0
   */
  function scanRight(b, f) {
      return function (as) {
          var l = as.length;
          var r = new Array(l + 1);
          r[l] = b;
          for (var i = l - 1; i >= 0; i--) {
              r[i] = f(as[i], r[i + 1]);
          }
          return r;
      };
  }
  exports.scanRight = scanRight;
  /**
   * Test whether an array is empty
   *
   * @example
   * import { isEmpty } from 'fp-ts/ReadonlyArray'
   *
   * assert.strictEqual(isEmpty([]), true)
   *
   * @since 2.5.0
   */
  function isEmpty(as) {
      return as.length === 0;
  }
  exports.isEmpty = isEmpty;
  /**
   * Test whether an array is non empty narrowing down the type to `NonEmptyReadonlyArray<A>`
   *
   * @category guards
   * @since 2.5.0
   */
  function isNonEmpty(as) {
      return as.length > 0;
  }
  exports.isNonEmpty = isNonEmpty;
  /**
   * Test whether an array contains a particular index
   *
   * @since 2.5.0
   */
  function isOutOfBound(i, as) {
      return i < 0 || i >= as.length;
  }
  exports.isOutOfBound = isOutOfBound;
  function lookup(i, as) {
      return as === undefined ? function (as) { return lookup(i, as); } : isOutOfBound(i, as) ? O.none : O.some(as[i]);
  }
  exports.lookup = lookup;
  function cons(head, tail) {
      if (tail === undefined) {
          return function (tail) { return cons(head, tail); };
      }
      var len = tail.length;
      var r = Array(len + 1);
      for (var i = 0; i < len; i++) {
          r[i + 1] = tail[i];
      }
      r[0] = head;
      return r;
  }
  exports.cons = cons;
  // TODO: curry and make data-last in v3
  /**
   * Append an element to the end of an array, creating a new non empty array
   *
   * @example
   * import { snoc } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(snoc([1, 2, 3], 4), [1, 2, 3, 4])
   *
   * @category constructors
   * @since 2.5.0
   */
  function snoc(init, end) {
      var len = init.length;
      var r = Array(len + 1);
      for (var i = 0; i < len; i++) {
          r[i] = init[i];
      }
      r[len] = end;
      return r;
  }
  exports.snoc = snoc;
  /**
   * Get the first element in an array, or `None` if the array is empty
   *
   * @example
   * import { head } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(head([1, 2, 3]), some(1))
   * assert.deepStrictEqual(head([]), none)
   *
   * @since 2.5.0
   */
  function head(as) {
      return isEmpty(as) ? O.none : O.some(as[0]);
  }
  exports.head = head;
  /**
   * Get the last element in an array, or `None` if the array is empty
   *
   * @example
   * import { last } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(last([1, 2, 3]), some(3))
   * assert.deepStrictEqual(last([]), none)
   *
   * @since 2.5.0
   */
  function last(as) {
      return lookup(as.length - 1, as);
  }
  exports.last = last;
  /**
   * Get all but the first element of an array, creating a new array, or `None` if the array is empty
   *
   * @example
   * import { tail } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(tail([1, 2, 3]), some([2, 3]))
   * assert.deepStrictEqual(tail([]), none)
   *
   * @since 2.5.0
   */
  function tail(as) {
      return isEmpty(as) ? O.none : O.some(as.slice(1));
  }
  exports.tail = tail;
  /**
   * Get all but the last element of an array, creating a new array, or `None` if the array is empty
   *
   * @example
   * import { init } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(init([1, 2, 3]), some([1, 2]))
   * assert.deepStrictEqual(init([]), none)
   *
   * @since 2.5.0
   */
  function init(as) {
      var len = as.length;
      return len === 0 ? O.none : O.some(as.slice(0, len - 1));
  }
  exports.init = init;
  /**
   * Keep only a number of elements from the start of an array, creating a new array.
   * `n` must be a natural number
   *
   * @example
   * import { takeLeft } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(takeLeft(2)([1, 2, 3]), [1, 2])
   *
   * @category combinators
   * @since 2.5.0
   */
  function takeLeft(n) {
      return function (as) { return as.slice(0, n); };
  }
  exports.takeLeft = takeLeft;
  /**
   * Keep only a number of elements from the end of an array, creating a new array.
   * `n` must be a natural number
   *
   * @example
   * import { takeRight } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(takeRight(2)([1, 2, 3, 4, 5]), [4, 5])
   *
   * @since 2.5.0
   */
  function takeRight(n) {
      return function (as) { return (n === 0 ? exports.empty : as.slice(-n)); };
  }
  exports.takeRight = takeRight;
  function takeLeftWhile(predicate) {
      return function (as) {
          var i = spanIndexUncurry(as, predicate);
          var init = Array(i);
          for (var j = 0; j < i; j++) {
              init[j] = as[j];
          }
          return init;
      };
  }
  exports.takeLeftWhile = takeLeftWhile;
  var spanIndexUncurry = function (as, predicate) {
      var l = as.length;
      var i = 0;
      for (; i < l; i++) {
          if (!predicate(as[i])) {
              break;
          }
      }
      return i;
  };
  function spanLeft(predicate) {
      return function (as) {
          var i = spanIndexUncurry(as, predicate);
          var init = Array(i);
          for (var j = 0; j < i; j++) {
              init[j] = as[j];
          }
          var l = as.length;
          var rest = Array(l - i);
          for (var j = i; j < l; j++) {
              rest[j - i] = as[j];
          }
          return { init: init, rest: rest };
      };
  }
  exports.spanLeft = spanLeft;
  /**
   * Drop a number of elements from the start of an array, creating a new array
   *
   * @example
   * import { dropLeft } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(dropLeft(2)([1, 2, 3]), [3])
   *
   * @category combinators
   * @since 2.5.0
   */
  function dropLeft(n) {
      return function (as) { return as.slice(n, as.length); };
  }
  exports.dropLeft = dropLeft;
  /**
   * Drop a number of elements from the end of an array, creating a new array
   *
   * @example
   * import { dropRight } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(dropRight(2)([1, 2, 3, 4, 5]), [1, 2, 3])
   *
   * @category combinators
   * @since 2.5.0
   */
  function dropRight(n) {
      return function (as) { return as.slice(0, as.length - n); };
  }
  exports.dropRight = dropRight;
  /**
   * Remove the longest initial subarray for which all element satisfy the specified predicate, creating a new array
   *
   * @example
   * import { dropLeftWhile } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(dropLeftWhile((n: number) => n % 2 === 1)([1, 3, 2, 4, 5]), [2, 4, 5])
   *
   * @category combinators
   * @since 2.5.0
   */
  function dropLeftWhile(predicate) {
      return function (as) {
          var i = spanIndexUncurry(as, predicate);
          var l = as.length;
          var rest = Array(l - i);
          for (var j = i; j < l; j++) {
              rest[j - i] = as[j];
          }
          return rest;
      };
  }
  exports.dropLeftWhile = dropLeftWhile;
  /**
   * Find the first index for which a predicate holds
   *
   * @example
   * import { findIndex } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(findIndex((n: number) => n === 2)([1, 2, 3]), some(1))
   * assert.deepStrictEqual(findIndex((n: number) => n === 2)([]), none)
   *
   * @since 2.5.0
   */
  function findIndex(predicate) {
      return function (as) {
          var len = as.length;
          for (var i = 0; i < len; i++) {
              if (predicate(as[i])) {
                  return O.some(i);
              }
          }
          return O.none;
      };
  }
  exports.findIndex = findIndex;
  function findFirst(predicate) {
      return function (as) {
          var len = as.length;
          for (var i = 0; i < len; i++) {
              if (predicate(as[i])) {
                  return O.some(as[i]);
              }
          }
          return O.none;
      };
  }
  exports.findFirst = findFirst;
  /**
   * Find the first element returned by an option based selector function
   *
   * @example
   * import { findFirstMap } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * interface Person {
   *   name: string
   *   age?: number
   * }
   *
   * const persons: ReadonlyArray<Person> = [{ name: 'John' }, { name: 'Mary', age: 45 }, { name: 'Joey', age: 28 }]
   *
   * // returns the name of the first person that has an age
   * assert.deepStrictEqual(findFirstMap((p: Person) => (p.age === undefined ? none : some(p.name)))(persons), some('Mary'))
   *
   * @since 2.5.0
   */
  function findFirstMap(f) {
      return function (as) {
          var len = as.length;
          for (var i = 0; i < len; i++) {
              var v = f(as[i]);
              if (O.isSome(v)) {
                  return v;
              }
          }
          return O.none;
      };
  }
  exports.findFirstMap = findFirstMap;
  function findLast(predicate) {
      return function (as) {
          var len = as.length;
          for (var i = len - 1; i >= 0; i--) {
              if (predicate(as[i])) {
                  return O.some(as[i]);
              }
          }
          return O.none;
      };
  }
  exports.findLast = findLast;
  /**
   * Find the last element returned by an option based selector function
   *
   * @example
   * import { findLastMap } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * interface Person {
   *   name: string
   *   age?: number
   * }
   *
   * const persons: ReadonlyArray<Person> = [{ name: 'John' }, { name: 'Mary', age: 45 }, { name: 'Joey', age: 28 }]
   *
   * // returns the name of the last person that has an age
   * assert.deepStrictEqual(findLastMap((p: Person) => (p.age === undefined ? none : some(p.name)))(persons), some('Joey'))
   *
   * @since 2.5.0
   */
  function findLastMap(f) {
      return function (as) {
          var len = as.length;
          for (var i = len - 1; i >= 0; i--) {
              var v = f(as[i]);
              if (O.isSome(v)) {
                  return v;
              }
          }
          return O.none;
      };
  }
  exports.findLastMap = findLastMap;
  /**
   * Returns the index of the last element of the list which matches the predicate
   *
   * @example
   * import { findLastIndex } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * interface X {
   *   a: number
   *   b: number
   * }
   * const xs: ReadonlyArray<X> = [{ a: 1, b: 0 }, { a: 1, b: 1 }]
   * assert.deepStrictEqual(findLastIndex((x: { a: number }) => x.a === 1)(xs), some(1))
   * assert.deepStrictEqual(findLastIndex((x: { a: number }) => x.a === 4)(xs), none)
   *
   *
   * @since 2.5.0
   */
  function findLastIndex(predicate) {
      return function (as) {
          var len = as.length;
          for (var i = len - 1; i >= 0; i--) {
              if (predicate(as[i])) {
                  return O.some(i);
              }
          }
          return O.none;
      };
  }
  exports.findLastIndex = findLastIndex;
  /**
   * Insert an element at the specified index, creating a new array, or returning `None` if the index is out of bounds
   *
   * @example
   * import { insertAt } from 'fp-ts/ReadonlyArray'
   * import { some } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(insertAt(2, 5)([1, 2, 3, 4]), some([1, 2, 5, 3, 4]))
   *
   * @since 2.5.0
   */
  function insertAt(i, a) {
      return function (as) { return (i < 0 || i > as.length ? O.none : O.some(unsafeInsertAt(i, a, as))); };
  }
  exports.insertAt = insertAt;
  /**
   * Change the element at the specified index, creating a new array, or returning `None` if the index is out of bounds
   *
   * @example
   * import { updateAt } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(updateAt(1, 1)([1, 2, 3]), some([1, 1, 3]))
   * assert.deepStrictEqual(updateAt(1, 1)([]), none)
   *
   * @since 2.5.0
   */
  function updateAt(i, a) {
      return function (as) { return (isOutOfBound(i, as) ? O.none : O.some(unsafeUpdateAt(i, a, as))); };
  }
  exports.updateAt = updateAt;
  /**
   * Delete the element at the specified index, creating a new array, or returning `None` if the index is out of bounds
   *
   * @example
   * import { deleteAt } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * assert.deepStrictEqual(deleteAt(0)([1, 2, 3]), some([2, 3]))
   * assert.deepStrictEqual(deleteAt(1)([]), none)
   *
   * @since 2.5.0
   */
  function deleteAt(i) {
      return function (as) { return (isOutOfBound(i, as) ? O.none : O.some(unsafeDeleteAt(i, as))); };
  }
  exports.deleteAt = deleteAt;
  /**
   * Apply a function to the element at the specified index, creating a new array, or returning `None` if the index is out
   * of bounds
   *
   * @example
   * import { modifyAt } from 'fp-ts/ReadonlyArray'
   * import { some, none } from 'fp-ts/Option'
   *
   * const double = (x: number): number => x * 2
   * assert.deepStrictEqual(modifyAt(1, double)([1, 2, 3]), some([1, 4, 3]))
   * assert.deepStrictEqual(modifyAt(1, double)([]), none)
   *
   * @since 2.5.0
   */
  function modifyAt(i, f) {
      return function (as) { return (isOutOfBound(i, as) ? O.none : O.some(unsafeUpdateAt(i, f(as[i]), as))); };
  }
  exports.modifyAt = modifyAt;
  /**
   * Reverse an array, creating a new array
   *
   * @example
   * import { reverse } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(reverse([1, 2, 3]), [3, 2, 1])
   *
   * @category combinators
   * @since 2.5.0
   */
  function reverse(as) {
      if (isEmpty(as)) {
          return as;
      }
      return as.slice().reverse();
  }
  exports.reverse = reverse;
  /**
   * Extracts from an array of `Either` all the `Right` elements. All the `Right` elements are extracted in order
   *
   * @example
   * import { rights } from 'fp-ts/ReadonlyArray'
   * import { right, left } from 'fp-ts/Either'
   *
   * assert.deepStrictEqual(rights([right(1), left('foo'), right(2)]), [1, 2])
   *
   * @category combinators
   * @since 2.5.0
   */
  function rights(as) {
      // tslint:disable-next-line: readonly-array
      var r = [];
      var len = as.length;
      for (var i = 0; i < len; i++) {
          var a = as[i];
          if (a._tag === 'Right') {
              r.push(a.right);
          }
      }
      return r;
  }
  exports.rights = rights;
  /**
   * Extracts from an array of `Either` all the `Left` elements. All the `Left` elements are extracted in order
   *
   * @example
   * import { lefts } from 'fp-ts/ReadonlyArray'
   * import { left, right } from 'fp-ts/Either'
   *
   * assert.deepStrictEqual(lefts([right(1), left('foo'), right(2)]), ['foo'])
   *
   * @since 2.5.0
   */
  function lefts(as) {
      // tslint:disable-next-line: readonly-array
      var r = [];
      var len = as.length;
      for (var i = 0; i < len; i++) {
          var a = as[i];
          if (a._tag === 'Left') {
              r.push(a.left);
          }
      }
      return r;
  }
  exports.lefts = lefts;
  /**
   * Sort the elements of an array in increasing order, creating a new array
   *
   * @example
   * import { sort } from 'fp-ts/ReadonlyArray'
   * import { ordNumber } from 'fp-ts/Ord'
   *
   * assert.deepStrictEqual(sort(ordNumber)([3, 2, 1]), [1, 2, 3])
   *
   * @category combinators
   * @since 2.5.0
   */
  var sort = function (O) { return function (as) {
      return as.length <= 1 ? as : as.slice().sort(O.compare);
  }; };
  exports.sort = sort;
  // TODO: curry and make data-last in v3
  /**
   * Apply a function to pairs of elements at the same index in two arrays, collecting the results in a new array. If one
   * input array is short, excess elements of the longer array are discarded.
   *
   * @example
   * import { zipWith } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(zipWith([1, 2, 3], ['a', 'b', 'c', 'd'], (n, s) => s + n), ['a1', 'b2', 'c3'])
   *
   * @category combinators
   * @since 2.5.0
   */
  function zipWith(fa, fb, f) {
      // tslint:disable-next-line: readonly-array
      var fc = [];
      var len = Math.min(fa.length, fb.length);
      for (var i = 0; i < len; i++) {
          fc[i] = f(fa[i], fb[i]);
      }
      return fc;
  }
  exports.zipWith = zipWith;
  function zip(as, bs) {
      if (bs === undefined) {
          return function (bs) { return zip(bs, as); };
      }
      return zipWith(as, bs, function (a, b) { return [a, b]; });
  }
  exports.zip = zip;
  /**
   * The function is reverse of `zip`. Takes an array of pairs and return two corresponding arrays
   *
   * @example
   * import { unzip } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(unzip([[1, 'a'], [2, 'b'], [3, 'c']]), [[1, 2, 3], ['a', 'b', 'c']])
   *
   * @since 2.5.0
   */
  function unzip(as) {
      // tslint:disable-next-line: readonly-array
      var fa = [];
      // tslint:disable-next-line: readonly-array
      var fb = [];
      for (var i = 0; i < as.length; i++) {
          fa[i] = as[i][0];
          fb[i] = as[i][1];
      }
      return [fa, fb];
  }
  exports.unzip = unzip;
  /**
   * Prepend an element to every member of an array
   *
   * @example
   * import { prependToAll } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(prependToAll(9)([1, 2, 3, 4]), [9, 1, 9, 2, 9, 3, 9, 4])
   *
   * @category combinators
   * @since 2.9.0
   */
  var prependToAll = function (e) { return function (xs) {
      // tslint:disable-next-line: readonly-array
      var ys = [];
      for (var _i = 0, xs_1 = xs; _i < xs_1.length; _i++) {
          var x = xs_1[_i];
          ys.push(e, x);
      }
      return ys;
  }; };
  exports.prependToAll = prependToAll;
  /**
   * Places an element in between members of an array
   *
   * @example
   * import { intersperse } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(intersperse(9)([1, 2, 3, 4]), [1, 9, 2, 9, 3, 9, 4])
   *
   * @category combinators
   * @since 2.9.0
   */
  function intersperse(e) {
      return function (as) {
          var length = as.length;
          if (length === 0) {
              return as;
          }
          return cons(as[0], exports.prependToAll(e)(as.slice(1, as.length)));
      };
  }
  exports.intersperse = intersperse;
  /**
   * Rotate an array to the right by `n` steps
   *
   * @example
   * import { rotate } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(rotate(2)([1, 2, 3, 4, 5]), [4, 5, 1, 2, 3])
   *
   * @category combinators
   * @since 2.5.0
   */
  function rotate(n) {
      return function (as) {
          var len = as.length;
          if (n === 0 || len <= 1 || len === Math.abs(n)) {
              return as;
          }
          else if (n < 0) {
              return rotate(len + n)(as);
          }
          else {
              return as.slice(-n).concat(as.slice(0, len - n));
          }
      };
  }
  exports.rotate = rotate;
  function elem(E) {
      return function (a, as) {
          if (as === undefined) {
              var elemE_1 = elem(E);
              return function (as) { return elemE_1(a, as); };
          }
          var predicate = function (element) { return E.equals(element, a); };
          var i = 0;
          var len = as.length;
          for (; i < len; i++) {
              if (predicate(as[i])) {
                  return true;
              }
          }
          return false;
      };
  }
  exports.elem = elem;
  /**
   * Remove duplicates from an array, keeping the first occurrence of an element.
   *
   * @example
   * import { uniq } from 'fp-ts/ReadonlyArray'
   * import { eqNumber } from 'fp-ts/Eq'
   *
   * assert.deepStrictEqual(uniq(eqNumber)([1, 2, 1]), [1, 2])
   *
   * @category combinators
   * @since 2.5.0
   */
  function uniq(E) {
      var elemS = elem(E);
      return function (as) {
          var len = as.length;
          if (len <= 1) {
              return as;
          }
          // tslint:disable-next-line: readonly-array
          var r = [];
          var i = 0;
          for (; i < len; i++) {
              var a = as[i];
              if (!elemS(a, r)) {
                  r.push(a);
              }
          }
          return len === r.length ? as : r;
      };
  }
  exports.uniq = uniq;
  /**
   * Sort the elements of an array in increasing order, where elements are compared using first `ords[0]`, then `ords[1]`,
   * etc...
   *
   * @example
   * import { sortBy } from 'fp-ts/ReadonlyArray'
   * import { ord, ordString, ordNumber } from 'fp-ts/Ord'
   *
   * interface Person {
   *   name: string
   *   age: number
   * }
   * const byName = ord.contramap(ordString, (p: Person) => p.name)
   * const byAge = ord.contramap(ordNumber, (p: Person) => p.age)
   *
   * const sortByNameByAge = sortBy([byName, byAge])
   *
   * const persons = [{ name: 'a', age: 1 }, { name: 'b', age: 3 }, { name: 'c', age: 2 }, { name: 'b', age: 2 }]
   * assert.deepStrictEqual(sortByNameByAge(persons), [
   *   { name: 'a', age: 1 },
   *   { name: 'b', age: 2 },
   *   { name: 'b', age: 3 },
   *   { name: 'c', age: 2 }
   * ])
   *
   * @category combinators
   * @since 2.5.0
   */
  function sortBy(ords) {
      var M = Ord_1.getMonoid();
      return exports.sort(ords.reduce(M.concat, M.empty));
  }
  exports.sortBy = sortBy;
  /**
   * A useful recursion pattern for processing an array to produce a new array, often used for "chopping" up the input
   * array. Typically chop is called with some function that will consume an initial prefix of the array and produce a
   * value and the rest of the array.
   *
   * @example
   * import { Eq, eqNumber } from 'fp-ts/Eq'
   * import { chop, spanLeft } from 'fp-ts/ReadonlyArray'
   *
   * const group = <A>(S: Eq<A>): ((as: ReadonlyArray<A>) => ReadonlyArray<ReadonlyArray<A>>) => {
   *   return chop(as => {
   *     const { init, rest } = spanLeft((a: A) => S.equals(a, as[0]))(as)
   *     return [init, rest]
   *   })
   * }
   * assert.deepStrictEqual(group(eqNumber)([1, 1, 2, 3, 3, 4]), [[1, 1], [2], [3, 3], [4]])
   *
   * @category combinators
   * @since 2.5.0
   */
  var chop = function (f) { return function (as) {
      // tslint:disable-next-line: readonly-array
      var result = [];
      var cs = as;
      while (isNonEmpty(cs)) {
          var _a = f(cs), b = _a[0], c = _a[1];
          result.push(b);
          cs = c;
      }
      return result;
  }; };
  exports.chop = chop;
  /**
   * Splits an array into two pieces, the first piece has `n` elements.
   *
   * @example
   * import { splitAt } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(splitAt(2)([1, 2, 3, 4, 5]), [[1, 2], [3, 4, 5]])
   *
   * @since 2.5.0
   */
  function splitAt(n) {
      return function (as) { return [as.slice(0, n), as.slice(n)]; };
  }
  exports.splitAt = splitAt;
  /**
   * Splits an array into length-`n` pieces. The last piece will be shorter if `n` does not evenly divide the length of
   * the array. Note that `chunksOf(n)([])` is `[]`, not `[[]]`. This is intentional, and is consistent with a recursive
   * definition of `chunksOf`; it satisfies the property that
   *
   * ```ts
   * chunksOf(n)(xs).concat(chunksOf(n)(ys)) == chunksOf(n)(xs.concat(ys)))
   * ```
   *
   * whenever `n` evenly divides the length of `xs`.
   *
   * @example
   * import { chunksOf } from 'fp-ts/ReadonlyArray'
   *
   * assert.deepStrictEqual(chunksOf(2)([1, 2, 3, 4, 5]), [[1, 2], [3, 4], [5]])
   *
   *
   * @since 2.5.0
   */
  function chunksOf(n) {
      var f = exports.chop(splitAt(n));
      return function (as) { return (as.length === 0 ? exports.empty : isOutOfBound(n - 1, as) ? [as] : f(as)); };
  }
  exports.chunksOf = chunksOf;
  function comprehension(input, f, g) {
      if (g === void 0) { g = function () { return true; }; }
      var go = function (scope, input) {
          if (input.length === 0) {
              return g.apply(void 0, scope) ? [f.apply(void 0, scope)] : exports.empty;
          }
          else {
              return chain_(input[0], function (x) { return go(snoc(scope, x), input.slice(1)); });
          }
      };
      return go(exports.empty, input);
  }
  exports.comprehension = comprehension;
  function union(E) {
      var elemE = elem(E);
      return function (xs, ys) {
          if (ys === undefined) {
              var unionE_1 = union(E);
              return function (ys) { return unionE_1(ys, xs); };
          }
          return concat(xs, ys.filter(function (a) { return !elemE(a, xs); }));
      };
  }
  exports.union = union;
  function intersection(E) {
      var elemE = elem(E);
      return function (xs, ys) {
          if (ys === undefined) {
              var intersectionE_1 = intersection(E);
              return function (ys) { return intersectionE_1(ys, xs); };
          }
          return xs.filter(function (a) { return elemE(a, ys); });
      };
  }
  exports.intersection = intersection;
  function difference(E) {
      var elemE = elem(E);
      return function (xs, ys) {
          if (ys === undefined) {
              var differenceE_1 = difference(E);
              return function (ys) { return differenceE_1(ys, xs); };
          }
          return xs.filter(function (a) { return !elemE(a, ys); });
      };
  }
  exports.difference = difference;
  /**
   * Wrap a value into the type constructor.
   *
   * @category Applicative
   * @since 2.5.0
   */
  var of = function (a) { return [a]; };
  exports.of = of;
  /**
   * @category Alternative
   * @since 2.7.0
   */
  var zero = function () { return exports.empty; };
  exports.zero = zero;
  // -------------------------------------------------------------------------------------
  // non-pipeables
  // -------------------------------------------------------------------------------------
  var map_ = function (fa, f) { return function_1.pipe(fa, exports.map(f)); };
  var mapWithIndex_ = function (fa, f) { return function_1.pipe(fa, exports.mapWithIndex(f)); };
  var ap_ = function (fab, fa) { return function_1.pipe(fab, exports.ap(fa)); };
  var chain_ = function (ma, f) {
      return function_1.pipe(ma, exports.chain(f));
  };
  var filter_ = function (fa, predicate) { return function_1.pipe(fa, exports.filter(predicate)); };
  var filterMap_ = function (fa, f) { return function_1.pipe(fa, exports.filterMap(f)); };
  var partitionWithIndex_ = function (fa, predicateWithIndex) { return function_1.pipe(fa, exports.partitionWithIndex(predicateWithIndex)); };
  var partition_ = function (fa, predicate) { return function_1.pipe(fa, exports.partition(predicate)); };
  var partitionMap_ = function (fa, f) { return function_1.pipe(fa, exports.partitionMap(f)); };
  var partitionMapWithIndex_ = function (fa, f) { return function_1.pipe(fa, exports.partitionMapWithIndex(f)); };
  var alt_ = function (fa, that) { return function_1.pipe(fa, exports.alt(that)); };
  var reduce_ = function (fa, b, f) { return function_1.pipe(fa, exports.reduce(b, f)); };
  var foldMap_ = function (M) {
      var foldMapM = exports.foldMap(M);
      return function (fa, f) { return function_1.pipe(fa, foldMapM(f)); };
  };
  var reduceRight_ = function (fa, b, f) { return function_1.pipe(fa, exports.reduceRight(b, f)); };
  var reduceWithIndex_ = function (fa, b, f) {
      var l = fa.length;
      var r = b;
      for (var i = 0; i < l; i++) {
          r = f(i, r, fa[i]);
      }
      return r;
  };
  var foldMapWithIndex_ = function (M) { return function (fa, f) {
      return fa.reduce(function (b, a, i) { return M.concat(b, f(i, a)); }, M.empty);
  }; };
  var reduceRightWithIndex_ = function (fa, b, f) {
      return function_1.pipe(fa, exports.reduceRightWithIndex(b, f));
  };
  var filterMapWithIndex_ = function (fa, f) {
      return function_1.pipe(fa, exports.filterMapWithIndex(f));
  };
  var filterWithIndex_ = function (fa, predicateWithIndex) { return function_1.pipe(fa, exports.filterWithIndex(predicateWithIndex)); };
  var extend_ = function (fa, f) { return function_1.pipe(fa, exports.extend(f)); };
  var traverse_ = function (F) {
      var traverseF = exports.traverse(F);
      return function (ta, f) { return function_1.pipe(ta, traverseF(f)); };
  };
  /* istanbul ignore next */
  var traverseWithIndex_ = function (F) {
      var traverseWithIndexF = exports.traverseWithIndex(F);
      return function (ta, f) { return function_1.pipe(ta, traverseWithIndexF(f)); };
  };
  /* istanbul ignore next */
  var wither_ = function (F) {
      var witherF = exports.wither(F);
      return function (fa, f) { return function_1.pipe(fa, witherF(f)); };
  };
  /* istanbul ignore next */
  var wilt_ = function (F) {
      var wiltF = exports.wilt(F);
      return function (fa, f) { return function_1.pipe(fa, wiltF(f)); };
  };
  // -------------------------------------------------------------------------------------
  // pipeables
  // -------------------------------------------------------------------------------------
  /**
   * Less strict version of [`alt`](#alt).
   *
   * @category Alt
   * @since 2.9.0
   */
  var altW = function (that) { return function (fa) { return concat(fa, that()); }; };
  exports.altW = altW;
  /**
   * Identifies an associative operation on a type constructor. It is similar to `Semigroup`, except that it applies to
   * types of kind `* -> *`.
   *
   * @category Alt
   * @since 2.5.0
   */
  exports.alt = exports.altW;
  /**
   * Apply a function to an argument under a type constructor.
   *
   * @category Apply
   * @since 2.5.0
   */
  var ap = function (fa) {
      return exports.chain(function (f) { return function_1.pipe(fa, exports.map(f)); });
  };
  exports.ap = ap;
  /**
   * Combine two effectful actions, keeping only the result of the first.
   *
   * Derivable from `Apply`.
   *
   * @category combinators
   * @since 2.5.0
   */
  var apFirst = function (fb) {
      return function_1.flow(exports.map(function (a) { return function () { return a; }; }), exports.ap(fb));
  };
  exports.apFirst = apFirst;
  /**
   * Combine two effectful actions, keeping only the result of the second.
   *
   * Derivable from `Apply`.
   *
   * @category combinators
   * @since 2.5.0
   */
  var apSecond = function (fb) {
      return function_1.flow(exports.map(function () { return function (b) { return b; }; }), exports.ap(fb));
  };
  exports.apSecond = apSecond;
  /**
   * Composes computations in sequence, using the return value of one computation to determine the next computation.
   *
   * @category Monad
   * @since 2.5.0
   */
  var chain = function (f) { return function (ma) {
      return function_1.pipe(ma, exports.chainWithIndex(function (_, a) { return f(a); }));
  }; };
  exports.chain = chain;
  /**
   * @since 2.7.0
   */
  var chainWithIndex = function (f) { return function (ma) {
      var outLen = 0;
      var l = ma.length;
      var temp = new Array(l);
      for (var i = 0; i < l; i++) {
          var e = ma[i];
          var arr = f(i, e);
          outLen += arr.length;
          temp[i] = arr;
      }
      var out = Array(outLen);
      var start = 0;
      for (var i = 0; i < l; i++) {
          var arr = temp[i];
          var l_1 = arr.length;
          for (var j = 0; j < l_1; j++) {
              out[j + start] = arr[j];
          }
          start += l_1;
      }
      return out;
  }; };
  exports.chainWithIndex = chainWithIndex;
  /**
   * Composes computations in sequence, using the return value of one computation to determine the next computation and
   * keeping only the result of the first.
   *
   * Derivable from `Monad`.
   *
   * @category combinators
   * @since 2.5.0
   */
  var chainFirst = function (f) {
      return exports.chain(function (a) {
          return function_1.pipe(f(a), exports.map(function () { return a; }));
      });
  };
  exports.chainFirst = chainFirst;
  /**
   * `map` can be used to turn functions `(a: A) => B` into functions `(fa: F<A>) => F<B>` whose argument and return types
   * use the type constructor `F` to represent some computational context.
   *
   * @category Functor
   * @since 2.5.0
   */
  var map = function (f) { return function (fa) {
      return fa.map(function (a) { return f(a); });
  }; };
  exports.map = map;
  /**
   * @category FunctorWithIndex
   * @since 2.5.0
   */
  var mapWithIndex = function (f) { return function (fa) { return fa.map(function (a, i) { return f(i, a); }); }; };
  exports.mapWithIndex = mapWithIndex;
  /**
   * @category Compactable
   * @since 2.5.0
   */
  var separate = function (fa) {
      // tslint:disable-next-line: readonly-array
      var left = [];
      // tslint:disable-next-line: readonly-array
      var right = [];
      for (var _i = 0, fa_1 = fa; _i < fa_1.length; _i++) {
          var e = fa_1[_i];
          if (e._tag === 'Left') {
              left.push(e.left);
          }
          else {
              right.push(e.right);
          }
      }
      return {
          left: left,
          right: right
      };
  };
  exports.separate = separate;
  /**
   * @category Filterable
   * @since 2.5.0
   */
  var filter = function (predicate) { return function (fa) { return fa.filter(predicate); }; };
  exports.filter = filter;
  /**
   * @category FilterableWithIndex
   * @since 2.5.0
   */
  var filterMapWithIndex = function (f) { return function (fa) {
      // tslint:disable-next-line: readonly-array
      var result = [];
      for (var i = 0; i < fa.length; i++) {
          var optionB = f(i, fa[i]);
          if (O.isSome(optionB)) {
              result.push(optionB.value);
          }
      }
      return result;
  }; };
  exports.filterMapWithIndex = filterMapWithIndex;
  /**
   * @category Filterable
   * @since 2.5.0
   */
  var filterMap = function (f) {
      return exports.filterMapWithIndex(function (_, a) { return f(a); });
  };
  exports.filterMap = filterMap;
  /**
   * @category Compactable
   * @since 2.5.0
   */
  exports.compact = 
  /*#__PURE__*/
  exports.filterMap(function_1.identity);
  /**
   * @category Filterable
   * @since 2.5.0
   */
  var partition = function (predicate) {
      return exports.partitionWithIndex(function (_, a) { return predicate(a); });
  };
  exports.partition = partition;
  /**
   * @category FilterableWithIndex
   * @since 2.5.0
   */
  var partitionWithIndex = function (predicateWithIndex) { return function (fa) {
      // tslint:disable-next-line: readonly-array
      var left = [];
      // tslint:disable-next-line: readonly-array
      var right = [];
      for (var i = 0; i < fa.length; i++) {
          var a = fa[i];
          if (predicateWithIndex(i, a)) {
              right.push(a);
          }
          else {
              left.push(a);
          }
      }
      return {
          left: left,
          right: right
      };
  }; };
  exports.partitionWithIndex = partitionWithIndex;
  /**
   * @category Filterable
   * @since 2.5.0
   */
  var partitionMap = function (f) {
      return exports.partitionMapWithIndex(function (_, a) { return f(a); });
  };
  exports.partitionMap = partitionMap;
  /**
   * @category FilterableWithIndex
   * @since 2.5.0
   */
  var partitionMapWithIndex = function (f) { return function (fa) {
      // tslint:disable-next-line: readonly-array
      var left = [];
      // tslint:disable-next-line: readonly-array
      var right = [];
      for (var i = 0; i < fa.length; i++) {
          var e = f(i, fa[i]);
          if (e._tag === 'Left') {
              left.push(e.left);
          }
          else {
              right.push(e.right);
          }
      }
      return {
          left: left,
          right: right
      };
  }; };
  exports.partitionMapWithIndex = partitionMapWithIndex;
  /**
   * @category FilterableWithIndex
   * @since 2.5.0
   */
  var filterWithIndex = function (predicateWithIndex) { return function (fa) {
      return fa.filter(function (a, i) { return predicateWithIndex(i, a); });
  }; };
  exports.filterWithIndex = filterWithIndex;
  /**
   * @category Extend
   * @since 2.5.0
   */
  var extend = function (f) { return function (wa) { return wa.map(function (_, i, as) { return f(as.slice(i)); }); }; };
  exports.extend = extend;
  /**
   * Derivable from `Extend`.
   *
   * @category combinators
   * @since 2.5.0
   */
  exports.duplicate = 
  /*#__PURE__*/
  exports.extend(function_1.identity);
  /**
   * @category FoldableWithIndex
   * @since 2.5.0
   */
  var foldMapWithIndex = function (M) {
      var foldMapWithIndexM = foldMapWithIndex_(M);
      return function (f) { return function (fa) { return foldMapWithIndexM(fa, f); }; };
  };
  exports.foldMapWithIndex = foldMapWithIndex;
  /**
   * @category Foldable
   * @since 2.5.0
   */
  var reduce = function (b, f) {
      return exports.reduceWithIndex(b, function (_, b, a) { return f(b, a); });
  };
  exports.reduce = reduce;
  /**
   * @category Foldable
   * @since 2.5.0
   */
  var foldMap = function (M) {
      var foldMapWithIndexM = exports.foldMapWithIndex(M);
      return function (f) { return foldMapWithIndexM(function (_, a) { return f(a); }); };
  };
  exports.foldMap = foldMap;
  /**
   * @category FoldableWithIndex
   * @since 2.5.0
   */
  var reduceWithIndex = function (b, f) { return function (fa) { return reduceWithIndex_(fa, b, f); }; };
  exports.reduceWithIndex = reduceWithIndex;
  /**
   * @category Foldable
   * @since 2.5.0
   */
  var reduceRight = function (b, f) {
      return exports.reduceRightWithIndex(b, function (_, a, b) { return f(a, b); });
  };
  exports.reduceRight = reduceRight;
  /**
   * @category FoldableWithIndex
   * @since 2.5.0
   */
  var reduceRightWithIndex = function (b, f) { return function (fa) { return fa.reduceRight(function (b, a, i) { return f(i, a, b); }, b); }; };
  exports.reduceRightWithIndex = reduceRightWithIndex;
  /**
   * **for optimized and stack safe version check the data types `traverseArray` function**
   * @category Traversable
   * @since 2.6.3
   */
  var traverse = function (F) {
      var traverseWithIndexF = exports.traverseWithIndex(F);
      return function (f) { return traverseWithIndexF(function (_, a) { return f(a); }); };
  };
  exports.traverse = traverse;
  /**
   * **for optimized and stack safe version check the data types `sequenceArray` function**
   * @category Traversable
   * @since 2.6.3
   */
  var sequence = function (F) { return function (ta) {
      return reduce_(ta, F.of(exports.zero()), function (fas, fa) {
          return F.ap(F.map(fas, function (as) { return function (a) { return snoc(as, a); }; }), fa);
      });
  }; };
  exports.sequence = sequence;
  /**
   * **for optimized and stack safe version check the data types `traverseArrayWithIndex` function**
   * @category TraversableWithIndex
   * @since 2.6.3
   */
  var traverseWithIndex = function (F) { return function (f) {
      return exports.reduceWithIndex(F.of(exports.zero()), function (i, fbs, a) {
          return F.ap(F.map(fbs, function (bs) { return function (b) { return snoc(bs, b); }; }), f(i, a));
      });
  }; };
  exports.traverseWithIndex = traverseWithIndex;
  /**
   * @category Witherable
   * @since 2.6.5
   */
  var wither = function (F) {
      var traverseF = exports.traverse(F);
      return function (f) { return function (fa) { return F.map(function_1.pipe(fa, traverseF(f)), exports.compact); }; };
  };
  exports.wither = wither;
  /**
   * @category Witherable
   * @since 2.6.5
   */
  var wilt = function (F) {
      var traverseF = exports.traverse(F);
      return function (f) { return function (fa) { return F.map(function_1.pipe(fa, traverseF(f)), exports.separate); }; };
  };
  exports.wilt = wilt;
  /**
   * @category Unfoldable
   * @since 2.6.6
   */
  var unfold = function (b, f) {
      // tslint:disable-next-line: readonly-array
      var ret = [];
      var bb = b;
      while (true) {
          var mt = f(bb);
          if (O.isSome(mt)) {
              var _a = mt.value, a = _a[0], b_1 = _a[1];
              ret.push(a);
              bb = b_1;
          }
          else {
              break;
          }
      }
      return ret;
  };
  exports.unfold = unfold;
  // -------------------------------------------------------------------------------------
  // instances
  // -------------------------------------------------------------------------------------
  /**
   * @category instances
   * @since 2.5.0
   */
  exports.URI = 'ReadonlyArray';
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Functor = {
      URI: exports.URI,
      map: map_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.FunctorWithIndex = {
      URI: exports.URI,
      map: map_,
      mapWithIndex: mapWithIndex_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Applicative = {
      URI: exports.URI,
      map: map_,
      ap: ap_,
      of: exports.of
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Monad = {
      URI: exports.URI,
      map: map_,
      ap: ap_,
      of: exports.of,
      chain: chain_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Unfoldable = {
      URI: exports.URI,
      unfold: exports.unfold
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Alt = {
      URI: exports.URI,
      map: map_,
      alt: alt_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Alternative = {
      URI: exports.URI,
      map: map_,
      ap: ap_,
      of: exports.of,
      alt: alt_,
      zero: exports.zero
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Extend = {
      URI: exports.URI,
      map: map_,
      extend: extend_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Compactable = {
      URI: exports.URI,
      compact: exports.compact,
      separate: exports.separate
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Filterable = {
      URI: exports.URI,
      map: map_,
      compact: exports.compact,
      separate: exports.separate,
      filter: filter_,
      filterMap: filterMap_,
      partition: partition_,
      partitionMap: partitionMap_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.FilterableWithIndex = {
      URI: exports.URI,
      map: map_,
      mapWithIndex: mapWithIndex_,
      compact: exports.compact,
      separate: exports.separate,
      filter: filter_,
      filterMap: filterMap_,
      partition: partition_,
      partitionMap: partitionMap_,
      partitionMapWithIndex: partitionMapWithIndex_,
      partitionWithIndex: partitionWithIndex_,
      filterMapWithIndex: filterMapWithIndex_,
      filterWithIndex: filterWithIndex_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Foldable = {
      URI: exports.URI,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.FoldableWithIndex = {
      URI: exports.URI,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_,
      reduceWithIndex: reduceWithIndex_,
      foldMapWithIndex: foldMapWithIndex_,
      reduceRightWithIndex: reduceRightWithIndex_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Traversable = {
      URI: exports.URI,
      map: map_,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_,
      traverse: traverse_,
      sequence: exports.sequence
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.TraversableWithIndex = {
      URI: exports.URI,
      map: map_,
      mapWithIndex: mapWithIndex_,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_,
      reduceWithIndex: reduceWithIndex_,
      foldMapWithIndex: foldMapWithIndex_,
      reduceRightWithIndex: reduceRightWithIndex_,
      traverse: traverse_,
      sequence: exports.sequence,
      traverseWithIndex: traverseWithIndex_
  };
  /**
   * @category instances
   * @since 2.7.0
   */
  exports.Witherable = {
      URI: exports.URI,
      map: map_,
      compact: exports.compact,
      separate: exports.separate,
      filter: filter_,
      filterMap: filterMap_,
      partition: partition_,
      partitionMap: partitionMap_,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_,
      traverse: traverse_,
      sequence: exports.sequence,
      wither: wither_,
      wilt: wilt_
  };
  // TODO: remove in v3
  /**
   * @category instances
   * @since 2.5.0
   */
  exports.readonlyArray = {
      URI: exports.URI,
      compact: exports.compact,
      separate: exports.separate,
      map: map_,
      ap: ap_,
      of: exports.of,
      chain: chain_,
      filter: filter_,
      filterMap: filterMap_,
      partition: partition_,
      partitionMap: partitionMap_,
      mapWithIndex: mapWithIndex_,
      partitionMapWithIndex: partitionMapWithIndex_,
      partitionWithIndex: partitionWithIndex_,
      filterMapWithIndex: filterMapWithIndex_,
      filterWithIndex: filterWithIndex_,
      alt: alt_,
      zero: exports.zero,
      unfold: exports.unfold,
      reduce: reduce_,
      foldMap: foldMap_,
      reduceRight: reduceRight_,
      traverse: traverse_,
      sequence: exports.sequence,
      reduceWithIndex: reduceWithIndex_,
      foldMapWithIndex: foldMapWithIndex_,
      reduceRightWithIndex: reduceRightWithIndex_,
      traverseWithIndex: traverseWithIndex_,
      extend: extend_,
      wither: wither_,
      wilt: wilt_
  };
  // -------------------------------------------------------------------------------------
  // unsafe
  // -------------------------------------------------------------------------------------
  /**
   * @category unsafe
   * @since 2.5.0
   */
  function unsafeInsertAt(i, a, as) {
      var xs = as.slice();
      xs.splice(i, 0, a);
      return xs;
  }
  exports.unsafeInsertAt = unsafeInsertAt;
  /**
   * @category unsafe
   * @since 2.5.0
   */
  function unsafeUpdateAt(i, a, as) {
      if (as[i] === a) {
          return as;
      }
      else {
          var xs = as.slice();
          xs[i] = a;
          return xs;
      }
  }
  exports.unsafeUpdateAt = unsafeUpdateAt;
  /**
   * @category unsafe
   * @since 2.5.0
   */
  function unsafeDeleteAt(i, as) {
      var xs = as.slice();
      xs.splice(i, 1);
      return xs;
  }
  exports.unsafeDeleteAt = unsafeDeleteAt;
  // -------------------------------------------------------------------------------------
  // utils
  // -------------------------------------------------------------------------------------
  /**
   * An empty array
   *
   * @since 2.5.0
   */
  exports.empty = [];
  /**
   * Check if a predicate holds true for every array member.
   *
   * @example
   * import { every } from 'fp-ts/ReadonlyArray'
   * import { pipe } from 'fp-ts/function'
   *
   * const isPositive = (n: number): boolean => n > 0
   *
   * assert.deepStrictEqual(pipe([1, 2, 3], every(isPositive)), true)
   * assert.deepStrictEqual(pipe([1, 2, -3], every(isPositive)), false)
   *
   * @since 2.9.0
   */
  var every = function (predicate) { return function (as) { return as.every(predicate); }; };
  exports.every = every;
  /**
   * Check if a predicate holds true for any array member.
   *
   * @example
   * import { some } from 'fp-ts/ReadonlyArray'
   * import { pipe } from 'fp-ts/function'
   *
   * const isPositive = (n: number): boolean => n > 0
   *
   * assert.deepStrictEqual(pipe([-1, -2, 3], some(isPositive)), true)
   * assert.deepStrictEqual(pipe([-1, -2, -3], some(isPositive)), false)
   *
   * @since 2.9.0
   */
  var some = function (predicate) { return function (as) { return as.some(predicate); }; };
  exports.some = some;
  // -------------------------------------------------------------------------------------
  // do notation
  // -------------------------------------------------------------------------------------
  /**
   * @since 2.9.0
   */
  exports.Do = 
  /*#__PURE__*/
  exports.of({});
  /**
   * @since 2.8.0
   */
  var bindTo = function (name) {
      return exports.map(function_1.bindTo_(name));
  };
  exports.bindTo = bindTo;
  /**
   * @since 2.8.0
   */
  var bind = function (name, f) {
      return exports.chain(function (a) {
          return function_1.pipe(f(a), exports.map(function (b) { return function_1.bind_(a, name, b); }));
      });
  };
  exports.bind = bind;
  // -------------------------------------------------------------------------------------
  // pipeable sequence S
  // -------------------------------------------------------------------------------------
  /**
   * @since 2.8.0
   */
  var apS = function (name, fb) {
      return function_1.flow(exports.map(function (a) { return function (b) { return function_1.bind_(a, name, b); }; }), exports.ap(fb));
  };
  exports.apS = apS;
  