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

[John Lask]

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
>
>