Saturday, May 29, 2010

Zip tease

The last posting reviewed Huet's original proposal for the Zipper. Before doing a technical deep dive on some of the consequences of that idea i thought i important to provide some context on how the idea has been developed. Since it was brought to light there have been two important variations rung which i discuss below.

Two kinds of genericity
It turns out that Huet's discovery can be made to work on a much wider class of structures than "just" trees. Intuitively speaking, if their type arguments are "zippable", then virtually all of the common functional data type constructors, including sequencing constructors like product, and branching constructors, like summation or "casing", result in "zippable" types. That is, there are procedures for deriving a notion of zipper capable of traversing and mutating the structure. Essentially, there are two strategies to achieve this genericity: one is based on structural genericity and the other on procedural genericity.

Genericity of structure

The former approach relies on being able to define a notion of context for any "reasonable" data structure. Not surprisingly, it turns out that we can give a good definition of "reasonable". What is surprising is that the resulting definition is amenable to an operation that perfectly mimics the notion of derivative from Newton's calculus. The operation is an operation on types. This allows us to give a type-level definition of the notion of location -- just as we did with trees, but now for any type.

We can use Scala's type notation to see where the new genericity has been added. The type of trees in the example is already polymorphic: Tree[A]. That's what having that type parameter
A means. The navigation trait is therefore also parametric in A. The navigation trait, however, is hardcoded in the container type, Tree[A]. When we add this second level of genericity, the navigation trait will have to take a second, higher-kinded type parameter for the container because it will work on any container within a range of reasonably defined containers.

The use case we have been considering -- navigating and mutating an in-memory representation of a tree -- is then extended to navigating and mutating an in-memory representation of an arbitrary data structure. Moreover, the code is purely functional -- with all of the attendant advantages of purely functional code we have been observing
since forevever. Obviously, in the context of the web, this particular use case is of considerable interest. Nearly, every web application is of this form: navigating a tree or graph of pages. Usually, that graph of pages is somehow homomorphic, i.e. an image of, the graph of some
underlying domain data structure, like the data structures of employee records in a payroll system, or the social graph of a social media application like Twitter. Many web applications, such as so-called content management systems, also support the mutation of the graph of
pages. So, having a method of generating this functionality from the types of the underlying data domain, be they web pages, or some other domain data type, is clearly pertinent to the most focused of application developers.

And yet, the notion of a derivative of data types is irresistibly intriguing. It's not simply that it has many other applications besides web navigation and update. That a calculational device that an Englishman discovered some 400+ years ago in his investigations for providing a mathematical framework for gravitation and other physical phenomena should be applicable to structuring computer programs is as surprising as it is elegant and that makes it cool.

Genericity of control

The latter approach to generically constructing zippers is just as rich in terms of the world of ideas it opens up as it is in the imminent practicality of its immediate applications. The key insight is to abstract on control, rather than on form. Not surprisingly, then the central tool is the (delimited) continuation. To be clear, in this approach, originally developed by Oleg Kiselyov, navigation is reifed as a function and supplied as a parameter. In this sense, it is not automagically deriving mechanism for navigation, as does the structural approach. The semantics of mutation, on the other hand, is provided with a powerful generative mechanism. More specifically, a dial is provided for the visibility of mutation with respect to different threads of control. In other words, fine-grained constrol on the transactional semantics of mutating the data structure is provided. This is exceptionally powerful because, as we have mentioned in many previous posts, the transactional semantics is one of the principal places on which performance of a system -- especially a high-volume system -- hinges; but, by being based on a form of monad, namely delimited continuations, the abstraction gets the compiler involved. This has the effect of enlisting the compiler in maintaining discipline and sanity on transaction semantics -- which is vitally important when supplying a fine-grained control on something as performance-critical as the semantics and visibility of update.

28 comments:

Ben Hutchison said...

Hi Greg,

Im curious what zippers are "good for", in practical terms?

I appreciate that they allow constant time updates to large immutable tree-like data structures, that might otherwise require eg a logN copy of all nodes leading back to the root.

But the price of doing this at that the modified Zipper is a "subjective" view of the data from the focus, or viewpoint, of the modifying user. That seems to require doing work before sharing with, or passing to, other users/threads/downstream-consumers of the data, who may have, or want, another focus.

