[R] [newbie] stack operations, or functions with side effects (or both)

[Martin Morgan]

On 01/05/2012 09:18 AM, Tom Roche wrote:
>
> William Dunlap Wed, 4 Jan 2012 22:54:41 +0000
>> R functions [can] use their enclosing environments to save state.
>
> Aha!
>
>> makeStack<- function () {
>>    stack<- list()
>>    list(pop = function() {
>>      if (length(stack) == 0) { # get from an enclosing env.
>>        retval<- NULL
>>      } else {
>>        retval<- stack[[length(stack)]] # get from an enclosing env.
>>        stack<<- stack[-length(stack)] # assign in an enclosing env.
>>      }
>>      retval
>>    }, push = function(x) {
>>      stack[[length(stack) + 1]]<<- x # assign in an enclosing env.
>>      invisible(x)
>>    })
>> }
>
> Thanks, that's quite clear.

One point is that subsetting with "[" or extending with 
stack[[length(stack) + 1]] triggers a copy of stack. Better to pre-allocate

    stack <- vector("list", 100)
    curr <- 0L

and fill, e.g., push with

   curr <<- curr + 1L
   stack[[curr]] <<- x

plus bounds check and perhaps growth when necessary.

>
>> There are various encapsulations of this method in R. See, e.g.,
>> "reference classes" or the "proto" package.
>
> I can't see a reference-class implementation, but I did find

Probably Bill was pointing to ?ReferenceClasses. My attempt at 
implementing a stack as a reference class led, ironically, to copying 
issues anyway (below; maybe there's a different implementation?)

Efficient R programming usually involves operations on vectors, rather 
than the iteration implied by a stack. This might change your conclusion 
that a stack-based solution is appropriate.

Martin

Reference class implementation

.Stack <- setRefClass("Stack",
     fields=list(stack="list", curr="integer"),
     methods=list(
       initialize=function(stackSize=100L, ...) {
           callSuper(stack=vector("list", stackSize), curr=0L, ...)
       },
       push=function(val) {
           curr <<- curr + 1L
           if (curr > length(stack))
               ## double size; could be a bad choice
               length(stack) <<- 2L * length(stack)
           stack[[curr]] <<- val
           invisible(val)
       },
       pop=function() {
           if (curr == 0L)
               NULL                      # sentinel: empty
           else {
               val <- stack[[curr]]
               curr <<- curr - 1L
               val
           }
       },
       show=function() {
           cat("Class:", class(.self), "\n")
           cat("current size:", .self$curr, "\n")
           cat("maximum size:", length(.self$stack), "\n")
           if (.self$curr) {
               cat("head:\n")
               print(.self$stack[[1L]])
           }
       }))

and then

 > stack <- .Stack$new()
 > tracemem(stack$stack)
[1] "<0x1afc090>"
 > stack$push(10)
tracemem[0x1afc090 -> 0x9283a0]: <Anonymous>
tracemem[0x9283a0 -> 0xb96450]: <Anonymous> <Anonymous>
 > stack$push(10)
tracemem[0xb96450 -> 0x1b2a7d0]: <Anonymous> <Anonymous>
 > stack
Class: Stack
current size: 2
maximum size: 100
head:
[1] 10
 > while (!is.null(val <- stack$pop()))
+     cat("val:", val, "\n")
val: 10
val: 10

>
> https://stat.ethz.ch/pipermail/r-help/2010-March/230353.html (slightly edited)
>> [Subject:] [R] Stack type
>> [From:] Gabor Grothendieck ggrothendieck at gmail.com
>> [Date:] Tue Mar 2 14:33:43 CET 2010
>
>> library(proto)
>> Stack<- proto(new = function(.) proto(Stack,
>>    stack = NULL,
>>    push = function(., el) { .$stack<- c(list(el), .$stack) },
>>    pop = function(.) {
>        stopifnot(length(.$stack)>  0)
>>      out<- .$stack[[1]]
>>      .$stack[[1]]<- NULL
>>      out
>> }))
>
>> mystack<- Stack$new()
>> mystack$push( 1 )
>> mystack$push( letters )
>> mystack$pop()
>> mystack$pop()
>> mystack$pop() # gives an error
>
> Thanks again! Tom Roche<Tom_Roche at pobox.com>
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.


-- 
Computational Biology
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N. PO Box 19024 Seattle, WA 98109

Location: M1-B861
Telephone: 206 667-2793