## Sunday, January 12, 2020

### Just for fun, transformations on lists

The mathematician in me likes to think about what happens to data and programs when you apply certain transformations to them. Here's a simple example. Imagine the function `swap` that simply makes a new cons cell by swapping the `car` and `cdr` of an existing cons cell:
```(define (swap cell) (cons (cdr cell) (car cell)))

> (swap '(1 . 2))
(2 . 1)

> (swap (swap '(1 . 2)))
(1 . 2)
```
As we'd expect, two swaps are equivalent to no swaps at all. Indeed any even number of swaps are equivalent. Any odd number of swaps is equivalent to one swap.

What if we call `swap` on a list?
```> (swap '(1 2 3))
((2 3) . 1)```
That's odd looking. But swapping again returns it to normal
```> (swap (swap '(1 2 3)))
(1 2 3)```

But `swap` only swaps the top-level cell. Let's define `deep-swap` that descends into the `car` and `cdr` if possible:
```(define (deep-swap cell)
(cons (if (pair? (cdr cell)) (deep-swap (cdr cell)) (cdr cell))
(if (pair? (car cell)) (deep-swap (car cell)) (car cell))))

> (deep-swap '((1 . 2) . (3 . 4)))
((4 . 3) 2 . 1)```
Wait, what? Oh, the list printer is just interpreting the second cons cell as a part of a top-level list. We can see this by trying this:
```> '((4 . 3) . (2 . 1))
((4 . 3) 2 . 1)```
So we just have to be aware of list printer eliding the dots for us.

What if we call `deep-swap` on a list?
```> (deep-swap '(1 2 3 4))
((((() . 4) . 3) . 2) . 1)```
Fortunately, `deep-swap`, like `swap`, undoes itself.
```> (deep-swap (deep-swap '(1 2 3 4)))
(1 2 3 4)```
It's easy to see that `swap` and `deep-swap` should commute.
```> (equal? (swap (deep-swap '((a . b) . (c . d))))
(deep-swap (swap '((a . b) . (c . d)))))
#t```
Alternatively, define `compose`
```;; Simple composition of two functions
(define (compose2 outer inner)
(lambda (x) (outer (inner x))))

;; Composition of arbitrary number of functions
(define (compose f . fs)
(if (null? fs)
f
(compose2 f (apply compose fs))))

> (equal? ((compose swap deep-swap) '((a . b) . (c . d)))
((compose deep-swap swap) '((a . b) . (c . d))))
#t```
So you can just move all the swaps together and all the deep-swaps together, then remove pairs of each one.

`swap` and `deep-swap` don't have very complex behavior, so let's turn to lists. We can define `rotate-left` as follows:
```(define (rotate-left l) (append (cdr l) (list (car l))))

> (rotate-left '(1 2 3 4))
(2 3 4 1)

> (rotate-left (rotate-left '(1 2 3 4)))
(3 4 1 2)```
(This is horribly inefficient, so this is just for fun, not production code.) Now what happens when we combine `rotate-left` with `reverse`?
```> (reverse (rotate-left (reverse '(1 2 3 4))))
(4 1 2 3)

(define rotate-right (compose reverse rotate-left reverse))

> (rotate-right '(1 2 3 4))
(4 1 2 3)```
`rotate-left` becomes `rotate-right` when used “under” `reverse`. Of course `rotate-left` doesn't commute with `reverse`: `(reverse (reverse (rotate-left '(1 2 3 4))))` the `reverse`s cancel each other and we're left with a `rotate-left`.

We can define “deep” versions of `reverse`, `rotate-left`, and `rotate-right`:
```(define (deeply f)
(lambda (l)
(if (list? l)
(f (map (deeply f) l))
l)))