Luc Duponcheel said...

Hi Ben,

one of the things zippers are good for is replacing structural recursion with tail recursion (that can be optimized using standard techniques)

see:
http://www.cs.nott.ac.uk/~ctm/CJ.pdf

Luc

Ben Hutchison said...

Oh dear, I know I'm in too deep when Im redirected to a Conor McBride paper ;)

axel22 said...

Hi,

thanks for your blog post! Is there perhaps a more refined theory behind these data type derivatives? How does it perfectly mimic Newton's calculus?

Thanks,
Alex

samskivert said...

For a more formal presentation, you can once again consult CMB:

http://strictlypositive.org/diff.pdf

werwer said...

Is usually a multi-OS hard disk drive monitoring application. Its intention is to come across, test, diagnose and repair hard disk drive difficulties, display hard disk health, general performance degradations and failures. Hard Disk Sentinel Key offers entire textual description, strategies and displays/reports essentially the most thorough information and facts with regards to the HDD in the laptop or within an exterior enclosure (USB / e-SATA). Several different alerts and report options can be obtained to make sure highest security of your important data.

Sami said...

Hi, I am curious about your site because I have a similar one.
Is there anything you can do? If so, how can this be stopped?
Do you have any supplements or other products that you would like to recommend? I've been getting so much lately.
This is driving me crazy, so any help would be greatly appreciated.
microsoft office 2019 crack
adobe photoshop cs3 crack
driver booster pro crack
editplus crack

zia sir said...

nice post
Ummy video downloader Crack
HitmanPro.Alert Crack
Any Video Converter Ultimate Crack

Mahar Ismail said...

Hello there, I just discovered your blog on Google, and I like it.
is quite useful. I'll keep an eye out for brussels sprouts.
If you keep doing this in the future, I will be grateful. A large number of people will profit.
based on your writing Cheers!
vcard wizard pro crack
shaperbox crack
systemmachanic pro crack
vidiq vision for youtube crack

Unknown said...

I was searching over search engines and found your blog and it really helps thank you very much…
avast cleanup premium crack is different and better than previous editions. avast cleanup premium crack has a customizable and basic style. Further, its standards and demands are also improving. It is becoming popular all around the world. Hence, it is the best of its type. avast cleanup premium crack comes with the support of a multilanguage system. Hence, anyone from anyone can use it. Further, Avast Cleanup Premium Keygen works with a fast speed and easily competes with police viruses, spyware packages, malware packages, and various errors. avast cleanup premium crack can completely erase files you don’t need and tune up your system to make it run faster. It also disables nonworking background applications and further improves performance. Hence, it is the best of its type. avast cleanup premium crack

Sabir said...

And I appreciate your work, I'm a great blogger.
This article bothered me a lot.
I will bookmark your site and continue searching for new information.
hide all ip crack
wondershare pdfelement pro crack
microsoft office 2019 crack
auto tune pro crack

unknown said...

Please let me know if you’re looking for an author for your weblog.
You have some really good posts and I believe I would be a good asset.
If you ever want to take some of the load off, I’d love to
write some content for your blog in exchange for a link back to mine.
Please send me an email if interested. Thanks!
avira system speedup crack
microsoft office 2020 crack
ultraedit crack
system mechanic pro crack

Simple Boy said...

I am very impressed with your post because this post is very helpful to me and gives me new information. Thanks for sharing this post is a great article. God bless you
need for speed hot pursuit remastered crack
cuphead the delicious last course crack
mercs213 brandon game
final fantasy viii remastered crack
crab champions codex cd crack
tom clancys the division 2 crack
resident evil 7 biohazard gold edition plaza crack
age of empires iii complete collection multi6 elamigos crack

Unknown said...

I like your all post. You Have Done really good Work On This Site. Thank you For The Information You provided. It helps Me a lot.
it Is Very Informative Thanks For Sharing. I have also Paid This sharing. I am ImPressed For With your Post Because This post is very
is very beneficial for me and provides new knowledge to me. This is a cleverly
written article. Good work with the hard work you have done I appreciate your work thanks for sharing it. It Is very Wounder Full Post
I would like to thank you for the effort you put into writing this page.
I also hope that you will be able to check the same high-quality content later.
Really, your creative writing skills have inspired me to create my own blog now😉
red dead redemption crack
red dead redemption 2 pc game with crack
red dead redemption empress pc game with crack
red dead redemption 2 crack

