User loginNavigation |
Streaming Representation-Changers
Jeremy Gibbons (2004). Streaming Representation-Changers. To appear in Mathematics of Program Construction, July 2004.
Unfolds generate data structures, and folds consume them. A hylomorphism is a fold after an unfold, generating then consuming a virtual data structure. A metamorphism is the opposite composition, an unfold after a fold; typically, it will convert from one data representation to another. In general, metamorphisms are less interesting than hylomorphisms: there is no automatic fusion to deforest the intermediate virtual data structure. However, under certain conditions fusion is possible: some of the work of the unfold can be done before all of the work of the fold is complete. This permits streaming metamorphisms, and among other things allows conversion of infinite data representations. We present the theory of metamorphisms and outline some examples. More origami work from Gibbons. This paper is related to several previous papers by Gibbons that were mentioned here (e.g., spigot pi, arithmetic coding), and it could be said that it summarizes the main results. I don't think this paper was linked to directly, so here goes. |
Browse archives
Active forum topics |
Recent comments
12 weeks 1 day ago
12 weeks 1 day ago
12 weeks 1 day ago
34 weeks 2 days ago
38 weeks 4 days ago
40 weeks 2 days ago
40 weeks 2 days ago
42 weeks 6 days ago
47 weeks 4 days ago
47 weeks 4 days ago