thank you @gfb
@shaffan1996 has joined the channel
Is there any imperative stack in Racket? e.g. pop
push
ps: I am writing non-recursive parser by a push-down machine. It is very imperative. I don’t think Racket list
is good data structure for this sort of thing. Thanks.
(define-simple-macro (push! x a-list) (set! a-list (cons x a-list)))
(define-simple-macro (pop! a-list) (begin0 (car a-list) (set! a-list (cdr a-list)))
(define my-stack '())
@chansey97 just out of curiosity, why do you feel a list is a bad data structure? I think consing onto the head of the list (e.g. push) is efficient, and using car
followed by cdr
is efficient for popping.
@badkins Because list is a functional data structure (imo) and I don’t like to embed a functional data structures in imperative code. This is like a code smell.
Yeah, but the list doesn’t know it’s a functional data structure, so it’s cool.
Single linked lists are often used in C.
(And Racket lists are single linked lists)
In fact, I am encapsulating my own stack, using list. Like following: (struct stack ([contents #:mutable]))
A mutable stack must be boxed.
Very strange, why the racket base library does not provide mutable stack? I have found a <https://docs.racket-lang.org/data/Imperative_Queues.html|Imperative Queues>, but no stack…
If you ever need a double linked list: https://github.com/soegaard/remacs/blob/master/dlist.rkt
@soegaard2 Is it a functional difference list? But what I want is imperative queue…
No, it’s an old school imperative double linked list.
I am already using Imperative Queues, fortunately it works very well. Racket data lib has a Growable Vectors, it can implement stack.
@badkins list
know itself is a functional data structure, because it is immutable.
Well, Racket does have a mutable cons cell, but I know what you mean. In some cases, an immutable data structure may have some disadvantages from an efficiency perspective, but given the sharing that’s possible when using lists, it may be an exception.
The reason there’s imperative queue but not imperative stack is that Racket list can readily be used as a stack.
Since Racket does not provide stack data structure:angry:, I have to write it by myself… https://github.com/chansey97/imperative-stack
The implementation is simple. In fact, I just copy-paste the example code from CLRS.
@sorawee list is not a mutable stack, a mutable stack must be boxed.
Imagine that if you were writing imperative code and used some mutable data structures, e.g. mutable struct, mutable queue, mutable vector, mutable tree and so on. Then you will hope mutable stack:smirk:.
First, Racket programmers tend to avoid mutable data structures and imperative code, so what you mentioned is not really needed
Second, if you are going to use one stack locally, this code also works:
#lang racket
(define (make-stack)
(define *stack* '())
(define (stack-push! e) (set! *stack* (cons e *stack*)))
(define (stack-pop!) (begin0 (first *stack*) (set! *stack* (rest *stack*))))
(define (stack-peek) (first *stack*))
(define (stack-empty?) (null? *stack*))
(values stack-push! stack-pop! stack-peek stack-empty?))
(define-values (push! pop! peek empty?) (make-stack))
For me, Racket is not only a practical programming language, but also an experimental platform for ideas.
There are many algorithms be not functional, such as: a non-recursive Top-Down parser which use a explicit stack. (we need mutable data)
Thanks. I understand what you mean. I originally did the same (except that I did not use multiple values).
But using a Racket’s list as a mutable stack is a bit weird (at least from the perspective of imperative style)
There’s mlist
which is a mutable singly-linked list and is slightly closer to what you want. But yeah it’s a bit weird.