Collecting collectables
Most programming languages provide a variety of built-in types. Some are used more often than others; some are simple, while others are complex. Numbers and booleans, for example, appear in many languages. Another pervasive abstraction is more complicated and can be surprisingly difficult to use safely: the collection.
Group of items #
A collection is a grouping of items[1] together with operations for accessing or manipulating them. Arrays, lists, dictionaries and even tuples can all be viewed as collections, although they preserve different information about their elements. Collections are so pervasive that you can find them in some unexpected places[2]:
a_index=(one two three) # create an array with a few elements
a_index+=(four five) # append some elements
a_index[9]=ten # add a specific index
for elem in "${a_index[@]}"; do # iterate over the elements
echo "$elem"
done
for idx in "${!a_index[@]}"; do # iterate over the array indices
printf "%d\t%s\n" "$idx" "${a_index[idx]}"
done
Element types #
Parameterized collection types let us create collections with different element types:
const array1 = [1, 2, 3];
const array2 = ['1', '2', '3'];
Or collections consisting of different types:
const array1 = [1, '2', true];
The second example is a lot more nuanced. It is trivial to create a collection of values of different types when we know those types upfront. But is it possible to create a general-purpose type that represents a collection of elements of different types and remains type-safe? The right representation depends on what you need to know about each element.
For example, a tuple is the simplest case:
type Items = [string, number, boolean];
const items: Items = ["hello", 41, true];
const a = items[0]; // string
const b = items[1]; // number
const c = items[2]; // boolean
This is fully type-safe, but the position determines the type. It works when the structure and length are known in advance. If the collection can have arbitrary length but only a known set of types, use a union:
type Item = string | number | boolean;
const items: Item[] = [
"hello",
42,
true,
"world"
];
for (const item of items) {
if (typeof item === "string") {
console.log(item.toUpperCase());
} else if (typeof item === "number") {
console.log(item.toFixed(2));
}
}
This is type-safe, but you lose the exact type of an individual element until you narrow it. A much stronger pattern is a discriminated union:
type Item =
| { type: "text"; value: string }
| { type: "number"; value: number }
| { type: "flag"; value: boolean };
const items: Item[] = [
{ type: "text", value: "hello" },
{ type: "number", value: 42 },
{ type: "flag", value: true }
];
for (const item of items) {
switch (item.type) {
case "text":
console.log(item.value.toUpperCase());
break;
case "number":
console.log(item.value.toFixed(2));
break;
case "flag":
console.log(item.value ? "yes" : "no");
break;
}
}
Here TypeScript knows the exact type of value after checking the type discriminant. You can also wrap this in a generic collection class:
class HeterogeneousCollection<T> {
private readonly items: T[] = [];
add(item: T): void {
this.items.push(item);
}
get(index: number): T | undefined {
return this.items[index];
}
values(): readonly T[] {
return this.items;
}
}
type Item =
| { type: "text"; value: string }
| { type: "number"; value: number }
| { type: "flag"; value: boolean };
const collection = new HeterogeneousCollection<Item>();
collection.add({ type: "text", value: "hello" });
collection.add({ type: "number", value: 42 });
collection.add({ type: "flag", value: true });
// compile error:
collection.add({ type: "number", value: "wrong" });
Heterogeneous lists in theory #
An ordinary homogeneous list has one element type. A List<A> may contain any number of values, but every position contains an A. Its length is generally a runtime property, while its element type is known statically.
A heterogeneous list (HList)[3] reverses that trade-off. Its type records an ordered sequence of element types:
HList<[String, Number, Boolean]>
A value of this type must contain a string in the first position, a number in the second and a boolean in the third. Both the length and the type at each position are therefore part of the static structure. In that sense, an HList is closer to a recursively constructed tuple than to an ordinary list.
The structure can be defined inductively with two cases:
empty : HList<[]>
cons : A × HList<Types>
→ HList<[A, ...Types]>
The empty case provides the starting point. The cons case adds a value of type A to an HList whose existing type sequence is Types; the result records A at the front of that sequence. An append-based builder follows the same principle at the opposite end.
Element type memory #
The union examples define the permitted set of element types first and only then use the collection. An HList can instead remember an inferred type at every position. Consider this example:
const collection = hetero()
.add("hello")
.add(42)
.add(true);
// type:
// Hetero<[string, number, boolean]>
collection.get(0); // string
collection.get(1); // number
collection.get(2); // boolean
Here the collection remembers the exact type of every element as you add it. That can be implemented using variadic tuple types and generics. The key idea is that the collection's type evolves as values are added.
type StrToNum<T> = T extends `${infer N extends number}` ? N : never;
type TupleIndex<T extends readonly unknown[]> = StrToNum<keyof T>;
class HList<T extends readonly unknown[]> {
private constructor(
private readonly values: T
) {}
static empty(): HList<[]> {
return new HList([]);
}
add<A>(value: A): HList<[...T, A]> {
return new HList([...this.values, value]);
}
get<I extends TupleIndex<T>>(index: I): T[I] {
return this.values[index];
}
}
const xs = HList.empty()
.add("Test")
.add(41)
.add(true)
.add({ x: 10, y: 20 });
TupleIndex<T> extracts only the tuple's finite numeric positions, so an access such as xs.get(4) is rejected rather than being treated as a general array lookup. TypeScript carries the entire heterogeneous structure in the generic parameter.
One important limitation: this works because the collection is immutable. This would fundamentally break the model:
const xs = HList.empty();
xs.add("hello");
xs.get(0);
If add() mutated xs, its static type would have to change from:
HList<[]> to HList<[string]>
TypeScript variables don't change their static generic type as a side effect of calling a method. Returning a new value with a new type solves that:
const a = HList.empty(); // HList<[]>
const b = a.add("x"); // HList<[string]>
const c = b.add(42); // HList<[string, number]>
There are plenty of collections that also let you mutate data, such as arrays. Here is how we can implement an array-like heterogeneous collection, but with an important constraint: if the index is known at compile time, TypeScript can make indexed access type-safe:
type StrToNum<T> = T extends `${infer N extends number}` ? N : never;
type TupleIndex<T extends readonly unknown[]> = StrToNum<keyof T>;
class HArray<T extends unknown[]> {
constructor(private readonly values: T) {}
static empty(): HArray<[]> {
return new HArray([]);
}
add<A>(value: A): HArray<[...T, A]> {
return new HArray([...this.values, value]);
}
get<I extends TupleIndex<T>>(index: I): T[I] {
return this.values[index];
}
set<I extends TupleIndex<T>>(index: I, value: T[I]): void {
this.values[index] = value;
}
}
const xs = HArray.empty()
.add("hello")
.add(42)
.add(true);
xs.get(0); // string
xs.get(1); // number
xs.get(2); // boolean
xs.set(0, "world"); // OK
xs.set(1, 100); // OK
xs.set(2, false); // OK
xs.set(0, 123);
// ^^^
// error: number isn't assignable to string
xs.set(1, "hello");
// ^^^^^^^
// error: string isn't assignable to number
Array index syntax #
But can we use actual [] indexing syntax? Instead of wrapping the tuple in a class, let the tuple itself be the collection. The problem then becomes how to construct such a tuple incrementally without declaring its types or length upfront. That is solvable with a builder, provided the sequence of additions is statically visible to TypeScript:
function add<T extends unknown[], A>(
xs: T,
value: A
): [...T, A] {
return [...xs, value];
}
const a = add([], "hello");
// [string]
const b = add(a, 42);
// [string, number]
const c = add(b, true);
// [string, number, boolean]
c[0]; // string
c[1]; // number
c[2]; // boolean
c[0] = "world"; // OK
c[1] = 100; // OK
c[0] = 100;
// error
It is a tuple whose type is progressively constructed using variadic tuple types. There is still a limitation, though. If the index itself is known only at runtime, such as const i: number, TypeScript cannot know that xs[i] is specifically a string or number. This remains true even if we combine HArray with the builder:
class HArray<T extends unknown[]> {
private constructor(
private readonly values: T
) {}
static empty(): HArray<[]> {
return new HArray([]);
}
add<A>(value: A): HArray<[...T, A]> {
return new HArray([...this.values, value]);
}
build(): T {
return [...this.values] as T;
}
}
const xs = HArray.empty()
.add("hello")
.add(42)
.add(true)
.build();
const a = xs[0]; // string
const b = xs[1]; // number
const c = xs[2]; // boolean
xs[0] = "world"; // OK
xs[1] = 100; // OK
xs[2] = false; // OK
xs[0] = 123; // Compile-time error
xs[1] = "abc"; // Compile-time error
TypeScript cannot guarantee that its runtime structure remains consistent with its tuple type.
xs.push("another"); // Allowed!
xs.pop(); // Also allowed!
Fundamental design #
The fundamental design choice remains. We want three properties:
- Incremental construction without declaring the types and length upfront.
- Type-safe indexed reads and writes.
- Protection against structural mutations that invalidate the types.
A native mutable tuple gives us the first two properties, but not the third. Encapsulation can protect the structural invariant at runtime, even when the language cannot express the entire sequence of element types statically.
Typed index tokens #
C# can achieve all three practical safety properties if we replace integer indices with typed index tokens.
using System;
using System.Collections.Generic;
public sealed class HArray
{
public sealed class Key<T>
{
internal HArray Owner { get; }
internal int Index { get; }
internal Key(HArray owner, int index)
{
Owner = owner;
Index = index;
}
}
private readonly List<object?> values = new();
public Key<T> Add<T>(T value)
{
var key = new Key<T>(this, values.Count);
values.Add(value);
return key;
}
public T Get<T>(Key<T> key)
{
EnsureOwner(key);
return (T)values[key.Index]!;
}
public void Set<T>(Key<T> key, T value)
{
EnsureOwner(key);
values[key.Index] = value;
}
private void EnsureOwner<T>(Key<T> key)
{
if (!ReferenceEquals(key.Owner, this))
{
throw new ArgumentException(
"The key belongs to another collection.",
nameof(key));
}
}
}
public static class Example
{
public static void Main()
{
var xs = new HArray();
var name = xs.Add("hello"); // Key<string>
var age = xs.Add(42); // Key<int>
var active = xs.Add(true); // Key<bool>
string a = xs.Get(name);
int b = xs.Get(age);
bool c = xs.Get(active);
xs.Set(name, "world"); // OK
xs.Set(age, 100); // OK
xs.Set(age, "hello"); // Compile-time error
}
}
There are two distinct kinds of type safety here.
- Position-based type safety:
xs[1]statically returns int. TypeScript can achieve this with tuples; C# cannot generalize it to arbitrary heterogeneous collections. - Key-based type safety:
xs.Get(age)statically returns int. Both languages can achieve this, and C# can enforce ownership and structural invariants at runtime through encapsulation.
Typed keys trade familiar integer-index syntax for a safer API. A language with a richer static type system can instead encode the collection's complete structure and valid positions in types.
Type-safe indexed access #
Haskell is particularly interesting because, unlike C#, it can represent a heterogeneous collection's structure at the type level and perform type-safe indexed access. With DataKinds[4], GADTs[5], type families[6] and type-level natural numbers, we can implement all three properties:
- Construct a heterogeneous collection incrementally without declaring its element types or length upfront, as long as the construction remains statically visible.
- Read and replace elements using indices, with the compiler determining each element's type.
- Prevent structural mutations that invalidate the collection's type.
Heterogeneous list #
We can implement an HList using a GADT:
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeOperators #-}
import Data.Kind (Type)
data HList (xs :: [Type]) where
HNil :: HList '[]
(:&) :: x -> HList xs -> HList (x ': xs)
infixr 5 :&
The type parameter xs is a type-level list describing the type of every element. For example:
xs :: HList '[String, Int, Bool]
xs = "hello" :& 42 :& True :& HNil
The compiler knows the type at every position. But we can also let Haskell infer the entire structure:
xs = "hello" :& (42 :: Int) :& True :& HNil
No predefined collection schema is necessary.
Index access #
First, we define a type-level function that determines the type at a given index:
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
import GHC.TypeNats (Nat, type (-))
type family At (n :: Nat) (xs :: [Type]) :: Type where
At 0 (x ': xs) = x
At n (x ': xs) = At (n - 1) xs
Now we can implement indexed access using a type class:
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
import Data.Proxy (Proxy(..))
class HGet (n :: Nat) (xs :: [Type]) where
hget :: Proxy n -> HList xs -> At n xs
instance HGet 0 (x ': xs) where
hget _ (x :& _) = x
instance
(HGet (n - 1) xs, At n (x ': xs) ~ At (n - 1) xs)
=> HGet n (x ': xs) where
hget _ (_ :& xs) = hget (Proxy @(n - 1)) xs
There is a technical problem with this implementation: the instances overlap, and GHC's type-family reduction and instance selection need additional machinery. Rather than complicating the design with overlapping instances, we can make use of a recursively defined index.
Recursive index #
Peano natural numbers as indices? Why not?
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.Kind (Type)
data Nat = Z | S Nat
data Fin (n :: Nat) where
FZ :: Fin ('S n)
FS :: Fin n -> Fin ('S n)
data HList (xs :: [Type]) where
HNil :: HList '[]
(:&) :: x -> HList xs -> HList (x ': xs)
infixr 5 :&
type family At (n :: Nat) (xs :: [Type]) :: Type where
At 'Z (x ': xs) = x
At ('S n) (x ': xs) = At n xs
Now we define a type-indexed accessor:
data Index (n :: Nat) (xs :: [Type]) where
IZ :: Index 'Z (x ': xs)
IS :: Index n xs -> Index ('S n) (x ': xs)
get :: Index n xs -> HList xs -> At n xs
get IZ (x :& _) = x
get (IS i) (_ :& xs) = get i xs
And the usage:
xs = "hello" :& (42 :: Int) :& True :& HNil
a = get IZ xs
-- String
b = get (IS IZ) xs
-- Int
c = get (IS (IS IZ)) xs
-- Bool
d = get (IS (IS (IS IZ))) xs
-- Compile-time error
Notice that
Index n xsacts as a proof that positionnexists in the heterogeneous listxs
Type-safe replacement #
Now, let's implement the setter:
set
:: Index n xs
-> At n xs
-> HList xs
-> HList xs
set IZ value (_ :& xs) =
value :& xs
set (IS i) value (x :& xs) =
x :& set i value xs
xs = "hello" :& (42 :: Int) :& True :& HNil
ys = set IZ "world" xs
zs = set (IS IZ) 100 ys
invalid = set (IS IZ) "hello" xs
-- Fails at compile time because index 1 expects Int, not String.
Dynamic construction #
We can also define an append operation:
type family Append (xs :: [Type]) (ys :: [Type]) :: [Type] where
Append '[] ys = ys
Append (x ': xs) ys = x ': Append xs ys
append
:: HList xs
-> HList ys
-> HList (Append xs ys)
append HNil ys = ys
append (x :& xs) ys = x :& append xs ys
add
:: HList xs
-> a
-> HList (Append xs '[a])
add xs value = append xs (value :& HNil)
-- Now we have something very similar to the TypeScript builder:
xs =
add
(add
(add HNil "hello")
(42 :: Int))
True
There is one fundamental limitation shared by TypeScript and Haskell: the compiler must have enough static information about the index. If an index is an arbitrary integer obtained at runtime, the compiler cannot generally determine one specific return type. A runtime index requires bounds checking and, for heterogeneous lists, some way of representing the unknown element type.
We can make the implementation a bit more interesting by eliminating the explicit Index constructors and supporting syntax such as:
get @0 xs -- String
get @1 xs -- Int
get @2 xs -- Bool
That is possible with TypeApplications[7] and a type-class-based lookup, giving us an API very close to TypeScript's xs[0]. We can implement get @0 xs, get @1 xs, and set @1 value xs using GHC's type-level natural numbers (Nat), visible type application and a recursive type class. The compiler will infer the element type from the index, reject invalid assignments, and reject out-of-bounds indices.
Complete implementation #
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
import Data.Kind (Type)
import GHC.TypeNats (Nat, type (-), type (<=)) -- 1 <= n constraint
-- Heterogeneous list
data HList (xs :: [Type]) where
HNil :: HList '[]
(:&) :: x -> HList xs -> HList (x ': xs)
infixr 5 :&
-- Type of the element at index n
type family At (n :: Nat) (xs :: [Type]) :: Type where
At 0 (x ': xs) = x
At n (x ': xs) = At (n - 1) xs
type family Append (xs :: [Type]) (ys :: [Type]) :: [Type] where
Append '[] ys = ys
Append (x ': xs) ys = x ': Append xs ys
-- Recursive index traversal
class HIndex (n :: Nat) (xs :: [Type]) where
get :: HList xs -> At n xs
set :: At n xs -> HList xs -> HList xs
instance {-# OVERLAPPING #-} HIndex 0 (x ': xs) where
get (x :& _) = x
set value (_ :& xs) = value :& xs
instance {-# OVERLAPPABLE #-}
( 1 <= n
, HIndex (n - 1) xs
, At n (x ': xs) ~ At (n - 1) xs
) => HIndex n (x ': xs) where
get (_ :& xs) = get @(n - 1) xs
set value (x :& xs) =
x :& set @(n - 1) value xs
append :: HList xs -> HList ys -> HList (Append xs ys)
append HNil ys = ys
append (x :& xs) ys = x :& append xs ys
add :: HList xs -> a -> HList (Append xs '[a])
add xs value = append xs (value :& HNil)
xs =
"hello" :&
(42 :: Int) :&
True :&
HNil
-- Reading
a = get @0 xs -- String
b = get @1 xs -- Int
c = get @2 xs -- Bool
-- Replacing
ys = set @0 "world" xs
zs = set @1 100 ys
result = get @1 zs -- Int, value 100
-- With indices
xs' = add
(add
(add HNil "hello")
(42 :: Int))
True
a' = get @0 xs' -- String
b' = get @1 xs' -- Int
ys' = set @1 100 xs' -- HList '[String, Int, Bool]
zs' = add ys' (3.14 :: Double) -- HList '[String, Int, Bool, Double]
c' = get @3 zs' -- Double
Comparing all three languages #
| Capability | TypeScript | C# | Haskell |
|---|---|---|---|
| Infer heterogeneous structure | Yes | Limited | Yes |
| Track arbitrary-length type sequence | Yes | No | Yes |
| Compile-time typed positional access | Yes | Limited to fixed structures | Yes |
| Compile-time checked replacement | Yes | Limited to fixed structures | Yes |
| Compile-time bounds checking | Yes, with suitable tuple APIs | Limited | Yes |
| Preserve structure through encapsulation | Yes | Yes | Yes |
| Type-level computation over element types | Yes | Limited | Yes |
Conclusion #
TypeScript and Haskell can encode this structure directly, although they use very different tools: variadic tuple types in TypeScript and type-level lists in Haskell. C# works well when the number of elements is fixed, but its type system does not naturally express an arbitrary-length sequence of element types. In all three languages, a runtime index remains fundamentally different from a compile-time-known index and requires a less precise result or an explicit runtime check.
The right representation therefore depends on what the program needs to preserve. Use a homogeneous collection when every element is handled in the same way, a union or tagged union when the set of possible types matters, and a tuple or heterogeneous list when both position and type are part of the structure. Type safety comes not from the collection alone, but from choosing a type that retains exactly the information the program will need later.
Source code #
Reference implementation (opens in a new tab)
References
- Collection (abstract data type) (opens in a new tab) · Back
- Collections — UNIX Shell (opens in a new tab) · Back
- Heterogeneous collections (opens in a new tab) · Back
- Datatype promotion — GHC User's Guide (opens in a new tab) · Back
- Generalised algebraic datatype (opens in a new tab) · Back
- Type families (opens in a new tab) · Back
- Visible type application — GHC User's Guide (opens in a new tab) · Back