http://funcall.blogspot.com/2025/01/fold-and-monoids.html

Abstract Heresies

              Unorthodox opinions on computer science and
programming.

Saturday, January 4, 2025

fold-... and monoids

Suppose you satisfy these axioms:

  * you have a binary function * and a set that * is closed over (
    i.e. for all x, y in the set, x*y is in the set)
  * * is associative, ((a * b) * c) = (a * (b * c))
  * There is an an identity element I: a * I = I * a = a

Then * is called a semigroup or "monoid".

Monoids come from abstract algebra, but they are ubiquitous in
computer science. Here are some monoids: string-append over strings,
addition over integers, state transition over machine states, compose
over unary functions.

Alternatively, we can define a monoid as a binary function * that is
closed under folds fold-left or fold-right. That is, (fold-left #'* I
list-of-set-elements) is an element of the set. Folds abstract the
processing lists of set elements. The walk through the list, the end
test, and the accumulation of the result are all taken care of by the
implementation of fold. You get to focus on the monoid that acts on
each element.

Folds come in two flavors: fold-left and fold-right. fold-left has an
obvious iterative implementation, but the result is accumulated left
to right, which can come out backwards. fold-right has an obvious
recursive implementation which accumulates right to left, The result
comes out in the right order, but the recursion can cause problems if
the stack space is limited.

Here are some stupid tricks you can do with folds and monoids.

Create n-ary functions

If we curry the call to fold, we extend the binary function of two
arguments to an n-ary function of a list of arguments. For example,
n-ary addition is just a fold over binary addition. (fold-left #'+ 0
list-of-integers). Likewise, n-ary compose is just a fold over binary
compose.

Fold-... is self documenting

If I haven't used fold-left or fold-right in a while, I sometimes
forget which one computes what. But fold-left and fold-right can
document themselves: use a combining function that returns the list
(F a b) to indicate a call to F:

> (fold-left (lambda (a b) (list 'F a b)) '|...| '(c b a))
(F (F (F |...| C) B) A)

> (fold-right (lambda (a b) (list 'F a b)) '(a b c) '|...|)
(F A (F B (F C |...|)))

You can see the structure of the recursion by using list as the
combining function:

> (fold-left #'list '|...| '(c b a))
(((|...| C) B) A)

> (fold-right #'list '(a b c) '|...|)
(A (B (C |...|)))

fold-... works on groups

A group is a special case of a monoid where the combining function is
also invertible. fold-... can be used on a group as well. For example,
fold-left can be used on linear fractional transformations, which are
a group under function composition.

fold-... as an accumulator

The combining function in fold-left must be at least semi-closed: the
output type is the same as the type of the left input. (In
fold-right, the output type is the same as the type of the right
input.) This is so we can use the output of the prior call as the
input to the next call. In effect, we set up a feedback loop between
the output to one of the inputs of the binary function. This feedback
loop has a curious property: it behaves as if it has state. This is
happens even though both fold-... and the combining functions are pure
functions. The state appears to arise from the feedback loop.

We can use fold-... to accumulate a value. For fold-left, at each
iteration, the accumulator is passed as the first (left) argument to
the combining function while the next element of the list is the
second (right) argument. The combining function returns a new value
for the accumulator (it can return the old value if nothing is to be
accumulated on this step). The result of the fold-left is the final
value of the accumulator.

Note that because the accumulated value is passed as the first
argument, you cannot use cons as the combining function to accumulate
a list. This is unfortunate because it seems obvious to write
(fold-left #'cons '() ...) to accumulate a list, but that isn't how
it works. However, if you swap the arguments to cons you'll
accumulate a list:

(defun xcons (cdr car) (cons car cdr))

(defun revappend (elements base)
  (fold-left #'xcons base elements))

fold-... as a state machine

Although fold-left is commonly used to accumulate results, it is more
general than that. We can use fold-left as a driver for a state
machine. The second argument to fold-left is the initial state, and
the combining function is the state transition function. The list
argument provides a single input to the state machine on each state
transition.

For example, suppose you have a data structure that is a made out of
nested plists. You want to navigate down through the plists to reach
a final leaf value. We set up a state machine where the state is the
location in the nested plists and the state transition is navigation
to a deeper plist.

(defun getf* (nested-plists path)
  (fold-left #'getf nested-plists path))

Alternatively, we could drive a state machine by calling fold-left
with an initial state and list of state transtion functions:

(defun run-state-machine (initial-state transitions)
  (fold-left (lambda (state transition)
               (funcall transition state))
             initial-state
             transitions))

Visualizing fold-left

If we unroll the recursion in fold-left, and introduce a temp
variable to hold the intermediate result, we see the following:

(fold-left F init '(c b a))

temp - init
temp - F(temp, c)
temp - F(temp, b)
temp - F(temp, a)

I often find it easier to write the combining function in a fold-... by
visualizing a chain of combining functions wired together like this.

Generating pipelines

Now let's partially apply F to its right argument. We do this by
currying F and immediately supplying an argument:

(defun curry-left (f)
  (lambda (l)
    (lambda (r)
      (funcall f l r))))

(defun curry-right (f)
  (lambda (r)
    (lambda (l)
      (funcall f l r))))

(defun partially-apply-left (f l)
  (funcall (curry-left f) l))

(defun partially-apply-right (f r)
  (funcall (curry-right f) r))

We can partially apply the combining function to the elements in the
list. This gives us a list of one argument functions. In fact, for
each set element in the set associated with our monoid, we can
associate a one-argument function. We can draw from this set of
one-argument functions to create pipelines through function
composition. So our visualization

temp - init
temp - F(temp, c)
temp - F(temp, b)
temp - F(temp, a)

becomes

temp - init
temp - F[c](temp)
temp - F[b](temp)
temp - F[a](temp)

We can write this pipeline this way:

result - F[a] - F[b] - F[c] - init

or this way:

result - (compose F[a] F[b] F[c]) - init

We can pretend that the elements of the set associated with monoid
are pipeline stages. We can treat lists of set elements as though
they are pipelines.

Notice how we never write a loop. We don't have the typical list loop
boilerplate

(if (null list)
         ... base case ...
  (let ((element (car list))
        (tail (cdr list)))
    ... ad hoc per element code ...
    (iter tail)))

Instead, we have a function that processes one element at a time and
we "lift" that function up to process lists of elements.

Pipelines are easier to reason about than loops. fold-... converts
loops into pipelines.

It takes a little practice to use fold-... in the less obvious ways.
Once you get used to it, you'll see them everywhere. You can
eliminate many loops by replacing them with fold-....

Monoids vs. Monads

A monad is a monoid over a set of curried functions. You use a
variant of compose to combine the curried functions. Monads force
sequential processing because you set up a pipeline and the earlier
stages of the pipeline naturally must run first. That is why monads
are used in lazy languages to embed imperative subroutines.

Posted by Joe Marshall at 6:00 PM # #
Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest
Labels: fold, Lisp, monad, monoid

No comments:

Post a Comment

Newer Post Older Post Home
Subscribe to: Post Comments (Atom)

Blog Archive

  * V  2025 (11)
      + V  January (11)
          o Substitution vs. State Transition
          o GitHub glitch bites hard (and update)
          o fold-... and monoids
          o A Newbie Is Exposed to Common Lisp
          o Dvorak and Lisp
          o REBOL 1.0 Was Slow
          o GitHub Copilot Revisited
          o Scheme Interpreter: Conclusions
          o Calling Conventions in the Interpreter
          o More Inlining
          o Inlinig Primitive Function Calls and Argument Eval...

  * >  2024 (45)
      + >  December (10)
      + >  November (1)
      + >  October (1)
      + >  July (3)
      + >  June (7)
      + >  May (12)
      + >  April (4)
      + >  March (3)
      + >  February (2)
      + >  January (2)

  * >  2023 (10)
      + >  November (1)
      + >  October (1)
      + >  September (1)
      + >  August (1)
      + >  July (2)
      + >  June (3)
      + >  May (1)

  * >  2022 (14)
      + >  October (2)
      + >  September (3)
      + >  August (1)
      + >  July (4)
      + >  March (1)
      + >  February (2)
      + >  January (1)

  * >  2021 (13)
      + >  December (1)
      + >  October (1)
      + >  August (3)
      + >  May (4)
      + >  April (3)
      + >  March (1)

  * >  2020 (22)
      + >  October (1)
      + >  February (6)
      + >  January (15)

  * >  2019 (5)
      + >  December (5)

  * >  2016 (4)
      + >  January (4)

  * >  2015 (8)
      + >  September (6)
      + >  August (2)

  * >  2014 (11)
      + >  September (4)
      + >  August (7)

  * >  2013 (24)
      + >  October (2)
      + >  September (3)
      + >  August (2)
      + >  July (12)
      + >  May (1)
      + >  April (2)
      + >  March (1)
      + >  January (1)

  * >  2012 (14)
      + >  August (1)
      + >  July (1)
      + >  June (1)
      + >  April (3)
      + >  March (3)
      + >  February (2)
      + >  January (3)

  * >  2011 (51)
      + >  November (4)
      + >  October (9)
      + >  September (4)
      + >  August (1)
      + >  April (5)
      + >  March (9)
      + >  February (10)
      + >  January (9)

  * >  2010 (57)
      + >  December (4)
      + >  October (1)
      + >  September (1)
      + >  August (8)
      + >  July (1)
      + >  June (8)
      + >  May (8)
      + >  April (18)
      + >  March (4)
      + >  February (3)
      + >  January (1)

  * >  2009 (114)
      + >  December (5)
      + >  November (2)
      + >  October (13)
      + >  September (10)
      + >  August (9)
      + >  July (19)
      + >  June (6)
      + >  May (7)
      + >  April (12)
      + >  March (21)
      + >  January (10)

  * >  2008 (62)
      + >  December (1)
      + >  November (2)
      + >  October (4)
      + >  September (7)
      + >  August (13)
      + >  July (11)
      + >  May (5)
      + >  April (7)
      + >  March (6)
      + >  February (5)
      + >  January (1)

  * >  2007 (61)
      + >  December (3)
      + >  November (4)
      + >  October (5)
      + >  September (8)
      + >  August (5)
      + >  July (8)
      + >  June (10)
      + >  May (5)
      + >  April (13)

  * >  2006 (1)
      + >  December (1)

 
 
Powered by Blogger.