Abstract
Functional transposition is a technique for converting relations into functions aimed at developing the relational algebra via the algebra of functions.
This paper attempts to develop a basis for generic transposition. Two instances of this construction are considered, one applicable to any relation and the other applicable to simple relations only.
Our illustration of the usefulness of the generic transpose takes advantage of the free theorem of a polymorphic function. We show how to derive laws of relational combinators as free theorems of their transposes. Finally, we relate the topic of functional transposition with the hashing technique for efficient data representation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, C., Backhouse, R., Hoogendijk, P., Voermans, E., van der Woude, J.: A relational theory of datatypes (December 1992)
Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories. John Wiley & Sons, Inc., Chichester (1990)
Backhouse, K., Backhouse, R.C.: Safety of abstract interpretations for free,via logical relations and Galois connections. In: Science of Computer Programming (2003) (accepted for publication)
Backhouse, R.C.: Regular algebra applied to language problems, Available from http://www.cs.nott.ac.uk/~rcb/papers/ , Extended version of Backhouse, R.: Fusion on languages. In: Sands, D. (ed.) ESOP 2001. LNCS, vol. 2028, pp. 107–121. Springer, Heidelberg (2001)
Backhouse, R.C., de Bruin, P., Hoogendijk, P., Malcolm, G., Voermans, T.S., van der Woude, J.: Polynomial relators. In: 2nd Int. Conf. Algebraic Methodology and Software Technology (AMAST 1991). LNCS, pp. 303–362. Springer, Heidelberg (1991)
Bird, R., deMoor, O.: Algebra of Programming. Series in Computer Science. Prentice-Hall International, Englewood Cliffs (1997), C.A.R. Hoare, series editor
Fitzgerald, J., Larsen, P.G.: Modelling Systems: Practical Tools and Techniques for Software Development, 1st edn. Cambridge University Press, Cambridge (1998)
Fokkinga, M.M.: Monadic maps and folds for arbitrary datatypes. Memoranda Informatica 94-28, University of Twente (June 1994)
Fokkinga, M.M., Meertens, L.: Adjunctions. Memoranda Informatica 94-31, University of Twente (June 1994)
Hoogendijk, P.: A Generic Theory of Data Types. PhD thesis, University of Eindhoven, The Netherlands (1997)
Hoogendijk, P.F., de Moor, O.: Container types categorically. Journal of Functional Programming 10(2), 191–225 (2000)
Horowitz, E., Sahni, S.: Fundamentals of Data Structures. Computer Software Engineering Series. Pitman (1978) E. Horowitz (ed.)
Peyton Jones, S.L.: Haskell 98 Language and Libraries. Cambridge University Press, Cambridge (2003), Also published as a Special Issue of the Journal of Functional Programming, 13(1) (January 2003)
Meng, S., Barbosa, L.S.: On refinement of generic state-based software components. In: Rattray, C., Maharaj, S., Shankland, C. (eds.) AMAST 2004. LNCS, vol. 3116, Springer, Heidelberg (2004) (to appear)
Oliveira, J.N.: Software Reification using the SETS Calculus. In: Denvir, T., Jones, C.B., Shaw, R.C. (eds.) Proc. of the BCS FACS 5th Refinement Workshop, Theory and Practice of Formal Software Development, London, UK, January 8-10, pp. 140–171. Springer, Heidelberg (1992) (Invited paper) ISBN 0387197524
Oliveira, J.N.: Hash Tables – A Case Study in ⊴ -calculation. Technical Report DI/INESC 94-12-1, INESC Group 2361, Braga (December 1994)
Oliveira, J.N.: ‘Fractal’ Types: an Attempt to Generalize Hash Table Calculation. In: Workshop on Generic Programming (WGP 1998), Marstrand, Sweden (June 1998)
Oliveira, J.N.: Hash tables as transposed data structures (2004), PURe Project technical report (in preparation)
Reynolds, J.C.: Types, abstraction and parametric polymorphism. Information Processing 83, 513–523 (1983)
Wadler, P.: Theorems for free! In: 4th International Symposium on Functional Programming Languages and Computer Architecture, London, September 1989, ACM, New York (1989)
Wirth, N.: Algorithms + Data Structures = Programs. Prentice-Hall, Englewood Cliffs (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fonseca de Oliveira, J.N., de Jesus Pereira Cunha Rodrigues, C. (2004). Transposing Relations: From Maybe Functions to Hash Tables. In: Kozen, D. (eds) Mathematics of Program Construction. MPC 2004. Lecture Notes in Computer Science, vol 3125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27764-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-27764-4_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22380-1
Online ISBN: 978-3-540-27764-4
eBook Packages: Springer Book Archive