Building a data structure with nothing but functions

Henry Chen — Mon, 31 Dec 2018 08:00:00 +0000

A simple but far reaching consequence of being able to nest functions is that data can be stored in the enclosing scope - or closure - of the inner function. Consider the following function:

def make_node(value, next_node):
    return lambda func: func(value, next_node)

When make_node is called with two arguments, they are attached to the closure of the returned function. Subsequently, we can access the two arguments via

def value(node):
    return node(lambda value, next_node: value)

and

def next_node(node):
    return node(lambda value, next_node: next_node)

For example,

>>> node = make_node("head", "tail")
>>> value(node)
'head'
>>> next_node(node)
'tail'

With these functions in hand, it is easy to implement a stack as a linked list. We define the usual stack operations

def push(value, stack):
    return make_node(value, stack)

and

def pop(stack):
    return value(stack), next_node(stack)

The behavior is as expected:

>>> stack = None
>>> stack = push(1, stack)
>>> stack = push(2, stack)
>>> stack = push(3, stack)
>>> val, stack = pop(stack)
>>> val
3
>>> val, stack = pop(stack)
>>> val
2
>>> val, stack = pop(stack)
>>> val
1

It is remarkable that this stack does not use any built-in data structure such as an array, nor does it build the linked list by instantiating node objects. Rather, there is a chain of functions wherein each function’s closure contains a value and a reference to the next function.

This discussion was inspired by the classic Structure and Interpretation of Computer Programs. In particular, section 2.1 introduces the notion of using closures to build data structures.

Stackless Quicksort

Henry Chen — Thu, 08 Nov 2018 08:00:00 +0000

Quicksort is a famous example of a recursive algorithm. Here is a sub-optimal implementation:

def qsort(lst, start=0, end=None):
    if end is None:
        end = len(lst)
    if end - start < 2:
        return

    pivot_position = partition(lst, start, end)

    qsort(lst, start, pivot_position)
    qsort(lst, pivot_position + 1, end)

The partition function chooses a pivot value and places it at the correct position, with smaller values to its left and larger values to its right. It also returns the final position of the pivot value.

def partition(lst, start, end):
    pivot = lst[start]
    rest = lst[start + 1 : end]

    left = [item for item in rest if item <= pivot]
    right = [item for item in rest if item > pivot]

    lst[start:end] = left + [pivot] + right
    return start + len(left)

For brevity, we use list slicing instead of swaps, but the discussion does not depend on how the partitioning is done.

In the above implementation, observe that each recursive call stands alone, simply sorting a segment of the list. As this article points out, the recursive call stack serves merely to ensure that the list is divided into smaller segments until every item is a pivot or belongs to a segment of one item.

Because the order in which different parts of the list is sorted is immaterial, we don’t need recursion or even a stack for that matter. Here is an implementation of quicksort using a set to track which segments are still to be sorted:

def qsort_stackless(lst):
    not_sorted = {(0, len(lst))}

    while not_sorted:
        start, end = not_sorted.pop()
        pivot_position = partition(lst, start, end)
        if pivot_position - start > 0:
            not_sorted.add((start, pivot_position))
        if end - (pivot_position + 1) > 0:
            not_sorted.add((pivot_position + 1, end))

The set not_sorted contains start and end indices of segments which remain to be sorted. Note that the pop method returns an arbitrary element of a set, which becomes empty when no unsorted segments remain. The list is then sorted. Let’s check a test case:

>>> lst = [3, 2, 1, 4, 5]
>>> qsort_stackless(lst)
>>> lst[1, 2, 3, 4, 5]

DEV Community: Henry Chen

Building a data structure with nothing but functions

Stackless Quicksort