
\documentclass[12pt]{article}
\usepackage[T2A,OT1]{fontenc}
\usepackage[default]{cantarell}
\usepackage[a4paper, top=20mm, bottom=20mm, left=20mm, right=20mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}
\usepackage{tabu}
\usepackage{hyperref}
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}
\usepackage{setspace}
\onehalfspacing
\author{Artyom Bologov \href{mailto:lambda-5@aartaka.me}{(email)}}
\date{\today}
\title{Making Sense of Lambda Calculus 5: Bring Computation to (Aggregate) Data}
\makeatletter
\def\endenv{\expandafter\end\expandafter{\@currenvir}}
\makeatother
\begin{document}
\maketitle

\includegraphics[width=\textwidth,height=\textheight,keepaspectratio]{./assets/lambda-5.png}

\paragraph{Timeline of Making Sense of Lambda Calculus} \begin{quote}
\begin{itemize}\item \href{run:lambda-0}{0: Abstration, Reduction, Substitution?}
\item \href{run:lambda-1}{1: Ignorant, Lazy, and Greedy Evaluation}
\item \href{run:lambda-2}{2: Numerous Quirks of Numbers}
\item \href{run:lambda-3}{3: Truth or Dare With Booleans}
\item \href{run:lambda-4}{4: Applicative vs. Normal Order}
\item \href{run:lambda-5}{5: Bring Computation to (Aggregate) Data}
\item \href{run:threading}{Interlude: Functional Threading “Macros”}
\item \href{run:lambda-6}{6: Recurring Problems}
\end{itemize}
\end{quote}

So we’ve covered
\href{run:lambda-2}{numbers as compositions} and
\href{run:lambda-3}{booleans as branches} in this series of posts.
But both of these are “primitive” data types.
We need aggregate types to build the whole world out of!
This post goes over techniques to build data types in Lambda Calculus.
And some conventional types too.

