IOList

IOList module: lazy, tree-structured string builder.

IOList represents a sequence of string segments as a tree, deferring concatenation until the list is flushed to IO. This avoids O(n²) copying when building large strings from many small pieces.

Usage pattern: march> let buf = IOList.append(IOList.from_string("Hello, "), IOList.from_string("world!")) march> IOList.to_string(buf) "Hello, world!"

The key invariant: IOList is lazy. Use it as an accumulator and only call to_string or write to IO at the very end.

Types

typeIOListIOList = Empty | Str(String) | Segments(List(IOList))#

Internal representation: Empty — zero bytes Str(s) — a single String segment Segments(xs) — a list of IOList nodes (children)

There is intentionally no binary Concat node. Building chains of Segments avoids deep left-spine trees that would overflow the stack when flattening.

Functions

fnappendappend(a : IOList, b : IOList) : IOList#

Append two IOLists, returning a new IOList that represents their concatenation. Neither argument is modified.

march> IOList.to_string(IOList.append(IOList.from_string("foo"), IOList.from_string("bar")))
"foobar"

Internally, Empty nodes are dropped. No bytes are copied until to_string.

Cost: O(1) — no flattening until to_string.

fnbyte_sizebyte_size(iol : IOList) : Int#

Compute the total byte size of all segments in the IOList without flattening to a string.

march> IOList.byte_size(IOList.from_string("hello"))
5
march> IOList.byte_size(IOList.empty())
0

Cost: O(number of nodes in the tree).

fnemptyempty() : IOList#

The empty IOList — contains no bytes.

march> IOList.to_string(IOList.empty())
""

Cost: O(1).

fnfrom_stringfrom_string(s : String) : IOList#

Wrap a String as an IOList leaf node.

march> IOList.to_string(IOList.from_string("hello"))
"hello"

No copy is made; the IOList holds a reference to the original string. Cost: O(1).

fnfrom_stringsfrom_strings(xs : List(String)) : IOList#

Build an IOList from a List(String) by wrapping all elements as leaves.

march> IOList.to_string(IOList.from_strings(["a", "b", "c"]))
"abc"

Cost: O(n) where n is the length of the list.

fnhashhash(iol : IOList) : String#

Compute a FNV-1a 64-bit content hash over the IOList segments without first flattening to a single string. Returns a 16-character lowercase hex string suitable for use as an ETag value.

march> IOList.hash(IOList.from_string("hello"))
"a430d84680aabd0b"
march> IOList.hash(IOList.empty())  -- the FNV-1a offset basis
"cbf29ce484222325"

The hash walks the IOList tree in order, hashing each Str segment's bytes as encountered. The result is identical to hashing the fully flattened string.

Suitable for ETag generation and fragment cache keying. Cost: O(total bytes across all segments).

fnis_emptyis_empty(iol : IOList) : Bool#

Return true if the IOList contains no bytes.

march> IOList.is_empty(IOList.empty())
true
march> IOList.is_empty(IOList.from_string(""))
true
march> IOList.is_empty(IOList.from_string("x"))
false

Cost: O(1) for Empty and Str; O(n) for Segments.

fnprependprepend(s : String, iol : IOList) : IOList#

Prepend a String to an IOList.

march> IOList.to_string(IOList.prepend("Hello, ", IOList.from_string("world!")))
"Hello, world!"

Cost: O(1).

fnpushpush(iol : IOList, s : String) : IOList#

Append a String to an IOList.

march> let buf = IOList.push(IOList.from_string("Hello"), ", world!")
march> IOList.to_string(buf)
"Hello, world!"

Cost: O(1).

fnto_stringto_string(iol : IOList) : String#

Flatten an IOList into a single String by collecting all leaf segments and concatenating them.

march> IOList.to_string(IOList.empty())
""
march> IOList.to_string(IOList.from_string("hello"))
"hello"

This is the only function that allocates a full concatenated string. Call it once at the end, not on every append.

Cost: O(total bytes across all segments).