[Haskell-cafe] Red-Blue Stack

[Derek Elkins]

On Thu, 2008-09-25 at 00:11 -0400, Matthew Eastman wrote:
> Hey guys,
> 
> This is probably more of a question about functional programming than  
> it is about Haskell, but hopefully you can help me out. I'm new to  
> thinking about things in a functional way so I'm not sure what the  
> best way to do some things are.
> 
> I'm in a data structures course right now, and the assignments for the  
> course are done in Java. I figured it'd be fun to try and implement  
> them in Haskell as well.
> 
> The part of the assignment I'm working on is to implement a  
> RedBlueStack, a stack where you can push items in as either Red or  
> Blue. You can pop Red and Blue items individually, but the stack has  
> to keep track of the overall order of items.
> 
> i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red, Red,  
> Blue]
> 
> All push and pop operations on the stack have to be done in O(1) time.
> 
> It was easy to do in Java since you can just keep track of everything  
> with a few pointers, but it took a while to get the Haskell version  
> working. Maybe I'm just not used to the functional way of doing things.

Note that purely functional data structures are inherently persistent
(i.e. you can access old copies as well as new copies.)  This is a
significant extra constraint.  Your Java type is almost certainly
ephemeral, the opposite of persistent.  Rewriting your Java code to be
persistent while still maintaining the asymptotic complexities of the
relevant operations is non-trivial.  You can always achieve persistence
by (deep) copying, but copying is an O(n) operation at best.

Consider a simple example.  The requirements are a sequence of elements
with O(1) add and remove to beginning and end.  This is easy.  One
solution is a doubly-linked list with head and tail pointers.  Now if I
add the requirement that it is persistent, i.e. if I have list1 =
[a,b,c,d] and I make list2 = list1.RemoveLast(), list1 should still be
[a,b,c,d] and list2 should be [a,b,c].  Now the problem is quite a bit
more difficult.  Try it.  Also try to prove (informally or formally)
that the asymptotic complexities hold and that the persistence guarantee
holds.

Okasaki's thesis and/or book, "Purely Functional Data Structures" goes
into the differences and how to produce data structures with good
complexity characteristics in a purely functional language.  The
implementations described are rather different from the usual
implementations used for ephemeral data structures.  The real-time
deques described in the thesis are one solution to the above problem, in
this case a purely functional one.

In a nutshell, persistent data structures are inherently more difficult
to build than ephemeral ones*, which are what are usually described, and
in a purely functional language all data structures are persistent.

* Proof: If I have a persistent data structure I can make an ephemeral
one with the same asymptotic complexity behaviour by simply having a
mutable reference holding the persistent data structure.