Unknown said...

This is also a very good post which I really enjoyed reading. It is not every day that I have the possibility to see something like this.

NHL 21 Crack
filemaker pro crack
Styx: Shards of Darkness Crack
Ultimate Fishing Simulator Crack

softtware.net said...

I really like your site. Fantastic colors and themes.
Did you create this site yourself? Reply again because I hope to create my own
site itself and I would like to know where you have come to
it is here or where the item is named from.
Thank you!
avast premier license key
avg antivirus 2018
avg internet security license key

Naeem Shah said...

This is a large cup. On your website, keep up the good work.
Your blog has a lot of potential, and I look forward to exploring it further.
Thank you very much for your hard work. I'm going to go out and find it for myself.
It's something I'd suggest to others. They will, I am certain.
utilise this website
ocenaudio crack
final fantasy awakening se licensed mod apk
anytrans crack
google sketchup crack
hd tune pro crack license key
dvdfab player crack
driverfinder pro crack
format factory pro license key crack

Muhammad Sajjad Ali said...

You have a great site, but I wanted to know if you know.
Any community forum dedicated to these topics.
What was discussed in this article? I really want to be a part of it.
A society in which I can obtain information from others with knowledge and interest.
Let us know if you have any suggestions. I appreciate this!

lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack
lucion filecenter suite crack

gawgfwgsvgvgV said...


Oh my goodness! Impressive article dude! Thanks, However I am having troubles with your RSS. I don’t understand the reason why I am unable to join it. Is there anybody having the same RSS issues? Anyone that knows the answer will you kindly respond? Thanx!!
pillars of eternity deadfire the forgotten sanctum crack
greenify donate apk
imindq corporate crack
sony vegas pro crack
stellaris federations crack
guitar rig pro crack
luminar crack

ISPR said...

archeage crack
free mp3 cutter and editor crack
av voice changer crack
apowersoft video download capture crack
ms officce 365 crack
home designer pro crack
screenpresso pro crack
reaver pro crack

Crack said...

Hi! Your Blog Writing is Very Wonderfull And Amazing. Thanks For Sharing...
ant download manager pro crack
driver genius pro crack
sidify music converter
4k video downloader crack
navicat premium crack

Kamran Afzal said...

Your writing style is distinct from that of other authors I've encountered.
Thank you so much for taking the time to put this up, I'll be bookmarking it for future reference.
4ukey android unlocker crack
team viewer crack
hotspot shield crack
k7 total security crack

https://programsasvirtualespc.net/ said...

I Like Your post
Autodesk 3ds Max Crack
MAGIX ACID Pro Crack
CCleaner Professional Crack

CH ToQEER said...

I am very impressed with your post because this post is very beneficial for me and provide a new knowledge to me.
Thanks for sharing this post is an excellent article. Keep it up. I use the same blogging platform that you have and have.
it Is Very Informative Thanks For Sharing. I have also Paid This sharing. I am ImPressed For With your Post Because This post is very.
xilisoft video converter ultimate
super screen recorder
adobe pagemaker
vero machining strategist
vocal remover pro

indir Crack said...


I’ve been surfing on the web more than 3 hours today, yet I never found any stunning article like yours.
It’s alluringly worth it for me.
As I would see it if all web proprietors and bloggers made puzzling substance as you did.
the net will be in a general sense more beneficial than at whatever point in late memory.

xnviewmp crack
winsnap crack
whatsender pro crack
nch prism plus crack
cleanmymac x activation code crack

softwear said...

I guess I am the only one who came here to share my very own experience. Guess what!? I am using my laptop for almost the past 2 years, but I had no idea of solving some basic issues. I do not know how to Crack Softwares Free Download But thankfully, I recently visited a website named xxlcrack.net/
Hard Disk Sentinel Pro Crack
ProfiCAD Crack

CONTANT WRITTING said...
This comment has been removed by the author.
ProCrackPC said...

There is definately a great deal to know about this subject. I like all of the points you've made.
cc cleaner key