Builder with cheap concatenation. Like the builder type from Data.Builder.ST, this builder can be stored somewhere and this used again later. However, this builder type has several advantages:

• Supports both cons and snoc (Data.Builder.ST only supports snoc)
• No linear-use restriction
• Extremely cheap concatenation (not supported by Data.Builder.ST at all)

In exchange for all of these, this implementation trades performance. Performance is degraded for two reasons:

• Evaluation of the builder is deferred, and the evaluation requires walking a tree of nodes.
• This builder stores individual elements rather than chunks. There is no fundamental reason for this. It is possible to store a SmallArray in each Cons and Snoc instead, but this makes the implementation a little more simple.

One reason to prefer this module instead of Data.Builder.ST is that this module lets the user works with builder in a more monoidal style rather than a stateful style. Consider a data type with several fields that is being converted to a builder. Here, Data.Builder.ST would require that Builder appear as both an argument and an result for each field's encode function. The linearly-used builder must be threaded through by hand or by clever use of StateT. With Data.Builder.Catenable, the encode functions only need return the builder.