|
[1]
|
Richard S. Bird and Sharon Curtis.
Finding celebrities: A lesson in functional programming.
Journal of Functional Programming, 16(1):13-20, 2006.
[ bib |
http ]
|
|
[2]
|
Richard S. Bird.
Improving saddleback search: A lesson in algorithm design.
In Tarmo Uustalu, editor, Mathematics of Program Construction,
volume 4014 of Lecture Notes in Computer Science, pages 82-89.
Springer, 2006.
[ bib |
http ]
|
|
[3]
|
Richard S. Bird.
Loopless functional algorithms.
In Tarmo Uustalu, editor, Mathematics of Program Construction,
volume 4014 of Lecture Notes in Computer Science, pages 90-114.
Springer, 2006.
[ bib |
http ]
|
|
[4]
|
Richard S. Bird and Stefan Sadnicki.
On-line list labelling with minimum labels.
Information Processing Letters, 2006.
To appear.
[ bib ]
|
|
[5]
|
Richard S. Bird.
A program to play Sudoku.
Journal of Functional Programming, 16(5), 2006.
To appear.
[ bib |
http ]
|
|
[6]
|
Richard S. Bird and Shin-Cheng Mu.
Countdown: A case study in origami programming.
Journal of Functional Programming, 15(5):679-702, 2005.
[ bib |
http ]
|
|
[7]
|
Richard S. Bird.
Polymorphic string matching.
In Haskell Workshop, pages 110-115, New York, NY, USA, 2005.
ACM Press.
[ bib |
http ]
|
|
[8]
|
Shin-Cheng Mu and Richard S. Bird.
Theory and applications of inverting functions as folds.
Science of Computer Programming, 51(1-2):87-116, 2004.
[ bib |
http ]
|
|
[9]
|
Richard S. Bird.
On tiling a chessboard.
Journal of Functional Programming, 14(6):613-622, 2004.
[ bib |
http ]
|
|
[10]
|
Richard S. Bird and Shin-Cheng Mu.
Inverting the Burrows-Wheeler transform.
Journal of Functional Programming, 14(6):603-612, 2004.
Earlier version appeared at Haskell Workshop 2001.
[ bib |
.pdf |
http ]
|
|
[11]
|
Jeremy Gibbons, David Lester, and Richard Bird.
Enumerating the rationals.
Journal of Functional Programming, 16(3):281-292, 2004.
[ bib |
.pdf ]
|
|
[12]
|
Richard Bird and Jeremy Gibbons.
Arithmetic coding with folds and unfolds.
In Johan Jeuring and Simon Peyton Jones, editors, Advanced
Functional Programming 4, volume 2638 of Lecture Notes in Computer
Science, pages 1-26. Springer-Verlag, 2003.
[ bib |
.pdf ]
|
|
[13]
|
Shin-Cheng Mu and Richard S. Bird.
Rebuilding a tree from its traversals: A case study of program
inversion.
In Atsushi Ohori, editor, Asian Symposium on Programming
Languages and Systems, volume 2895 of Lecture Notes in Computer
Science, pages 265-282. Springer, 2003.
[ bib |
.pdf |
http ]
|
|
[14]
|
Richard Bird and Ralf Hinze.
Trouble shared is trouble halved.
In Haskell Workshop, pages 1-6, New York, NY, USA, 2003. ACM
Press.
[ bib |
http ]
|
|
[15]
|
Richard Bird, Jeremy Gibbons, and Shin Cheng Mu.
Algebraic methods for optimization problems.
In Roland Backhouse, Roy Crole, and Jeremy Gibbons, editors,
Algebraic and Coalgebraic Methods in the Mathematics of Program
Construction, volume 2297 of Lecture Notes in Computer Science, pages
281-307. Springer-Verlag, 2002.
[ bib |
.pdf ]
We argue for the benefits of relations over functions for
modelling programs, and even more so for modelling specifications. To
support this argument, we present an extended case study for a class
of optimization problems, deriving efficient functional programs from
concise relational specifications.
|
|
[16]
|
Shin-Cheng Mu and Richard S. Bird.
Inverting functions as folds.
In Eerke A. Boiten and Bernhard Möller, editors, Mathematics
of Program Construction, volume 2386 of Lecture Notes in Computer
Science, pages 209-232. Springer, 2002.
[ bib |
.pdf |
http ]
|
|
[17]
|
Shin-Cheng Mu and Richard Bird.
Functional quantum programming.
In Asian Workshop on Programming Languages and Systems, KAIST,
Dajeaon, Korea, December 2001.
[ bib |
.pdf ]
|
|
[18]
|
Richard S. Bird.
Unfolding pointer algorithms.
Journal of Functional Programming, 11(3):347-358, 2001.
[ bib |
http ]
|
|
[19]
|
Richard S. Bird.
Maximum marking problems.
Journal of Functional Programming, 11(4):411-424, 2001.
[ bib |
http ]
|
|
[20]
|
Shin-Cheng Mu and Richard Bird.
On building trees with minimum height, relationally.
In First Asian Workshop on Programming Languages and Systems,
2000.
[ bib |
.pdf ]
|
|
[21]
|
Richard Bird, Jeremy Gibbons, and Geraint Jones.
Program optimisation, naturally.
In J. W. Davies, A. W. Roscoe, and J. C. P. Woodcock, editors,
Millenial Perspectives in Computer Science. Palgrave, 2000.
[ bib |
.pdf |
.ps.gz ]
It is well-known that each polymorphic function satisfies a
certain equational law, called a naturality condition. Such
laws are part and parcel of the basic toolkit for improving the
efficiency of functional programs. More rarely, some polymorphic
functions also possess a higher-order naturality property. One
example is the operation unzip that takes lists of pairs to
pairs of lists. Surprisingly, this property can be invoked to improve
the asymptotic efficiency of some divide-and-conquer algorithms from
O(n log n) to O(n). The improved algorithms make use of
polymorphic recursion, and can be expressed neatly using nested
datatypes, so they also serve as evidence of the practical utility of
these two concepts.
|
|
[22]
|
Richard Bird and Ross Paterson.
Generalised folds for nested datatypes.
Formal Aspects of Computing, 11:200-222, 1999.
[ bib |
.pdf |
http ]
|
|
[23]
|
Richard S. Bird and Ross Paterson.
de Bruijn notation as a nested datatype.
Journal of Functional Programming, 9(1):77-91, 1999.
[ bib |
.pdf |
http ]
|
|
[24]
|
Richard S. Bird and Lambert Meertens.
Nested datatypes.
In Johan Jeuring, editor, LNCS 1422: Proceedings of Mathematics
of Program Construction, pages 52-67, Marstrand, Sweden, June 1998.
Springer-Verlag.
[ bib |
.pdf |
http ]
|
|
[25]
|
Richard S. Bird.
Introduction to Functional Programming Using Haskell.
Prentice-Hall, 1998.
[ bib |
http ]
|
|
[26]
|
Richard S. Bird.
Meertens' number.
Journal of Functional Programming, 8(1):83-88, 1998.
[ bib |
http ]
|
|
[27]
|
Richard S. Bird.
Allegories as a basis for algorithmics.
In Eugenio Moggi and Guiseppe Rosolini, editors, LNCS 1290:
Category Theory and Computer Science, pages 34-46. Springer-Verlag,
September 1997.
[ bib |
http ]
|
|
[28]
|
Richard S. Bird.
On merging and selection.
Journal of Functional Programming, 7(3):349-354, 1997.
[ bib |
http ]
|
|
[29]
|
Richard S. Bird.
On building trees with minimum height.
Journal of Functional Programming, 7(4):441-445, 1997.
[ bib |
http ]
|
|
[30]
|
Richard S. Bird, Geraint Jones, and Oege de Moor.
More haste, less speed: Lazy versus eager evaluation.
Journal of Functional Programming, 7(5):541-547, 1997.
[ bib |
.pdf |
http ]
|
|
[31]
|
Richard S. Bird and Jesús N. Ravelo.
On computing representatives.
Information Processing Letters, 63:1-7, 1997.
[ bib |
http ]
|
|
[32]
|
Richard S. Bird and Lambert G. L. T. Meertens, editors.
IFIP TC2 WG2.1 International Workshop on Algorithmic Languages
and Calculi, volume 95 of IFIP Conference Proceedings. Chapman &
Hall, 1997.
[ bib ]
|
|
[33]
|
Richard S. Bird.
Functional algorithm design.
Science of Computer Programming, 26(1-3):15-31, 1996.
[ bib |
http ]
|
|
[34]
|
Richard Bird and Oege de Moor.
The Algebra of Programming.
Prentice-Hall, 1996.
[ bib |
http ]
|
|
[35]
|
Richard Bird, Oege de Moor, and Paul Hoogendijk.
Generic functional programming with types and relations.
Journal of Functional Programming, 6(1):1-28, 1996.
[ bib |
.pdf ]
|
|
[36]
|
Richard S. Bird.
Functional algorithm design.
In Mathematics of Program Construction, volume 947 of
Lecture Notes in Computer Science, pages 2-17. Springer, 1995.
[ bib |
http ]
|
|
[37]
|
Richard Bird and Oege de Moor.
Relational program derivation and context-free language recognition.
In A. W. Roscoe, editor, A Classical Mind: Essays in Honour of
C. A. R. Hoare, chapter 2. Prentice-Hall, 1994.
[ bib ]
|
|
[38]
|
Richard Bird and Oege de Moor.
Hybrid dynamic programming.
Programming Research Group, Oxford, 1994.
[ bib ]
|
|
[39]
|
Richard S. Bird and Oege de Moor.
From dynamic programming to greedy algorithms.
In Bernhard Möller, Helmut Partsch, and Steve Schumann, editors,
IFIP TC2/WG2.1 State-of-the-Art Report on Formal Program Development,
volume 755 of Lecture Notes in Computer Science. Springer-Verlag, 1993.
[ bib |
.pdf |
http ]
|
|
[40]
|
Richard S. Bird and Oege de Moor.
Solving optimisation problems with catamorphisms.
In Bird et al. [41], pages 45-66.
[ bib |
.pdf |
http ]
|
|
[41]
|
Richard S. Bird, Carroll Morgan, and Jim Woodcock, editors.
Mathematics of Program Construction, volume 669 of Lecture
Notes in Computer Science. Springer, 1993.
[ bib |
http ]
|
|
[42]
|
Richard S. Bird and Oege de Moor.
List partitions.
Formal Aspects of Computing, 5:61-78, 1993.
[ bib |
http ]
|
|
[43]
|
R. S. Bird.
The last tail.
Journal of Functional Programming, 3(1):117-122, 1993.
[ bib ]
|
|
[44]
|
Richard S. Bird.
The smallest upravel.
Science of Computer Programming, 18:281-292, 1992.
[ bib |
http ]
|
|
[45]
|
Richard S. Bird.
Two greedy algorithms.
Journal of Functional Programming, 2(2):237-244, 1992.
[ bib ]
|
|
[46]
|
Richard S. Bird.
Unravelling greedy algorithms.
Journal of Functional Programming, 2(3):375-385, 1992.
[ bib ]
|
|
[47]
|
Richard S. Bird.
On removing duplicates.
Journal of Functional Programming, 1(2):235-243, 1991.
[ bib ]
|
|
[48]
|
Richard S. Bird.
The Minout problem.
Journal of Functional Programming, 1(1):121-124, January 1991.
[ bib ]
|
|
[49]
|
Richard S. Bird.
Knuth's problem.
In B. Möller, editor, IFIP TC2/WG2.1 Working Conference on
Constructing Programs from Specifications, pages 1-8. North-Holland, 1991.
[ bib ]
|
|
[50]
|
Richard S. Bird.
A calculus of functions for program derivation.
In David A. Turner, editor, Research Topics in Functional
Programming. Addison-Wesley, 1990.
Also available as Technical Monograph PRG-64, from the Programming
Research Group, Oxford University.
[ bib ]
|
|
[51]
|
Richard S. Bird.
Small specification exercises.
In W. H. J. Feijen, A. J. M. van Gasteren, D. Gries, and J. Misra,
editors, Beauty is our Business, pages 36-43. Springer-Verlag, 1990.
[ bib ]
|
|
[52]
|
Richard S. Bird, Jeremy Gibbons, and Geraint Jones.
Formal derivation of a pattern matching algorithm.
Science of Computer Programming, 12(2):93-104, July 1989.
[ bib |
http ]
|
|
[53]
|
Richard S. Bird.
Algebraic identities for program calculation.
Computer Journal, 32(2):122-126, April 1989.
[ bib |
http ]
|
|
[54]
|
Richard S. Bird and Philip L. Wadler.
An Introduction to Functional Programming.
Prentice-Hall, 1988.
[ bib ]
|
|
[55]
|
Richard S. Bird.
Lectures on constructive functional programming.
In Manfred Broy, editor, Constructive Methods in Computer
Science, pages 151-218. Springer-Verlag, 1988.
NATO ASI Series F Volume 55. Also available as Technical Monograph
PRG-69, from the Programming Research Group, Oxford University.
[ bib ]
|
|
[56]
|
Richard S. Bird and John Hughes.
The alpha-beta algorithm: An exercise in program transformation.
Information Processing Letters, 24(1):53-57, January 1987.
[ bib |
http ]
|
|
[57]
|
Richard S. Bird.
An introduction to the theory of lists.
In M. Broy, editor, Logic of Programming and Calculi of Discrete
Design, pages 3-42. Springer-Verlag, 1987.
NATO ASI Series F Volume 36. Also available as Technical Monograph
PRG-56, from the Programming Research Group, Oxford University.
[ bib ]
|
|
[58]
|
R. S. Bird.
A formal development of an efficient supercombinator compiler.
Science of Computer Programming, 8:113-137, 1987.
[ bib |
http ]
|
|
[59]
|
Richard S. Bird and Lambert Meertens.
Two exercises found in a book on algorithmics.
In Lambert Meertens, editor, Program Specification and
Transformation, pages 451-457. North-Holland, 1987.
[ bib ]
|
|
[60]
|
Richard S. Bird.
Transformational programming and the paragraph problem.
Science of Computer Programming, 6:159-189, 1986.
[ bib |
http ]
|
|
[61]
|
Richard S. Bird.
Addendum to ``The promotion and accumulation strategies in
transformational programming''.
ACM Transactions on Programming Languages and Systems,
7(3):490-492, July 1985.
[ bib ]
|
|
[62]
|
Richard S. Bird.
The promotion and accumulation strategies in transformational
programming.
ACM Transactions on Programming Languages and Systems,
6(4):487-504, October 1984.
See also [61].
[ bib |
http ]
|
|
[63]
|
Richard S. Bird.
Using circular programs to eliminate multiple traversals of data.
Acta Informatica, 21:239-250, 1984.
[ bib |
http ]
|
|
[64]
|
Richard S. Bird.
The jogger's problem.
Information Processing Letters, 13(3):114-117, 1981.
[ bib |
http ]
|
|
[65]
|
Richard S. Bird.
Surveyor's forum: A recurring bug.
ACM Computing Surveys, 13(2):243, 1981.
[ bib |
http ]
|
|
[66]
|
Richard S. Bird.
Tabulation techniques for recursive programs.
ACM Computing Surveys, 12(4):403-417, December 1980.
See [65].
[ bib |
http ]
|
|
[67]
|
Richard S. Bird.
Recursion elimination with variable parameters.
Computer Journal, 22(2):151-154, 1979.
[ bib |
http ]
|
|
[68]
|
Richard S. Bird.
Improving programs by the introduction of recursion.
Communications of the ACM, 20(11):856-863, November 1977.
[ bib |
http ]
|
|
[69]
|
Richard S. Bird.
Notes on recursion elimination.
Communications of the ACM, 20(6):434-439, 1977.
[ bib |
http ]
|
|
[70]
|
Richard S. Bird.
Two-dimensional pattern matching.
Information Processing Letters, 6(5):168-170, 1977.
[ bib |
http ]
|
|
[71]
|
Richard Bird.
Programs and Machines.
Wiley, 1976.
[ bib ]
|
|
[72]
|
Richard Bird.
Non recursive functionals.
Zeitschrift für mathematische Logik und Grundlagen der
Mathematik, 21:41-46, 1975.
[ bib ]
|
|
[73]
|
Richard Bird.
On transformations of programs.
Journal of Computer and System Sciences, 8:22-35, 1974.
[ bib ]
|
|
[74]
|
Richard S. Bird.
Speeding up programs.
Computer Journal, 17(4):337-339, 1974.
[ bib ]
|
|
[75]
|
Richard Bird.
A note on definition by cases.
Zeitschrift für mathematische Logik und Grundlagen der
Mathematik, 19:207-208, 1973.
[ bib ]
|
|
[76]
|
Richard Bird.
Integers with given initial digits.
American Mathematical Monthly, 79:367-370, 1972.
[ bib |
http ]
|
