Stacks

A stack is a data structure with just a couple of operations:

• push: push a new item onto the top of the stack
• pop: return the most recently pushed item, while removing it from the stack as a side-effect.

In a purely functional setting, we’d like to avoid side-effects. So in this document I’ll be following the convention of this implementation and use the following operations:

• push: return a new stack that is the result of pushing a new item onto a stack, while leaving the original stack unchanged
• peak: return the most recently pushed item on the stack, and leave the stack unchanged
• without_top: return a new stack that is the result of removing the most recently pushed item from the top of a stack, while leaving the original stack unchanged
• size: return the number of elements in a stack

Functions

I linked above to an implementation by Shawn Oneil that implements a persistent, functional stack by explicitly using environments. This implementation is basically the same, but by relying just on function calls, I’m hoping it will reveal a bit more of the way functions work.

Set up

First we set up the API for the stack data structure:

peak <- function(s) UseMethod("peak")
push <- function(s, new_item) UseMethod("push")
without_top <- function(s) UseMethod("without_top")
size <- function(s) UseMethod("size")

And it would probably be helpful to have a reasonable print method

print.stack <- function(s) {
    cat("A stack of size", size(s))
    if (size(s) > 0L) {
        cat("\nTop:\n") 
        str(peak(s))
    }
    invisible(s)
}

The base case

And now we implement a constructor for an empty stack. In the process, we end up implementing peak, without_top, and size.

# an empty stack should just be a function that returns the expected values
stack <- function() {
    f <- function(query) 
        switch(query, 
               peak = NULL,
               without_top = stop("Stack is already empty", call. = FALSE),
               size = 0L)
    structure(f, class = "stack")
}

peak.stack <- function(s) s("peak")
without_top.stack <- function(s) s("without_top")
size.stack <- function(s) s("size")

All that is left is to implement push.

Push

The push operation should return a new stack. Note that without_top on the newly created stack should just return the stack that was used in the call to push, so we really don’t need to do much. The one consideration to make here is to ensure that size(s) gets evaluated. Otherwise, every call to get the size of a stack would result in recursively calling for the size of every stack below it. :

push.stack <- function(s, new_item) {
    sz <- size(s) + 1L
    f <- function(query) 
        switch(query,
               peak = new_item,
               without_top = s,
               size = sz)
    structure(f, class = "stack")
}

That’s it! We have implemented a stack. There’s nothing here that’s super sophisticated, but the syntax feels a little magical. In Oneil’s implementation he uses environments to assign values, and here I rely on the fact that functions carry around their own environments. We still share data to achieve speed and efficiency, along with persistence.

Test it out

Let’s try it out:

# an empty stack
s <- stack()
size(s)

## [1] 0

t <- push(s, 1)
u <- push(t, 2)
peak(t)

## [1] 1

peak(u)

## [1] 2

# shared data
identical(without_top(u), t)

## [1] TRUE

# as opposed to:
t2 <- push(s, 1)
identical(t2, t)

## [1] FALSE

Convenience methods

Making an as.list method makes the structure lapply-able, among other things.

as.list.stack <- function(s) {
    # pre-allocate
    res <- vector("list", size(s))
    
    for (ind in seq_len(size(s))) {
        res[[ind]] <- peak(s)
        s <- without_top(s)
    }
    res
}