[Haskell-cafe] Zipper with two focii for concurrent fun
Yaakov M. Nemoy
loupgaroublond at gmail.com
Mon Jan 17 07:50:11 CET 2011
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.
More information about the Haskell-Cafe