[FrontPage] [TitleIndex] [WordIndex

In response to continuing questions about stacks, queues, and problem set 1....

In a purely functional programming language(*), evolution of a structure is supported by creating a new structure, almost like the old one but with the desired variation, and using this new structure in place of the old one. This means that you'd use, e.g., (push elt stack) in place of stack. With a LIFO structure, there is only one thing to replace -- the stack-top -- so it makes a reasonable approach. With a FIFO structure, you need to hold on to both ends of the queue simulaneously. Replacing the queue start with an updated version might leave someone holding the end of the *old* queue structure and vice versa. There are a few ways around this. The easiest one is mutation/assignment: Don't change from an old thing to a new-and-similar thing; actually change/modify/mutate the thing itself. Then the old handles you have refer to a thing that is itself slightly different.

Again, it IS possible to implement a queue in scheme and it is even possible to implement a queue in a purely functional style. It just isn't as straightforward as implementing a stack (for the reasons described above).

(*) Note: In reality scheme is not purely functional. We have been mostly ignoring the non-functional parts of scheme, because my intention in introducing scheme was to show you functional programming, *not* to make you good scheme programmers. Good scheme programmers use the non-functional parts of the language (judiciously).

2013-07-17 10:43