yoko: Generic Programming with Disbanded Data Types
Based off of the paper "A Pattern for Almost Homomorphic Functions" at http://www.ittc.ku.edu/~nfrisby/frisby-wgp-2012.pdf, presented at the Workshop on Generic Programming 2012. Also, my dissertation http://www.ittc.ku.edu/~nfrisby/frisby-dissertation.pdf
yoko
views a nominal datatype as a band of constructors, each
a nominal type in its own right. Such datatypes can be disbanded via the
disband
function into an anonymous sum of nominal constructors, and vice
versa via the band
function. This library uses extensive type-level
programming to enrich its instant-generics
foundation with capabilities
derived from the constructor-centric perspective.
For example, consider the following nominal datatype.
data Beatles = John ... | Paul ... | George ... | Ringo ...
This type can of course be understood as a sum of the individual fields types.
data John = John ... data Paul = Paul ... data George = George ... data Ringo = Ringo ...
yoko
's conceptual foundations start there. In particular, this allows a
constructor, say John
, to be used independently of its original range type
and sibling constructors.
As a generic programming library, yoko
extends instant-generics
with
support for constructor-centric generic programming. The
Examples/LambdaLift/LambdaLift.hs
file distributed with the yoko
source
demonstrates defining a lambda-lifting conversion between the two types
ULC
, which has lambdas, and Prog
, which has top-level function
declarations instead.
data ULC = Lam Type ULC | Var Int | Let [Decl] ULC | App ULC ULC data Decl = Decl Type ULC data Prog = Prog [FunDec] TLF type FunDec = ([Type], [Type], Type, TLF) data TLF = Top Int [Occ] | Occ Occ | App TLF TLF data Occ = Par Int | Env Int
These types are defined in separate modules, since they have constructors
with the same name. Indeed, the fact that they having matching constructors
named App
is crucial for yoko
's automatic conversion from ULC
's App
to TLF
's App
. As written, the generic lambda-lifter would continue to
work for any new ULC
constructors (e.g. syntax for tuples or mutable
references) as long as constructors with the same names and analogous fields
were added to TLF
and the semantics of those constructors doesn't involve
binding. This default generic behavior of the lambda-lifter is specified in
about ten lines of user code.
The non-generic code is much more complicated. This is intentional: I wanted
to show that sometimes shoehorning an algorithm into the requisite type (ie
a -> m a'
) can be difficult and require subtleties like backwards state.
Existing generic libraries don't use constructor names to the degree that
yoko
does, and so cannot accomodate generic conversions as well.
[Skip to Readme]
Modules
[Index]
Downloads
- yoko-2.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.1, 0.2, 0.3, 0.3.0.1, 0.3.1, 0.3.1.1, 0.3.1.2, 0.3.1.3, 0.3.2, 0.3.2.1, 0.3.2.2, 0.9, 2.0 |
---|---|
Change log | CHANGES |
Dependencies | base (>=4 && <5), bifunctors, containers, invariant, kinds (>=0.0.1.5), mtl, records (>=0.1.1.6), semigroups, template-haskell, th-sccs, type-cereal (>=0.2), type-digits (>=0.2), type-equality, type-functions (>=0.2.0.3), type-ord (>=0.2), type-ord-spine-cereal (>=0.2), type-spine (>=0.2.0.20120924) [details] |
License | BSD-3-Clause |
Author | Nicolas Frisby <nicolas.frisby@gmail.com> |
Maintainer | Nicolas Frisby <nicolas.frisby@gmail.com> |
Category | Generics, Reflection |
Source repo | head: git clone git://github.com/nfrisby/yoko.git |
Uploaded | by NicolasFrisby at 2012-09-26T04:51:49Z |
Distributions | |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 8221 total (40 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs available [build log] Successful builds reported [all 1 reports] |