46
ECEASST
WUI (Web User Interface) library [Han06] has several similarities to the formlenses. In particu-
lar, WUI includes a combinator for lifting abijectionto WUIs, similar toour LFunctor Formlens
instance (restricted to bijections); however, Hanus did not consider Applicative or Monoidal
equational laws on WUIs, nor constructing them as functors over lenses.
Formlets were originally developed as part of Links [CLWY07]. Formlet libraries have since
been implemented for Haskell, F#, Scala, OCaml, Racket, and Javascript. Eidhof’s Haskell
library [Eid08] evolved first into digestive functors [dJ12], and most recently the reform pack-
age [SJ12]. The latter integrates with various other libraries, and extends formlets with better
support for validation and for separating layout from formlet structure. The F# WebSharper
library [BTG11] introduces flowlets, which combine formlets with functional reactive program-
ming [EH97] allowing forms to change dynamically at run-time.
Bidirectional transformations. Languages for describing bidirectional transformations have
been extensively studied in recent years; a recent Dagstuhl seminar report [HSST11] presents
acomprehensive survey. The original paper on lenses [FGM
+
07]describesworkondatabases
and programming languages; another more recent survey also discusses work from the software
engineeringliterature [CFH
+
09].TheXSugar[BMS08]languagedefinesbidirectionaltransfor-
mations between XML documents and strings. Similarly, the biXid [KH06] language specifies
essentially bijective conversions between pairs of XML documents. Transformations in both
XSugar and biXid are specified using pairs of intertwined grammars, which resemble our high-
level pattern syntax. The most closely related work we are aware of is by Rendel et al. [RO10].
They propose using functors over partial isomorphisms to describe invertible syntax descrip-
tions. Our design for formlenses is similar, but also supports using non-bijective bidirectional
transformations, while allowing for a convenient high-level syntax similar to that for formlets.
Applicative and monoidal functors. Applicative functorshavebeen usedextensivelyas anal-
ternative to monads for structuring effectful computation. Theywere used (implicitly) by Swier-
stra and Duponcheel [SD96] for parser combinators, and named and recognized as a lighter-
weight alternative to monads by McBride and Paterson [MP08]. The relationships among mon-
ads, arrows, and applicative functors were further elucidated by Lindley et al. [LWY11]. The
connection to monoidal functors was explored further by Paterson [Pat12], who also observes
that it is oftenmucheasier towork with monoidal functors. However, Paterson focuses attention
onfunctors on cartesian closed categories and Lens is not closed.
Functors oncategories other thanHask haveappearedinother contexts. Functors over isomor-
phismsareusedinthe fclabels library[VHEV12]. However, fclabels alsoprovidesanapplicative
functor interface, which can be used to produce intuitively incorrect bidirectional transforma-
tions. Similarly, functors over partial isomorphisms from Iso to Hask are essential in Rendel
and Ostermann’s invertible syntax descriptions [RO10]. Theyalsoemploy a variant of Monoidal
functors (which they call ProductFunctors). A natural question for further work is whether
Monoidal functors over partial isomorphisms suffice for invertible syntax descriptions, so that
one can easily compose parser or pretty-printer combinators with formlenses. To the best of our
knowledge, we are the first to use (monoidal) functors over lenses for programming.
13/ 21
43
Lenses for Web Data
5 Conclusion
Formlenses combine the features of formlets and lenses in a powerful abstraction that makes it
easy for programmers to present data on the web. Our work on formlenses is ongoing. In the
future, we plan to further develop the semantic properties of formlenses, investigate additional
combinatorsandgenericprogrammingtechniques for formlenses,and examine other formalisms
for Web interaction, such as flowlets [BTG11]. We also plan to investigate ways of interacting
withbrowsers that are not based onformssuchas JavaScript. Finally, we planto explore ways of
leveraging the semantic properties of formlenses to obtain efficient mechanisms for maintaining
the HTML even as the underlying data changes.
Acknowledgements: We wish to thankArjun Guha, Ross Tate, Philip Wadler, Daniel Wagner,
the Cornell Database Group, and the BX ’13 reviewers for helpful comments.
Bibliography
[Bie95]
G. M. Bierman. What is a Categorical Model of Intuitionistic Linear Logic? In
TLCA. Pp. 78–93. 1995.
[BMS08] C. Brabrand, A. Møller, M. I. Schwartzbach. Dual Syntax for XML Languages.
Information Systems 33(4–5):385–406, 2008. Short version in DBPL ’05.
[BTG11] J. Bjornson, A. Tayanovskyy, A. Granicz. Composing Reactive GUIs in F# Using
WebSharper. In IFL. LNCS 6647, pp. 203–216. Springer, 2011.
[CFH
+
09] K. Czarnecki, J. N. Foster, Z. Hu, R. L¨ammel, A. Sch¨urr, J. F. Terwilliger. Bidi-
rectional Transformations: A Cross-Discipline Perspective. GRACE Meeting notes,
State of the Art, and Outlook. In ICMT. Pp. 260–283. June 2009.
[CLWY07] E. Cooper, S. Lindley, P. Wadler,J. Yallop.Links: WebProgrammingWithout Tiers.
In FMCO. Pp. 266–296. 2007.
[CLWY08] E. Cooper, S. Lindley, P. Wadler, J. Yallop. The Essence of Form Abstraction. In
APLAS. Pp. 205–220. Springer, 2008.
[EH97]
C. Elliott, P. Hudak. Functional Reactive Animation. In ICFP. Pp. 263–273. 1997.
[Eid08]
C. Eidhof. Formlets in Haskell. 2008. Available at http://blog.tupil.com/
formlets-in-haskell.
[FGM
+
07] J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, A. Schmitt. Combina-
tors for bidirectional tree transformations: A linguistic approach to the view-update
problem. ACM Trans. Program. Lang. Syst. 29(3), May 2007.
[FPP08]
J. N. Foster, A. Pilkiewcz, B. C. Pierce. Quotient Lenses. In ICFP. Pp. 383–395.
Sept. 2008.
14 / 21
49
ECEASST
[Han06]
M. Hanus. Type-oriented construction of web user interfaces. In PPDP. Pp. 27–38.
2006.
[Hap12]
The Happstackweb server. 2012. Available fromhttp://happstack.com .
[HSST11] Z. Hu, A. Sch¨urr, P. Stevens, J. Terwilliger. Bidirectional Transformation “bx”.
Dagstuhl Reports 1(1):42–67, 2011. Available at t http://drops.dagstuhl.de/opus/
volltexte/2011/3144.
[dJ12]
J. V. der Jeugt. The digestive-functors package. 2012.
http://hackage.haskell.org/package/digestive-functors.
[KH06]
S. Kawanaka, H. Hosoya. biXid: a bidirectional transformation language for XML.
In ICFP. Pp. 201–214. Sept. 2006.
[KW12]
E. Kmett, D. Wagner. category-extras metapackageversion1.0.2. 2012. Available at
http://hackage.haskell.org/package/category-extras.
[LWY11] S. Lindley, P. Wadler, J. Yallop. Idioms are Oblivious, Arrows are Meticulous,
Monads are Promiscuous. Electron. Notes Theor. Comput. Sci. 229(5):97–117, Mar.
2011.
[Mac98]
S. MacLane. Categories for the working mathematician (second edition). Springer-
Verlag, 1998.
[Mai07]
G. Mainland. Why it’s nice to be quoted: Quasiquoting for Haskell. In Haskell.
Pp. 73–82. 2007.
[MP08]
C. McBride, R. Paterson. Applicative Programming with Effects. Journal of Func-
tional Programming 18(1):1–13, Jan. 2008.
[Pat12]
R. Paterson. ConstructingApplicative Functors. In MPC. LNCS 7342, pp. 300–323.
Springer, 2012.
[RO10]
T. Rendel, K. Ostermann. Invertible Syntax Descriptions: Unifying Parsing and
Pretty Printing. InHaskell. Pp. 1–12. 2010.
[SD96]
S. D. Swierstra, L. Duponcheel. Deterministic, Error-Correcting Combinator
Parsers. In Second International School on Advanced Functional Programming.
LNCS 1129, pp. 184–207. Springer, 1996.
[SJ02]
T. Sheard, S.P.Jones. Template metaprogrammingfor Haskell. InHaskell. Pp.1–16.
2002.
[SJ12]
J. Shaw, J. V. der Jeugt. The reform package. 2012. Available athttp://hackage.
haskell.org/package/reform-0.1.1.
[VHEV12] S. Visser, E. Hesselink, C. Eidhof, S. Visscher. The fclabels package, version 1.1.3.
May2012. Available athttp://hackage.haskell.org/package/fclabels.
15/ 21
5
Lenses for Web Data
[Vis11]
S. Visscher. data-category package version 0.4.1. 2011. Available athttp://hackage.
haskell.org/package/data-category.
16 / 21
51
ECEASST
A Monoidal categories and functors
The keyto our approach is touse monoidal rather thanapplicative functors to define formlenses.
This section reviews the (mostly standard) definitions for categories and monoidal functors.
Categories. A category is a collection of objects and arrows such that every object has an
identity arrow and arrows compose associatively.
class Category cwhere
id ::c xx
()::c yz ! c xy ! cx z
Haskell functions, bijections, and lenses each forma category.
instance Category (!) where
id = lx! x
fg = lx! f (g x)
instance Category Bij where
id = Bij id id
fg = Bij (fwd f fwdg) (bwd gbwd f)
instance Category Lens where
id = Lens id(const$id)
lm= Lens (get lget m)
(lac ! put m a(put l (get m a) c))
An isomorphism in a category c is an arrow f ::c a b with an “inverse” g:: c b a satisfying
fg=id =gf. Inacomputational setting, it is convenient torepresent isomorphisms explicitly.
dataIsoc a b= Iso ffwdI ::ca b;bwdI ::c bag
Isomorphisms are expected to satisfy the following condition:
fwdI isobwdI iso= id= bwdI isofwdI iso
Note that Bij is just Iso(!). However, we will keep the notation separate to avoidconfusion.
Monoidal categories. A monoidal category is a category with additional structure, namely a
unit and product on objects in the category. For simplicity, we will use the following definition
of monoidal categories, which is specialized to Haskell’s unit () and pairing types (;) and also
includes a pairing operation on c-arrows ( ) as well as c-isomorphisms relating unit and
pairing:
class Category c) MonoidalCategory cwhere
() ::c a
1
b
1
!ca
2
b
2
!c (a
1
;a
2
)(b
1
;b
2
)
munitl ::Isoc (();a) a
17/ 21
49
Lenses for Web Data
munitr ::Isoc (a;()) a
massoc::Isoc (a;(b;d)) ((a;b);d)
Monoidal categories are expected to satisfy a number of additional laws, which essentially state
that () is a unit with respect to (;) and “all diagrams involving the above operations com-
mute” [Mac98]. We will also omit discussion of the relevant laws of monoidal categories; the
standard laws hold for all of the monoidal categories we will consider in this paper.
Haskell types and functions form a monoidal category (!), with the followingoperations:
instance MonoidalCategory (!) where
fg = l(a;b) ! (f a;gb)
munitl = Iso (l(();a) ! a) (la ! (();a))
munitr = Iso (l(a;()) ! a) (la ! (a;()))
massoc= Iso (l(a;(b;d))! ((a;b);d))
(l((a;b);d)! (a;(b;d)))
In fact, any category with finite products is monoidal, but there are many monoidal categories
whosemonoidal product doesnot forma full Cartesianproduct. This is the case,forexample, for
bijections, since the fst and snd mappings arenot bijections; models of linear typetheory [Bie95]
provide more examples.
Two examples of monoidal categories that are relevant for our purposes are Bij and Lens. For
Bij, wefirst showhowto lift isomorphisms onHask toBij (thereis some redundancy here, which
we tolerate for the sake of uniformity):
iso2bij
:: Iso(!)a b! IsoBij a b
iso2bij (Isoto fro) =Iso(Bij to fro) (Bij froto)
instance MonoidalCategory Bij where
fg = Bij (l(a;b) ! (fwd f a;fwd g b))
(l(fa;gb)! (bwd f fa;bwd ggb))
munitl = iso2bij munitl
munitr = iso2bij munitr
massoc= iso2bij massoc
For Lens, we first lift the coercion bij2lens from bijections to lenses to act on isomorphisms:
iso2lens
:: IsoBij ab !IsoLens a b
iso2lens (Isoto fro) =Iso(bij2lensto) (bij2lens fro)
instance MonoidalCategory Lens where
l
1
l
2
=l
1
L
l
2
munitl = iso2lens munitl
munitr = iso2lens munitr
massoc= iso2lens massoc
18 / 21
63
ECEASST
Dual categories. Every category has a dual, obtained by reversing arrows:
newtype c
op
ab =CofunCo::c b ag
instance Category c) Category c
op
where
id
=Co id
(Cof)(Co g) = Co (gf)
The dual of any monoidal categoryis also monoidal:
iso2dual
:: Iso c ab !Isoc
op
ab
iso2dual (Iso tofro) = Iso (Co fro) (Co to)
instance MonoidalCategory c ) MonoidalCategory c
op
where
(Col
1
)(Co l
2
)=Co (l
1
l
2
)
munitl
=iso2dual munitl
munitr
=iso2dual munitr
massoc
=iso2dual massoc
Inparticular, Lens
op
is monoidal. This fact will be useful later sinceFormlensa isa contravariant
functor from Lens to Hask.
Functors. The built-in Haskell Functor type class models functors from Hask to Hask. For
our purposes, we will need to generalize its definition slightly
2
to consider functors from other
categories (suchas Bij and Lens) toHask. Accordingly, we introduce the following type classes:
class Category c) GFunctor c f where
gmap::ca b! f a ! f b
Again, since we are interested only in Hask-valued functors rather than defining a type class
for functors between arbitrary categories, we define a specific type class for functors from an
arbitrary categoryc to Hask.
Monoidal functors. Next, we consider monoidal functors:
class Monoidal f where
unit::f ()
(?) ::f a! f b ! f (a;b)
Note that we do not explicitly identify the domain of f in the type class Monoidal f; this is not
necessary(and leads totypecheckingcomplications due tothe unconstrained type variable) since
the signature of the operations of a monoidal functor depends only on the codomain category
2
Others have proposed much more general libraries for categoricalconcepts in Haskell [KW12,Vis11]; we believe
our approach could beframed using such alibrary, butprefer to keep the focus on the needed concepts to retain ac-
cessibilityto readers notalready familiarwiththeselibraries. Thisisalso an appropriateplacetomentionthatcorrect
useof categoricalconcepts in Haskell requiressomeadditionalside-conditionssuch as avoidanceof nontermination;
wetreatthis issue informally.
19/ 21
Documents you may be interested
Documents you may be interested