[Paper] Functional Pearl: The Zipper

by syoyo

FUNCTIONAL PEARL: The Zipper
http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf

前回 の続きです. DFOMS(Data Flow Optimization Made Simple) では、Huet の Zipper と呼ばれるデータ構造(or 関数型的には functional pearl と呼んだほうがいいようだ)をベースにして、データフロー最適化のフレームワークが Haskell で構築されています.

Zipper ってなんじゃらほいと辿ってみると、データフロー最適化のような入力のグラフが操作により出力のグラフ変化する(immutable にできない)のは関数型言語では扱いが難しいのだが、Zipper と呼ばれる functional pearl を使うとそれが美しく実現できる、というシロモノらしい.

概念的には、いま弄っているデータ構造の部分を指すカーソル(or focus)という要素を追加することで Zipper というが出来上がるようです.より抽象的には Zipper は関数の微分でもあるみたい.

データフロー最適化を Haskell で行うために、まずは Zipper から詳しく学ばないとですね.

参考文献

Haskell/Zippers
http://en.wikibooks.org/wiki/Haskell/Zippers

Roll Your Own Window Manager: Tracking Focus with a Zipper
http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17

An Applicative Control-Flow Graph Based on Huet’s Zipper
http://www.cs.tufts.edu/~nr/pubs/zipcfg-abstract.html

Advertisements