What even is a list?

You usually think of a list as a series of elements, right?

[1, 2, 3, 4]

Let's call this the "producer" view of the data structure. The list [1,2,3,4] will produce the values 1, then 2, then 3, then 4.

The other (weird, inverted) way to think of a list is "a thing that can feed a consumer". From this perspective, the list [1,2,3,4] is a thing that, when given a consumer, will feed that consumer the values 1, then 2, then 3, then 4.

There are a lot of ways that a consumer of a list might work (think List.foldLeft, List.foldRight, or arbitrary recursive functions that consume a list) but let's for now just pick a model and say that a list consumer is a left fold, with some effects. More on this choice later.

Here's a type, Foldable which defines a list as "a thing that can be folded". Give this type a minute for this type to sink in, it's rather brain-bendy!

type Foldable a = Foldable (∀ r g. r -> (r -> a ->{g} r) ->{g} r)

That is, a : Foldable Nat is something that can feed values to any consumer of Nat. The forall in g and r here tells us that the consuming left fold can produce an arbitrary result type r, and it can use arbitrary effects g. A Foldable must be capable of feeding all such consumers.

Here's how you create a Foldable from a List and how you go the other direction:

Foldable.fromList : [a] -> Foldable a
Foldable.fromList as = Foldable (r f -> List.foldLeft f r as)

Foldable.toList : Foldable a -> [a]
Foldable.toList = cases Foldable cb -> cb [] (acc a -> acc List.:+ a)

These definitions are again a bit brain-bendy, but it's the kind of code that only typechecks one way. The Foldable.fromList function just calls List.foldLeft with the consuming functions it's given. And Foldable.toList passes in a consumer that builds up a List.

The first time you write functions in this weird upside down world, you brain might explode and you'll feel like a supergenius just getting it to typecheck. Eventually you'll get the hang of it and find it's kinda fun.

Foldable.fromList [1, 2, 3, 4] |> Foldable.toList

[1, 2, 3, 4]

Fusion for free

Operations on Foldable like Foldable.map are "just" going to transform the consuming fold in some way. They don't materialize the intermediate list, they're just composing some functions, so a pipeline of transformations will fuse together:

Foldable.fromList [1, 2, 3, 4]
  |> Foldable.map (x -> x Nat.* 100)
  |> Foldable.map Nat.increment
  |> Foldable.toList

[101, 201, 301, 401]

Here's the implementation of Foldable.map. It's a bit brain-bendy but it works and only typechecks one way:

Foldable.map : (a -> b) -> Foldable a -> Foldable b
Foldable.map f = cases
  Foldable cb -> Foldable (r op -> cb r (r a -> op r (f a)))

You can implement many of the usual operations like filter, flatMap, and more; they fuse together like you'd expect. I recommend trying these as a fun exercise. And by fun I mean you brain might melt.

Stateful transformations with early termination

Because we get to pick the consuming fold for our Foldable, and the consuming fold is allowed to use arbitrary effects of any g type we want, we can get different behaviors by getting creative about our choice of g.

For instance Foldable.take can be implemented by picking a g that includes a combination of Early for early termination, and Scope to for a local mutable reference used to halt the fold when its count reaches 0.

Here in this example, I'm creating an infinite Foldable of Nat, applying a couple transformations, then doing Foldable.take. This would never terminate if the intermediate sequences were being materialized!

Foldable.from 0
  |> Foldable.map Nat.increment
  |> Foldable.map (x -> x Nat.* 1000)
  |> Foldable.take 5
  |> Foldable.toList

[1000, 2000, 3000, 4000, 5000]

This pipeline fuses together, with all those operations happening with a single fold and only the first 5 steps of it computed. No fancy optimizers needed.

How to pick the consumer shape

Earlier I mentioned that you can think of a list as "a thing that can feed a consumer". But there are lots of ways to consume a list besides just "an effectful left fold" and it's the same with other data structures. How do you know what representation of consumer to pick?

The trick is to look at the functions you want to fuse for your data structure and see what information those functions really need. Do they really need to be arbitrary pattern matching on the producer, or can they just give the producer some simple "instructions"?

You can get a richer set of fuseable operations by increasing the capabilities of your consumers, but the more capable your consumers, the more this constrains the implementation of the producer. For instance, suppose our list consumers could request arbitrary values from the producer in a random access fashion; that means that producers will need to support random access as well.

You often don't need a fancy optimizer

Laziness and this technique achieve some of the efficiency improvements that languages or frameworks achieve with with an optimizer that transforms a syntax tree of the code.

On the one hand, the syntax tree is the most flexible thing to work with. Any optimization you can think of is ultimately converting code expressed one way to code expressed in a different (more efficient) way. But this flexibility of the syntax tree comes at a cost. It's complicated to create and transform syntax trees and it also puts you in a difficult position of needing to decide on a fixed set of operations for your domain.

Instead of reaching for a syntax tree and optimizer, you can instead try thinking in advance about what optimizations you want to support on your data type and then see if you can craft a representation where those optimizations come for free or are done "as you go".