Shape-agnostic programming in Scala 3 with tiny capabilities

Keep calm and de-signal virtue, signal types! Less outrage, more Iterator.

Generic code that transforms one container into another often gets stuck when you do not know what the containers are. You would like to write a function that accepts an F[A], applies a function A => B, and returns a G[B], yet F and G are only type variables. In this article I explain a small pattern that solves this problem in a direct way. The idea is simple. Describe what you need from the source shape to read elements, then describe what you need from the target shape to build elements. Write algorithms against these small capabilities, then add instances for each container you care about. The result is ergonomic, efficient, and easy to extend.

The goal

You want to express a function that maps across one shape and lands in another while staying generic. A signature that captures the intent is shown below.

def somefunc[F[_], G[_], A, B](fa: F[A])(f: A => B): G[B]

Without further structure there is no way to iterate fa or to append into G[B]. The pattern introduces two families of tiny typeclasses. One family reads values out of any F, the other family builds values into any G. Reading is done by exposing an Iterator[A] for any F[A]. Writing is done in two flavors because different targets prefer different building strategies. Lists like cons then reverse, vectors and sets like append. There is also a convenience constructor that builds a target directly from an iterator. The interfaces are shown below.

// Read-side
trait Stepper[F[_]]:
  def iterator[A](fa: F[A]): Iterator[A]

// Write-side, append style
trait AppendK[G[_]]:
  def empty[A]: G[A]
  def append[A](ga: G[A], a: A): G[A]

// Write-side, cons then reverse style
trait ConsK[G[_]]:
  def empty[A]: G[A]
  def cons[A](h: A, t: G[A]): G[A]

trait ReverserK[G[_]]:
  def reverse[A](ga: G[A]): G[A]

// Convenience factory
trait FactoryK[G[_]]:
  def fromIterator[A](it: Iterator[A]): G[A]

Type constructors and how they model the world

A type constructor like F[_] is a function at the level of types. It takes a type such as A and returns a new type such as F[A]. This simple idea gives you a precise way to talk about structure that lives around values. In category theory terms, a unary type constructor in Scala 3 can be viewed as an endofunctor on the category of Scala types and total functions. It maps objects, which are types, and arrows, which are functions. If f: A => B, then a lawful functor supplies map(f): F[A] => F[B]. The functor laws state two simple requirements. Mapping identity does nothing. Mapping a composition equals composition of maps. These laws make programs easier to reason about because they explain how structure is preserved when you transform values.

This perspective becomes concrete when you look at common data shapes. Option[A] represents optionality. The world often has missing or unavailable values. List[A] represents many. The world often has collections. Either[E, A] represents a computation that either fails with an error or succeeds with a result. The world often has operations that can fail. Each of these type constructors gives you a disciplined way to encode a real situation. You do not only say what values exist. You say what structure those values live inside.

Parametricity explains why generic code over F[_] is powerful. A function that works for all F and only uses declared capabilities cannot make up a value of A from nothing. It cannot peek inside F[A] without the operations you provide. This constraint is a feature. From it you get free theorems that describe behavior that must hold regardless of the underlying representation. When you later change a concrete container, the generic algorithm continues to work because it depends only on the abstract interface and on the laws.

Much of real modeling is about shape and behavior over time. Algebraic views make this precise. Many data types used in practice are polynomial functors built from sums and products. A list can be seen as either empty or a pair of head and tail. This is a sum of a unit and a product. Initial algebras capture finite inductive data such as lists or trees. Final coalgebras capture potentially infinite or observable processes such as streams. Thinking in these terms helps you decide if your domain concept is better seen as a thing that is built up or as a thing that unfolds. In both cases the thing is carried by a type constructor that organizes values with a clear shape.

Effects fit into the same picture. An effect type like IO[A] is also a constructor. It does not hold many A values the way a list does. It holds a recipe for producing one later, possibly with resource usage or failure. Applicatives and monads explain how to combine these recipes. Applicative combination models independent composition with pure and map2. Monadic combination models sequential composition where later steps can depend on earlier results. These algebraic interfaces are not decoration. They encode the real rules of the domain. If two operations must be independent, keep them at the applicative level. If one step must read a value produced earlier, reach for monadic code.

Bridges between constructors are first class as well. A natural transformation from F to G takes each F[A] to G[A] in a way that respects mapping. This is useful when you want to change representation without changing meaning. Moving from List to Vector for performance while keeping program structure is a common example. The transformation expresses that the choice of container is an implementation detail under a stable interface.