API Documentation: Chain
Chain is an immutable sequence data structure that allows constant time prepending, appending and concatenation.
This makes it especially efficient when used as a Monoid, e.g. with Validated or Writer.
As such it aims to be used where List and Vector incur a performance penalty.
Cats also includes type class implementations to support using
Chain as a general-purpose collection type, including Traverse, Monad, and Alternative.
List is a great data type, it is very simple and easy to understand.
It has very low overhead for the most important functions such as fold and map and also supports prepending a single element in constant time.
Traversing a data structure with something like Writer[List[Log], A] or ValidatedNel[Error, A] is powerful and allows us to precisely specify what kind of iteration we want to do while remaining succinct.
However, in terms of efficiency it's a whole different story unfortunately.
That is because both of these traversals make use of the
List monoid (or the NonEmptyList semigroup), which by the nature of
List is very inefficient.
If you use traverse with a data structure with
n elements and Writer or Validated as the Applicative type, you will end up with a runtime of
This is because, with
List, appending a single element requires iterating over the entire data structure and therefore takes linear time.
Vector has its own problems and in this case it's unfortunately not that much faster than
List at all. You can check this blog post by Li Haoyi for some deeper insight into
Chain evolved from what used to be
fs2.Catenable and Erik Osheim's Chain library.
List, it is also a very simple data structure, but unlike
List it supports constant O(1) time
This makes its Monoid instance super performant and a much better fit for usage with Validated, Writer, Ior or Const.
NonEmptyChain is the non-empty version of
It does not have a Monoid instance since it cannot be empty, but it does have a Semigroup instance.
Likewise, it defines a NonEmptyTraverse instance, but no TraverseFilter instance.
There are numerous ways to construct a
NonEmptyChain, e.g. you can create one from a single element, a
NonEmptyList or a
import cats.data._ NonEmptyChain(1, 2, 3, 4) // res0: NonEmptyChain[Int] = Append( // leftNE = Singleton(a = 1), // rightNE = Wrap(seq = ArraySeq(2, 3, 4)) // ) NonEmptyChain.fromNonEmptyList(NonEmptyList(1, List(2, 3))) // res1: NonEmptyChain[Int] = Wrap(seq = List(1, 2, 3)) NonEmptyChain.fromNonEmptyVector(NonEmptyVector(1, Vector(2, 3))) // res2: NonEmptyChain[Int] = Wrap(seq = Vector(1, 2, 3)) NonEmptyChain.one(1) // res3: NonEmptyChain[Int] = Singleton(a = 1)
You can also create an Option of
NonEmptyChain from a
Chain or any other collection type:
import cats.data._ NonEmptyChain.fromChain(Chain(1, 2, 3)) // res4: Option[NonEmptyChain[Int]] = Some( // value = Wrap(seq = ArraySeq(1, 2, 3)) // ) NonEmptyChain.fromSeq(List.empty[Int]) // res5: Option[NonEmptyChain[Int]] = None NonEmptyChain.fromSeq(Vector(1, 2, 3)) // res6: Option[NonEmptyChain[Int]] = Some(value = Wrap(seq = Vector(1, 2, 3)))
Sometimes, you'll want to prepend or append a single element to a chain and return the result as a
import cats.data._ NonEmptyChain.fromChainAppend(Chain(1, 2, 3), 4) // res7: NonEmptyChain[Int] = Append( // leftNE = Wrap(seq = ArraySeq(1, 2, 3)), // rightNE = Singleton(a = 4) // ) NonEmptyChain.fromChainAppend(Chain.empty[Int], 1) // res8: NonEmptyChain[Int] = Singleton(a = 1) NonEmptyChain.fromChainPrepend(1, Chain(2, 3)) // res9: NonEmptyChain[Int] = Append( // leftNE = Singleton(a = 1), // rightNE = Wrap(seq = ArraySeq(2, 3)) // )
How it works
Chain is implemented as a simple unbalanced binary tree ADT with four cases:
Chain with no elements, a singleton
Chain with exactly one element, a concatenation of two chains, or a wrapper for a Seq.
In code it looks like this:
sealed abstract class Chain[+A] case object Empty extends Chain[Nothing] case class Singleton[A](a: A) extends Chain[A] case class Append[A](left: Chain[A], right: Chain[A]) extends Chain[A] case class Wrap[A](seq: Seq[A]) extends Chain[A]
Append constructor is what gives us the fast concatenation ability.
Concatenating two existing
Chains is just a call to the
Append constructor, which is always constant time
In case we want to append or prepend a single element,
all we have to do is wrap the element with the
Singleton constructor and then use the
Append constructor to append or prepend the
Wrap constructor lifts any
Seq into a
This can be useful for concatenating already created collections that don't have great concatenation performance.
Append(Wrap(list1), Wrap(list2)).foldMap(f) will in general be much faster than just concatenating
list2 and folding the result.
Chain doesn't directly expose the
Wrap constructors, because the arguments might refer to an empty
Instead of calling
Append directly you can simply use
++, which will check if one of the arguments is empty:
def concat[A](c: Chain[A], c2: Chain[A]): Chain[A] = if (c.isEmpty) c2 else if (c2.isEmpty) c else Append(c, c2)
To construct a
Chain from a
Seq you should use
Chain.fromSeq which will also check for emptiness:
def fromSeq[A](s: Seq[A]): Chain[A] = if (s.isEmpty) nil else if (s.lengthCompare(1) == 0) one(s.head) else Wrap(s)
Chain supports constant time concatenation, because it builds an unbalance tree of
prepend are treated as concatenation with single element collection to keep the same performance characteristics.
This unbalanced tree will always allow iteration in linear time.
To get a good idea of performance of
Chain, here are some benchmarks that test monoidal append (higher score is better):
Benchmark Mode Cnt Score Error Units CollectionMonoidBench.accumulateChain thrpt 25 81.973 ± 3.921 ops/s CollectionMonoidBench.accumulateList thrpt 25 21.150 ± 1.756 ops/s CollectionMonoidBench.accumulateVector thrpt 25 11.725 ± 0.306 ops/s
As you can see accumulating things with
Chain is almost 4 times faster than
List and nearly 8 times faster than
So appending is a lot more performant than the standard library collections, but what about operations like
Fortunately we've also benchmarked these (again, higher score is better):
Benchmark Mode Cnt Score Error Units ChainBench.consLargeChain thrpt 25 143759156.264 ± 5611584.788 ops/s ChainBench.consLargeList thrpt 25 148512687.273 ± 5992793.489 ops/s ChainBench.consLargeVector thrpt 25 7249505.257 ± 202436.549 ops/s ChainBench.consSmallChain thrpt 25 119925876.637 ± 1663011.363 ops/s ChainBench.consSmallList thrpt 25 152664330.695 ± 1828399.646 ops/s ChainBench.consSmallVector thrpt 25 57686442.030 ± 533768.670 ops/s ChainBench.createChainOption thrpt 25 167191685.222 ± 1474976.197 ops/s ChainBench.createChainSeqOption thrpt 25 21264365.364 ± 372757.348 ops/s ChainBench.createSmallChain thrpt 25 87260308.052 ± 960407.889 ops/s ChainBench.createSmallList thrpt 25 20000981.857 ± 396001.340 ops/s ChainBench.createSmallVector thrpt 25 26311376.712 ± 288871.258 ops/s ChainBench.createTinyChain thrpt 25 75311482.869 ± 1066466.694 ops/s ChainBench.createTinyList thrpt 25 67502351.990 ± 1071560.419 ops/s ChainBench.createTinyVector thrpt 25 39676430.380 ± 405717.649 ops/s ChainBench.foldLeftLargeChain thrpt 25 117.866 ± 3.343 ops/s ChainBench.foldLeftLargeList thrpt 25 193.640 ± 2.298 ops/s ChainBench.foldLeftLargeVector thrpt 25 178.370 ± 0.830 ops/s ChainBench.foldLeftSmallChain thrpt 25 43732934.777 ± 362285.965 ops/s ChainBench.foldLeftSmallList thrpt 25 51155941.055 ± 882005.961 ops/s ChainBench.foldLeftSmallVector thrpt 25 41902918.940 ± 53030.742 ops/s ChainBench.lengthLargeChain thrpt 25 131831.918 ± 1613.341 ops/s ChainBench.lengthLargeList thrpt 25 271.015 ± 0.962 ops/s ChainBench.mapLargeChain thrpt 25 78.162 ± 2.620 ops/s ChainBench.mapLargeList thrpt 25 73.676 ± 8.999 ops/s ChainBench.mapLargeVector thrpt 25 132.443 ± 2.360 ops/s ChainBench.mapSmallChain thrpt 25 24047623.583 ± 1834073.508 ops/s ChainBench.mapSmallList thrpt 25 21482014.328 ± 387854.819 ops/s ChainBench.mapSmallVector thrpt 25 34707281.383 ± 382477.558 ops/s ChainBench.reverseLargeChain thrpt 25 37700.549 ± 154.942 ops/s ChainBench.reverseLargeList thrpt 25 142.832 ± 3.626 ops/s
While not dominant,
Chain performance is in the middle of the pack for most operations benchmarked.
Chain does have poor random access performance, and should be avoided in favor of
Vector for random access heavy use cases.
Chain excels with concatenation heavy workloads and has comparable performance to
Vector for most other operations.
So next time you write any code that uses
Vector as a Monoid, be sure to use
Note: All benchmarks above were run using JMH 1.32 with Scala 2.13.8 on JDK 11. For full details, see here. You can also check out the benchmark source code.