\paragraph{Note on syntax} \begin{quote}
Starting with this post, I’ll use syntax of
\href{https://github.com/aartaka/lamber}{Lamber, my Lambda Calculus-based programming language}.
I find it more readable than conventional single-letter-single-argument lambdas.
\end{quote}

\section*{Conses/Tuples/Pairs: All You Need} \label{cons}

An idea that generalizes to all of this post (and beyond:)
Bring computation to data, not the other way around.
It’s a bit of a brain teaser, but let’s see for ourselves.
Conses (or pairs, or tuples) are two-element collections.
With “car” (head) and “cdr” (tail):

\begin{figure}[h!]\begin{verbatim}
def cons fn (car cdr)
  (fn (f) f car cdr) .
\end{verbatim}\caption{Cons type definitions}\end{figure}

So cons takes two things: \verb|car| and \verb|cdr|.
Then it takes a third argument, a function.
\href{run:lambda-0}{It’s curried, so we don’t have to provide this function upfront (section currying)}.
And applies the function to the first two arguments.
That’s what I was talking about.
Make cons user provide their action on data.
Don’t just provide the data to them.

Now the simplest action might be fetching values.
Here are two functions for fetching cons parts.

\begin{figure}[h!]\begin{verbatim}
def car fn (pair)
  pair (fn (a b) a) .

def cdr fn (pair)
  pair (fn (a b) b) .
\end{verbatim}\caption{Cons accessors}\end{figure}

See that?
We apply the data structure to the accessor function.
Not the other way around.
It’s counter-intuitive, but useful and generalizes well to other aggregate types.

<h3 nil>On NIL</h2>

An important thing to all this cons business is NIL.
The cons terminator, the final
\href{#trees}{list/tree} element.
NIL is useful, because it’s also a representation of an empty list.
Data structures are useless if you don’t have a way to represent empty states, right?

NIL has two canonical representations with separate handling routines:

\begin{figure}[h!]\begin{verbatim}
def nil false .
def alt-nil (fn x true) .
\end{verbatim}\caption{Two different representations of NIL}\end{figure}

The former seems to be a consensus and it has a nice property:
it’s 0, False, and NIL, all at the same time.
Consistent and beautiful.
With it, functions for NIL-aware \verb|cons| iteration are elegant enough:
just provide two values

\begin{itemize}\item A function to apply to the head and tail if this is a cons;
\item And a default value if it’s a NIL.
\end{itemize}

Null check, for example, is booleans (plus some formalities) applied to the pair:

\begin{figure}[h!]\begin{verbatim}
def null fn (pair)
  pair (fn (h t x) false) true .
\end{verbatim}\caption{Definition of null function with NIL = False}\end{figure}

This idiom notably includes a second argument to the pair.
And (respectively) a third argument to the cons-processing function.
This argument (True) is what NIL branch returns.
But if it’s not NIL, this argument has to go somewhere, and that’s the purpose of \verb|x| parameter.
An elegant application of this pattern is \verb|foldr| function:

\begin{figure}[h!]\begin{verbatim}
def foldr fn (f init list)
  local %foldr = fn (h t z)
    f h (t %foldr z)
  end
  list %foldr init
end
\end{verbatim}\caption{Right fold implementation with False-encoded NIL}\end{figure}

We feed \verb|%foldr|, a recursive function, to a cons list, alongside the initial value (a.k.a. init a.k.a. \verb|z|).
If the list is NIL, it returns the init.
If it’s not, it’s applying a recursive function to its head and application of it to the tail and init.
Init is passed deep into the list recursion until there’s NIL.
NIL returns this init and then the whole recursion chain collapses into a final value.
Applying the folded function to init and last element.
Then to the result of that and penultimate element.
Then to the result and the element before that.
Et cetera.

To illustrate, here’s a control flow for \verb|foldr + 0 [1 2 3]|:

\begin{itemize}
\item Apply \verb|[1 2 3]| to fold and 0
\item It’s not NIL, so apply recursive function to head and tail
\item Apply \verb|+| to 1 and...
\begin{itemize}
\item Apply \verb|[2 3]| to fold and 0
\item It’s not NIL, so apply recursive function to head and tail
\item Apply \verb|+| to 2 and...
\begin{itemize}
\item Apply \verb|[3]| to fold and 0
\item It’s not NIL, so apply recursive function to head and tail
\item Apply \verb|+| to 3 and...
\begin{itemize}
\item Apply \verb|[]|/NIL to fold and 0
\item It’s NIL, so just return 0
\end{itemize}
\item Get 3 + 0 = 3
\end{itemize}
\item Get 2 + 3 = 5
\end{itemize}
\item Get 1 + 5 = 6
\item Done, \verb|foldr + 0 [1 2 3]| is 6, all thanks to the beauty of NIL!
\end{itemize}

\par\noindent\rule{\textwidth}{0.4pt}

Wait, but what about \verb|alt-nil|?!
It’s nice in that it allows short and neat \verb|null| check:

\begin{figure}[h!]\begin{verbatim}
def alt-null fn (pair)
  pair (fn (h t) false) .
\end{verbatim}\caption{Alternative NIL check}\end{figure}

If the cons is NIL, it just returns True.
If it’s non-NIL, it applies the function to head and tail and returns False.
Which is quite elegant...
But that’s about it for its benefits—and e.g. \verb|foldr| looks too ugly and explicit with it.
So I prefer the 0/False/Nothing/NIL equality.
All of Lamber list-processing is based on this assumption.

Now, can we generalise all this apply-data-to-function business to something else?

\section*{Triples} \label{triples}

Triples are like tuples/conses, but with three elements.

\begin{figure}[h!]\begin{verbatim}
def triple fn (first second third)
  (fn (f) f first second third) .

def first fn (triple)
  triple (fn (a b c) a) .

;; Et cetera for second and third
\end{verbatim}\caption{Triple definition}\end{figure}

If you want to represent an N-element collection, pass these elements to the constructor.
And wait for the last argument—the function to apply to these.

\section*{Trees} \label{trees}

With these two or three element collections, we can build arbitrarily complex structures.
Cons trees (binary, ternary, or whatever else you come up with.)
That’s what Lisp code is all about—trees of symbols.

\begin{figure}[h!]\begin{verbatim}
cons (cons 1 2)
     (cons (cons 3 (cons 4 nil)) (cons 5 (cons 6 7)))
\end{verbatim}\caption{Cons tree}\end{figure}

Represents a tree with

\begin{itemize}\item 1 and 2 (as one pair)
\item 3 and 4 (as a so-called proper NIL-terminated list)
\item and 5, 6, and 7 (as a chain of conses)
\end{itemize}

Or, visualizing it with a little piece of ASCII art
\href{https://github.com/cbaggers/draw-cons-tree}{(generated by draw-cons-tree)}

\begin{figure}[h!]\begin{verbatim}
[o|o]---[o|o]-------[o|o]-[o|o]-7
 |       |           |     
|[o|o]-2 [o|o]-[o|/]  5     6
 |       |     
| 1       3     4
\end{verbatim}\caption{Cons tree, visualized}\end{figure}

See the tree there?
Not the most readable thing, but the benefit is apparent:
It allows creating arbitrarily complex structures.
So we only need conses, right?
In a sense yes, but there are more tricks and types we can use:

\section*{Union Types} \label{union}

We can increase the number of values we store in the structure, like with triples.
But we can also increase the number of actions!
That’s how union types actually work in LC.
Get multiple functions, one per possible type, and only run the one matching the type.

The most representative union type is Either.
Basically, it’s either Left with one value (usually an error,) or Right with the other value (usually a result.)

\begin{figure}[h!]\begin{verbatim}
def left fn (leftval)
  fn (leftfn rightfn)
    leftfn leftval .

def right fn (rightval)
  fn (leftfn rightfn)
    rightfn rightval .
\end{verbatim}\caption{Either constructors}\end{figure}

There’s only one value now, but two action functions!
If the thing is right, call \verb|rightfn| function, otherwise call \verb|leftfn|.
Now to actual functions processing these:

\begin{figure}[h!]\begin{verbatim}
def isleft fn (either)
  either (fn _ true) (fn _ false) .

def leftval fn (either)
  either identity (fn _ nil) .
\end{verbatim}\caption{Left-related functions}\end{figure}

The pattern repeats: we pass actions to data, not the other way around.
But this time, there are multiple actions we pass.
In this case, checking that the data is Left means passing a True-returning function as \verb|leftfn|.
And getting the left value is basically an identity \verb|leftfn| to return whatever is stored there.
Corresponding \verb|rightfn|-s are obvious: return False/NIL when Right.

Again, this example can be generalized to an arbitrary number of action functions.
\href{https://wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding}{That’s what Mogensen–Scott encoding is about}.
Store the data, get action functions, run the matching one, get the result.

\section*{Maybe and Nothing (spoiler: there’s no Nothing)} \label{maybe}

July 2025: Originally, the post was coming to an abrupt end right after the previous section.
But I decided to also list my implementation of Maybe monad.
In part because it diverges from Marvin Borner’s one in a significant way.
\href{https://text.marvinborner.de/2024-11-18-00#maybe}{The way Marvin defines Maybe is}:

\begin{figure}[h!]\begin{verbatim}
Nothing   = nothing => just => nothing
Just = v => nothing => just => just(v)

isNothing = maybe => maybe(true)(_ => false)
isJust    = maybe => maybe(false)(_ => true)

getValue = just => just()(v => v)
\end{verbatim}\caption{Maybe, Just, and Nothing definitions}\end{figure}

Notice the order of arguments to Nothing/Just:
“nothing” clause goes first, “just” second.
Which makes as much sense as any other placement, actually:

\begin{figure}[h!]\begin{quote}
Personally I often choose the argument/tag order such that the de Bruijn indices make some intuitive sense to me
\end{quote}\caption{Marvin Borner on Nothing/Maybe parameter order}\end{figure}

But, for my implementation, I picked an opposite order, and here’s how it ended:

\begin{figure}[h!]\begin{verbatim}
alias nothing nil .

def maybe fn (x)
  fn (just none)
    just x .

def isnothing fn (mb)
  mb (fn _ false) true .

def isjust = complement isnothing .

def just fn (default mb)
  mb identity default .
\end{verbatim}\caption{Lamber implementation of Maybe}\end{figure}

So Nothing is no longer a random-looking function, it’s merely an alias for NIL.
Which is extending a 0=False=NIL=Nothing property I strive for so much.
And then, the order of arguments to \verb|isnothing| and \verb|just| is reversed too.
Which makes a lot of sense for \verb|just|, kind of saying “if maybe, then take identity, otherwise return default value.”
NIL/Nothing returns the second argument automatically, so no need for any special logic.
I like it when the tech solves its own problems.
As my implementation of Maybe did!

I guess that’s a lot of screen time taken for a small hack.
But at least you’ve gotten a taste of what writing Lambda Calculus monads sometimes involves:
parameter juggling!
Now to actually good material:

\section*{Directions to More Complex Structures} \label{directions}

I’m too stupid for more complex data types.
\href{https://text.marvinborner.de/2024-11-18-00}{Luckily, Marvin Borner isn’t}.
So go read his “Tiny, Untyped Monads” instead of a conclusion to this post.
It’s worth the read!
I’ll get to that too, and maybe I can steal some more of it into
\href{https://github.com/aartaka/lamber}{Lamber, my Lambda Calculus-compiling language}.

As an additional reference: the “bring computation to data” technique is used by Christian Queinnec in his
\href{https://christian.queinnec.org/WWW/LiSP.html}{Lisp in Small Pieces book},
in the part about emulating object-orientation when all you have are lambdas.
The solution he suggests is making a constructor lambda closing over initial arguments.
And then passing in a symbol matching respective “field” to fetch/modify it.
It can be generalized by passing in a function instead of symbol, like most structures in this post do!


\par\noindent\rule{\textwidth}{0.4pt}
\href{https://creativecommons.org/licenses/by/4.0}{CC-BY 4.0} 2022-2026 by Artyom Bologov (aartaka,)
\href{https://codeberg.org/aartaka/pages/commit/a91befa}{with one commit remixing Claude-generated code}.
Any and all opinions listed here are my own and not representative of my employers; future, past and present.
\end{document}
