Balancing trees

Have tree. Will use zipper to mutate. Much rejoicing. Only, when you have a binary search tree, you’d like to have a balanced tree so you get the O(lg n) search rather than a list masquerading as a tree (so all nodes only have left or right children), which would give you O(n) search. What…

Using the syntax tree in Go

The Go programming language provides an abstract syntax tree, parser and pretty printer as libraries written in Go. This enables you to mangle your Go code by writing code in Go – this isn’t quite lisp macros but it is a nice facility. Here is some example code that I will transform by manipulating the…

Direct implementation of shift/reset in Smalltalk

My work on zippers led me to a very strange thought, which I’ve constructed from Oleg Kiselyov‘s and Chung-Chieh Shan‘s papers: “a zipper is a suspended walk is a delimited continuation”. That was too intriguing to let go, so I started reading. That in turn led me to the “control operators”, things that let us…