CONS is your friend

I was watching Guy Steele’s talk subtitled foldl and foldr Considered Slightly Harmful. He ends the talk with the words “Get rid of cons”. Well… I am not ready to ditch the cons yet.

Hang on to your seat belt Dorothy ’cause Kansas is going bye bye

From a mathematician’s point of view, a list of objects of type \(X\) is an element from the free monoid generated by the set of elements of \(X\) where the monoid structure (a unital associative binary operation) is given by concatenation. The key word here is associative. An associative binary operation satisfies the associativity law

\[ a\cdot(b\cdot c) = (a\cdot b)\cdot c \]

All of the binary operations you learn in primary school such as addition and multiplication of numbers, are associative. Even max and min operators viewed as binary operators are associative:

\[ \max(x,\max(y,z)) = \max(\max(x,y),z) \]

If we consider only the positive numbers, the max operator has a unit which is 0

\[ \max(x,0) = \max(0,x) = x \]

otherwise max does not have a unit.

Now, in lisp we represent lists using a data structure called a cons. A cons is a pair \((x,y)\) which admits two projection operators: one gives us the first component and the other giving the second. Historically, they are called car and cdr. I’ll use the same names.

List processing vs tree processing

Here is one thing any lisp programmer knows, or I should say, should know: cons is a non-associative and non-unital binary operator.

(cons nil (cons 0 1))

(NIL 0 . 1)

(cons (cons nil 0) 1)

((NIL . 0) . 1)

We mimic associativity of concatenation by using a convention, or a normal form. So, a list of integers \((1,2,3)\) has a normal form

(cons 1 (cons 2 (cons 3 nil)))

(1 2 3)

If cons were an associative operation we could have represented the same list with

(cons (cons 1 2) (cons 3 nil))

((1 . 2) 3)

(cons (cons nil 1) (cons 2 3))

((NIL . 1) 2 . 3)

(cons (cons 1 2) (cons nil 3))

((1 . 2) NIL . 3)

Now, an element of the free monoid on a set \(X\) is known as a list of object of type \(X\), but there is also an analogue of the same thing if the underlying binary operation is non-associative. That thing is called a binary tree whose leaves are labeled by elements of \(X\). For example

((1 . 2) . (3 . 4))

represents the binary tree

   *
  / \
 *   *
/ \ / \
1 2 3 4

The name of Lisp comes from list processing, but I think the more appropriate name would have been treep, “a tree processing language” because cons, the fundamental data structure of almost all lisps, is by its nature non-associative. So, if we use cons sequentially like all lisps do, not by necessity but by convention, that is car carries the value and cdr points to the rest of the list, we get essentially a sequential data structure.

Guy Steele makes a very good observation: the sequential nature of elements of free associative monoids is not suitable for parallel processing. For parallel code we need efficient non-associative data structures, and then he describes a new structure called a conc tree which he didn’t have to do. He already had it: cons!

An implementation of map-reduce in lisp

Now, I will implement the map-reduce that Steele describes in lisp for giggles but with a slight change:

(defun map-reduce (tree re ma sh seed)
   (cond ((null tree) seed)
         ((atom tree) (funcall ma tree seed))
         (t (funcall re (map-reduce (car tree) re ma sh (funcall sh seed))
                        (map-reduce (cdr tree) re ma sh (funcall sh seed))))))

MAP-REDUCE

Notice that there is a great opportunity in implementing the reduce part in a highly parallel fashion. Let me explain what the input parameters are

tree is the tree we are going to process
re is the combining function. After the tree is processed recursively the return values are going to be combined using this function.
ma is the mapping function. Notice the difference. In the original definition map accepts only one argument, and now it is two. This is because we might want a different mapping function depending on how deep an element is located in the tree.
sh is a shifting function. As we go deeper in the tree we might want to shift the seed value returned from the mapping function.
seed is a seed value to be returned if the mapping function encounters a nil element which is usually the unit element of the reducing function.

This is the same exact function that Steele wrote except for the sh function.

Some examples

Let me start by writing some auxiliary functions that I am going to need later.

(defun random-tree (n m)
   (cond ((< n 0) nil)
         ((zerop n) (random m))
         ((= n 1) (cons (random m) (random m)))
         ((zerop (random 2)) (cons (random m) (random-tree (1- n) m)))
         (t (cons (random-tree (1- n) m) (random m)))))

RANDOM-TREE

(defun id (x) x)

ID

(defun pr (n) (if (zerop n) (lambda (x y) x) (lambda (x y) y)))

PR

I am also going to need a random tree to test my functions on

(defvar my-tree (random-tree 6 25))

MY-TREE

my-tree

(22 12 (((11 . 3) . 5) . 4) . 16)

Here are implementations of two functions which return the leftmost and the rightmost elements in a tree.

(defun left-most (tree)
   (map-reduce tree (pr 0) (pr 0) #'id nil))

LEFT-MOST

(defun right-most (tree)
   (map-reduce tree (pr 1) (pr 0) #'id nil))

RIGHT-MOST

The average complexity of these functions are \(\mathcal{O}(\log(n))\). For the sequential cons lists, the left-most function is \(\mathcal{O}(1)\) and the right-most is \(\mathcal{O}(n)\). But for general binary trees both are \(\mathcal{O}(log(n))\).

Let me test these functions:

(cons (left-most my-tree) (right-most my-tree))

(22 . 16)

These are not very interesting. Let me try length. Well… I should not call it length. It should be called the number of leaves in a tree

(defun num-leaves (tree)
   (map-reduce tree #'+ (lambda (x n) 1) #'id 0))

NUM-LEAVES

(num-leaves my-tree)

7

How about returning the same tree but increasing each leaf by 1, or putting the results in a cons list?

(map-reduce my-tree #'cons (lambda (x n) (1+ x)) #'id nil)

(23 13 (((12 . 4) . 6) . 5) . 17)

(map-reduce my-tree #'append (lambda (x n) (list (1+ x))) #'id nil)

(23 13 12 4 6 5 17)

How about left/right reflecting a tree?

(map-reduce my-tree (lambda (x y) (cons y x)) (pr 0) #'id nil)

(((16 4 5 3 . 11) . 12) . 22)

How about adding all the leaves, or finding the maximum?

(map-reduce my-tree #'+ (pr 0) #'id nil)

73

(map-reduce my-tree #'max (pr 0) #'id nil)

22

How about filtering a tree?

(defun filter (tree pred)
   (map-reduce 
        tree 
        (lambda (x y) 
           (cond ((null x) y)
                 ((null y) x) 
                 (t (cons x y))))
        (lambda (x n) 
           (if (funcall pred x) 
              x 
              n)) 
        #'id 
        nil))

FILTER

(filter my-tree #'evenp)

(22 12 4 . 16)

(filter my-tree #'oddp)

((11 . 3) . 5)

Notice that in the examples above, I did not use the shift function because the mapping functions I used didn’t care how deep we were in the tree. Let us say I wanted to calculate the depth of our tree:

(defun depth (tree)
   (map-reduce tree #'max (pr 1) #'1+ 0))

DEPTH

(depth 0)

0

(depth (cons 0 0))

1

(depth (cons 0 (cons 0 0)))

2

(depth my-tree)

6

How about I wanted to add the leaves, but each leaf is multiplied by depth of the leaf before they are added together?

(map-reduce my-tree #'+ #'* #'1+ 0)

219

A final word