> ((deeply reverse) '((1 2 3) 4 5 (6 7 (8 9 10))))
(((10 9 8) 7 6) 5 4 (3 2 1))

> ((deeply rotate-left) '((1 2 3) 4 5 (6 7 (8 9 10))))
(4 5 (7 (9 10 8) 6) (2 3 1))

> ((deeply rotate-right) '((1 2 3) 4 5 (6 7 (8 9 10))))
(((10 8 9) 6 7) (3 1 2) 4 5)```
Naturally, a `(deeply rotate-left)` will undo a `(deeply rotate-right)`. You might suspect that the composition of `(deeply reverse)`, `(deeply rotate-left)`, and `(deeply reverse)` is equivalent to `(deeply rotate-right)`, and you'd be right (I suspected as much, too, but it didn't seem so obvious, so I checked).

Notice that the deeper list structure has 3 elements each, but the topmost list structure has 4 elements, so 3 deep rotations is equivalent to one shallow rotation in the opposite direction, or `(compose rotate-left (deeply rotate-left) (deeply rotate-left) (deeply rotate-left))` is an identity. In fact, the shallow `rotate-left` commutes freely with `(compose (deeply-rotate left) (deeply rotate-left) (deeply rotate-left))`
```;; These are all equivalent identities
(compose rotate-left (deeply rotate-left) (deeply rotate-left) (deeply rotate-left))
(compose (deeply rotate-left) rotate-left (deeply rotate-left) (deeply rotate-left))
(compose (deeply rotate-left) (deeply rotate-left) rotate-left (deeply rotate-left))
(compose (deeply rotate-left) (deeply rotate-left) (deeply rotate-left) rotate-left)```

Arbitrary application of these operators will scramble your list structure much like arbitrary rotations will scramble a Rubik's cube. The analogy is more than skin deep: group theory can be used to describe and analyze the combinatorics of both. Group theory tells us that operations of the form `F-1GF` are likely to be interesting. And indeed:
```> ((compose rotate-right reverse rotate-left) '((1 2 3) 4 5 (6 7 (8 9 10))))
(4 (1 2 3) (6 7 (8 9 10)) 5)

(define involute (compose rotate-right reverse rotate-left))```
swaps the outside elements with the inside ones. And if we `compose` a `rotate-left` with this, we find we've reversed only the last three elements in the list `((1 2 3) (6 7 (8 9 10)) 5 4)`.

Just using these operators, there seems to be no way to get to get to `'((1 2 3) 5 4 (6 7 (8 9 10)))` (at least I couldn't find one), so I defined another operator:
```(define (call-on-tail f)
(lambda (x)
(cons (car x) (f (cdr x)))))```
which leaves the head element alone while applying the transformation to the rest.
```> ((compose rotate-left reverse (call-on-tail rotate-right) involute)
'((1 2 3) 4 5 (6 7 (8 9 10))))
((1 2 3) 5 4 (6 7 (8 9 10)))```

These functions can move elements up and down the list structure:
```(define (leftmost c)
(if (pair? c)
(leftmost (car c))
c))

(define (replace-leftmost c new-value)
(if (pair? c)
(cons (replace-leftmost (car c) new-value) (cdr c))
new-value))

(define (rightmost c)
(if (pair? c)
(if (null? (cdr c))
(rightmost (car c))
(rightmost (cdr c)))
c))

(define (replace-rightmost c new-value)
(if (pair? c)
(if (null? (cdr c))
(cons (replace-rightmost (car c) new-value) (cdr c))
(cons (car c) (replace-rightmost (cdr c) new-value)))
new-value))

(define (swap-ends l)
(replace-leftmost (replace-rightmost l (leftmost l)) (rightmost l)))

> (swap-ends '((1 2 3) 4 5 (6 7 (8 9 10))))
((10 2 3) 4 5 (6 7 (8 9 1)))

> ((compose involute swap-ends involute) '((1 2 3) 4 5 (6 7 (8 9 10))))
((1 2 3) 5 4 (6 7 (8 9 10)))

> ((deeply swap-ends) '((1 2 3) 4 5 (6 7 (8 9 10))))
((6 2 1) 4 5 (8 7 (10 9 3)))

> ((compose (deeply swap-ends)
(deeply swap-ends)
(deeply swap-ends)
(deeply swap-ends)
(deeply swap-ends)) '((1 2 3) 4 5 (6 7 (8 9 10))))
((1 2 3) 4 5 (6 7 (8 9 10)))```

There's no real application for all this, except maybe to come up with some puzzles. It's just fun to noodle around with list transformations to see what you can come up with, and to practice your list manipulation skills. You really need a language with a REPL to play around like this. A parsimonious syntax like Lisp helps, too. It would have been a bit more difficult to fool around if I had to put the appropriate commas, curly braces, brackets, and semicolons in just right.

None of these operations work on circular lists, but you can imagine that rotations and reversals could work on fully circular lists, but I'm not sure how they'd make sense on lists with circular tails. It would be challenging to make them work, though. They also don't work on “dotted” lists — they throw an error when they run into the dotted item at the end of the list. But it is fairly easy to imagine how they might be made to work on a dotted list. It would be much less of a challenge to implement.

#### 1 comment:

John Cowan said...

IWBNI the printer had an option not to suppress dots and print full dotted-pair structures. Not generally useful, but I've wanted it a few times.