[Haskell-cafe] Zipper with two focii for concurrent fun

[Yaakov M. Nemoy]

Ah, many thanks. this looks about right. I'll go through it later
today and see if i have any questions about it.

-Yaakov

On Mon, Jan 17, 2011 at 06:22:34PM +1030, John Lask wrote:
> 
> 
> see http://okmij.org/ftp/continuations/Continuations.html,
> "Zipper-based file server/OS", aka ZFS
> 
> where Oleg addresses concurrent operations on a shared data
> structure with multiple mutable cursors implemented via delimited
> continuations with varying isolation levels  ...
> 
> your issues are specifically addressed.
> 
> jvl
> 
> 
> 
> On 17/01/2011 5:20 PM, Yaakov M. Nemoy wrote:
> 
> >Hey List,
> >
> >So i've been pondering zippers in a concurrent situation, where more
> >than one thread has access to the same data structure, but with
> >different focal points. I've gotten a bit stuck though trying to
> >figure out how to do this using a zipper. The use case i'm thinking of
> >is slightly more complex, but using a basic example below should
> >suffice for an explanation.
> >
> >Say we have a list of characters in a text file which we're using in
> >the form of a zipper to show the current user's cursor position in the
> >text file. This means a data type such as:
> >
> >data ZipperList a = ZL [a] a [a]
> >
> >where the second element is the current position of the cursor. Now as
> >long as one user is editing the text file, we're fine.
> >
> >Now let's say we're working on a newfangled multipointer desktop where
> >two users have a keyboard and mouse each and want to work on the same
> >open file. We could have a list like this:
> >
> >data ZipperList a = ZL [a] a [a] a [a]
> >
> >which leaves us with a number of limitations. We're now limited to two
> >cursors rather than one, but once we start assuming multipointer, two
> >seems like a bigger limitation than just one cursor. Also, we can't
> >tell which user is at which focal point of the zipper easily.
> >
> >We could replace the user with:
> >
> >data User a = User String a
> >
> >data ZipperList a = ZL [a] (User a) [a] (User a) [a]
> >
> >but that gets into some ugly pattern matching. It still leaves us
> >stuck with a two user limit.
> >
> >Say we create a zipper that can contain other zippers. Such as:
> >
> >data ZipperList a = ZL (ZipperList a) a (ZipperList a) | L [a]
> >
> >which lets us include as many users as we want. Now this creates a
> >very different problem. Each cursor in our fictional text editor has a
> >totally different data structure. This is how any calculation at any
> >cursor knows where in the text file it is. If one user edits the
> >character at the cursor, every other zipper-like data structure has to
> >be updated for each other users. Thus a huge concurrency issue.
> >
> >This is where i hit a block. Am i totally crazy in thinking i can
> >solve this problem using a zipper? Or has someone thought about this
> >problem already and perhaps there's even a paper on it? Please advise.
> >
> >-Yaakov
> >
> >_______________________________________________
> >Haskell-Cafe mailing list
> >Haskell-Cafe at haskell.org
> >http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe