×

When is a function a fold or an unfold? (English) Zbl 1260.68096

Corradini, Andrea (ed.) et al., CMCS 2001. Proceedings of the 4th workshop on coalgebraic methods in computer science, Genova, Italy, April 6–7, 2001. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 44, No. 1, 146-160 (2001).
Summary: We give a necessary and sufficient condition for when a set-theoretic function can be written using the recursion operator \(\mathsf{fold}\), and a dual condition for the recursion operator \(\mathsf{unfold}\). The conditions are simple, practically useful, and generic in the underlying datatype.
For the entire collection see [Zbl 1260.68011].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68Q65 Abstract data types; algebraic specification

Software:

QuickCheck; Haskell
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bird, R.; de Moor, O., Algebra of Programming (1997), Prentice Hall · Zbl 0867.68042
[2] K. Claessen and J. Hughes. Quickcheck: A lightweight tool for random testing of Haskell programs. In Proc. 5th ACM SIGPLAN International Conference on Functional Programming; K. Claessen and J. Hughes. Quickcheck: A lightweight tool for random testing of Haskell programs. In Proc. 5th ACM SIGPLAN International Conference on Functional Programming
[3] Cole, M., Parallel programming with list homomorphisms, Parallel Processing Letters, 5, 2, 191-203 (1995)
[4] J. Gibbons. Calculating functional programs. In Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction; J. Gibbons. Calculating functional programs. In Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction · Zbl 1065.68034
[5] J. Gibbons and G. Hutton. Proof methods for structured corecursive programs. In Proc. 1st Scottish Functional Programming Workshop; J. Gibbons and G. Hutton. Proof methods for structured corecursive programs. In Proc. 1st Scottish Functional Programming Workshop · Zbl 1098.68028
[6] J. Gibbons and G. Jones. The under-appreciated unfold. In Proc. 3rd ACM SIGPLAN International Conference on Functional Programming; J. Gibbons and G. Jones. The under-appreciated unfold. In Proc. 3rd ACM SIGPLAN International Conference on Functional Programming · Zbl 1369.68099
[7] M. M. Fokkinga. Law and Order in Algorithmics; M. M. Fokkinga. Law and Order in Algorithmics
[8] Gorlatch, S., Extracting and implementing list homomorphisms in parallel program development, Science of Computer Programming, 33, 1-27 (1999) · Zbl 0942.68027
[9] Z. Hu, H. Iwasaki and M. Takeichi. Deriving structural hylomorphisms from recursive definitions. In Proc. 1st ACM SIGPLAN International Conference on Functional Programming; Z. Hu, H. Iwasaki and M. Takeichi. Deriving structural hylomorphisms from recursive definitions. In Proc. 1st ACM SIGPLAN International Conference on Functional Programming · Zbl 1345.68059
[10] G. Hutton. Fold and unfold for program semantics. In Proc. 3rd ACM SIGPLAN International Conference on Functional Programming; G. Hutton. Fold and unfold for program semantics. In Proc. 3rd ACM SIGPLAN International Conference on Functional Programming · Zbl 1369.68103
[11] Hutton, G., A tutorial on the universality and expressiveness of fold, Journal of Functional Programming, 9, 4, 355-372 (July 1999)
[12] B. Jacobs. Exercises in coalgebraic specification. In Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction; B. Jacobs. Exercises in coalgebraic specification. In Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction · Zbl 1065.68035
[13] (Jacobs, B.; Moss, L.; Reichel, H.; Rutten, J., Proc. of the First Workshop on Coalgebraic Methods in Computer Science, Volume 11 (1998), Elsevier Science B.V) · Zbl 0903.00067
[14] Jacobs, B.; Rutten, J., A tutorial on (co)algebras and (co)induction, Bulletin of the European Association for Theoretical Computer Science, 62, 222-259 (1997) · Zbl 0880.68070
[15] (Jacobs, B.; Rutten, J., Proc. of the Second Workshop on Coalgebraic Methods in Computer Science, Volume 19 (1999), Elsevier Science B.V)
[16] J. Launchbury and T. Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Proc. Conference on Functional Programming Languages and Computer Architecture; J. Launchbury and T. Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Proc. Conference on Functional Programming Languages and Computer Architecture
[17] S. Mac Lane. Categories for the Working Mathematician; S. Mac Lane. Categories for the Working Mathematician · Zbl 0232.18001
[18] Malcolm, G., Algebraic data types and program transformation, Science of Computer Programming, 14, 2-3, 255-280 (September 1990)
[19] Meertens, L., Paramorphisms, Formal Aspects of Computing, 4, 5, 413-424 (1992) · Zbl 0754.68086
[20] E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In J. Hughes, editor, Proc. Conference on Functional Programming and Computer Architecture; E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In J. Hughes, editor, Proc. Conference on Functional Programming and Computer Architecture
[21] A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. Conference on Functional Programming Languages and Computer Architecture; A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. Conference on Functional Programming Languages and Computer Architecture · Zbl 0939.68556
[22] V. Vene and T. Uustalu. Functional programming with apomorphisms (corecursion). Proceedings of the Estonian Academy of Sciences: Physics, Mathematics47; V. Vene and T. Uustalu. Functional programming with apomorphisms (corecursion). Proceedings of the Estonian Academy of Sciences: Physics, Mathematics47 · Zbl 0963.68028
[23] V. Vene. Categorical Programming with Inductive and Coinductive Types; V. Vene. Categorical Programming with Inductive and Coinductive Types · Zbl 0966.68516
[24] Wadler, P., Deforestation: Transforming programs to eliminate trees, Theoretical Computer Science, 73, 231-248 (1990) · Zbl 0701.68013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.