## Abstract

We propose a method of developing efficient programs for finding the optimal sequence, such as the maximum valued one among those that are acceptable. We introduce a method of deriving efficient algorithms from naive enumerate-and-choose-style ones. Our method is based on shortcut fusion, which is a program transformation for eliminating intermediate data structures passed between functions, and a set of auxiliary transformations. As an implementation of our method, we introduce a library for finding optimal sequences. The library consists of proposed transformations, together with functions useful to describe desirable sequences, so that naive enumerate-and-choose-style programs will be automatically improved.

This is a preview of subscription content, access via your institution.

## References

- 1.
Acar, U. A., Blelloch, G. E. and Harper, R., “Selective memoization,” in

*Conference Record of POPL 2003: The 30th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisisana, January 15-17, 2003*, ACM Press, pp. 14–25, 2003. - 2.
Arnborg, S., Lagergren, J. and Seese, D., “Easy problems for tree-decomposable graphs,”

*J. Algorithms, 12*, 2, pp. 308–340, 1991. - 3.
Bellman, R.,

*Dynamic Programming*, Princeton University Press, 1957. - 4.
Bentley, J.,

*Programming Pearls*, ACM, 1986. - 5.
Bird, R. S., “Maximum marking problems,”

*J. Funct. Program., 11, 4*, pp. 411–424, 2001. - 6.
Bird, R. S. and de Moor, O.,

*Algebra of Programming*, Prentice Hall, 1997. - 7.
Borie, R. B., Parker, R. G. and Tovey, C. A., “Automatic generation of lineartime algorithms from predicate calculus descriptions of problems on recursively constructed graph families,”

*Algorithmica, 7, 5&6*, pp. 555–581, 1992. - 8.
Chin, W.-N., Khoo, S.-C. and Jones, N., “Redundant call elimination via tupling,”

*Fundam. Inf., 69, 1–2*, pp. 1–37, 2006. - 9.
Chitil, O., “Type inference builds a short cut to deforestation,” in

*Proc. of the 4th ACM SIGPLAN International Conference on Functional Programming, ICFP’99, Paris, France, September 27-29, 1999*, ACM Press, pp. 249–260, 1999. - 10.
Cohen, N. H., “Eliminating redundant recursive calls,”

*ACM Trans. Program. Lang. Syst*., 5, 3, pp. 265–299, 1983. - 11.
Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E.,

*Introduction to algorithms, Second edition*, MIT Press, 2001. - 12.
de Moor, O., “Categories, Relations and Dynamic Programming,” Ph.D. thesis,

*Technical Monograph PRG-98*, Oxford University Computing Laboratory, 1992. - 13.
de Moor, O., “A generic program for sequential decision processes,” in

*Programming Languages: Implementations, Logics and Programs, 7th International Symposium, PLILP’95, Utrecht, The Netherlands, September 20-22, 1995, Proceedings, LNCS, 982*, Springer-Verlag, pp. 1–23, 1995. - 14.
Giegerich, R., Meyer, C. and Steffen, P., “A discipline of dynamic programming over sequence data,”

*Sci. Comput. Program., 51, 3*, pp. 215–263, 2004. - 15.
Giegerich, R. and Steffen, P., “Implementing algebraic dynamic programming in the functional and the imperative programming paradigm,” in

*Mathematics of Program Construction, 6th International Conference, MPC 2002, Dagstuhl Castle, Germany, July 8-10, 2002, Proceedings, LNCS, 2386*, Springer-Verlag, pp. 1–20, 2002. - 16.
Gill, A., “Cheap Deforestation for Non-strict Functional Languages,” Ph.D. thesis, Department of Computing Science, Glasgow University, 1996.

- 17.
Gill, A., Launchbury, J. and Peyton Jones, S., “A short cut to deforestation,” in

*FPCA ’93 Conference on Functional Programming Languages and Computer Architecture. Copenhagen, Denmark, 9-11 June 1993*, ACM Press, pp. 223–232, 1993. - 18.
Hu, Z., Iwasaki, H., Takeichi, M. and Takano, A., “Tupling calculation eliminates multiple data traversals,” in

*Proc. of the 2nd ACM SIGPLAN International Conference on Functional Programming, ICFP’97, Amsterdam, The Netherlands, June 9-11, 1997*, ACM Press, pp. 164–175, 1997. - 19.
Kabanov, J. and Vene, V., “Recursion schemes for dynamic programming,” in

*Mathematics of Program Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3-5, 2006, Proceedings, LNCS, 4014*, Springer- Verlag, pp. 235–252, 2006. - 20.
Launchbury, J. and Sheard, T., “Warm fusion: Deriving build-catas from recursive definitions,” in

*Conference Record of FPCA ’95 SIGPLAN-SIGARCHWG2.8 Conference on Functional Programming Languages and Computer Architecture. La Jolla, CA, USA, 25-28 June 1995*, ACM Press, pp. 314–323, 1995. - 21.
Liu, Y. A. and Stoller, S. D., “Dynamic programming via static incrementalization,”

*Higher-Order Symb. Comput., 16, 1–2*, pp. 37–62, 2003. - 22.
Liu, Y. A., Stoller, S. D., Li, N., and Rothamel, T., “Optimizing aggregate array computations in loops,”

*ACM Trans. Program. Lang. Syst., 27, 1*, pp. 91–125, 2005. - 23.
Morihata, A., “A short cut to optimal sequences,” in

*Proc. of the Seventh Asian Symposium on Programming Languages and Systems, APLAS 2009, LNCS, 5904*, Springer-Verlag, pp. 63–78, 2009. - 24.
Morihata, A., “Calculational Approach to Automatic Algorithm Construction,” Ph.D. thesis, Department of Mathematical Informatics, University of Tokyo, 2009.

- 25.
Morihata, A., Matsuzaki, K. and Takeichi, M., “Write it recursively: A generic framework for optimal path queries,” in

*Proc. of the 2008 ACM SIGPLAN International Conference on Functional Programming, ICFP 2008, Sept. 22-24, 2008, Victoria, BC, Canada*, ACM Press, pp. 169–178, 2008. - 26.
Mu, S.-C., “Maximum segment sum is back: Deriving algorithms for two segment problems with bounded lengths,” in

*Proc. of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM 2008, San Francisco, California, USA, January 7-8, 2008*, ACM Press, pp. 31–39, 2008. - 27.
Peyton Jones, S. ed.,

*Haskell 98 Language and Libraries: The Revised Report*, Cambridge University Press, 2003. - 28.
Peyton Jones, S., Tolmach, A. and Hoare, T., “Playing by the rules: Rewriting as a practical optimisation technique in GHC,” in

*Proc. of 2001 ACM SIGPLAN Haskell Workshop (HW’2001), Firenze, Italy, 2nd September 2001, Technical Report UU-CS-2001-23*, Institute of Information and Computing Sciences Utrecht University, pp. 203–233, 2001. - 29.
Puchinger, J. and Stuckey, P. J., “Automating branch-and-bound for dynamic programs,” in

*Proc. of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM 2008, San Francisco, California, USA, January 7-8, 2008*, ACM Press, pp. 81–89, 2008. - 30.
Sasano, I., Hu, Z., Takeichi, M. and Ogawa, M., “Make it practical: A generic linear-time algorithm for solving maximum-weightsum problems,” in

*Proc. of the 5th ACM SIGPLAN International Conference on Functional Programming, ICFP’00*, ACM Press, pp. 137–149, 2000. - 31.
Sasano, I., Ogawa, M. and Hu, Z., “Maximum marking problems with accumulative weight functions,” in

*Theoretical Aspects of Computing - ICTAC 2005, Second International Colloquium, Hanoi, Vietnam, October 17-21, 2005, Proceedings, LNCS, 3722*, Springer-Verlag, pp. 562–578, 2005. - 32.
Wadler, P., “Theorems for free!,” in

*FPCA ’89 Conference on Functional Programming Languages and Computer Architecture. Imperial College, London, England, 11-13 September 1989*, ACM Press, pp. 347–359, 1989. - 33.
Yokoyama, T., Hu, Z. and Takeichi, M., “Calculation rules for warming-up in fusion transformation,” in

*the 2005 Symposium on Trends in Functional Programming, TFP 2005, Tallinn, Estonia, 23-24 September 2005*, pp. 399–412, 2005. - 34.
Zantema, H., “Longest segment problems,”

*Sci. Comput. Program., 18, 1*, pp. 39–66, 1992.

## Author information

### Affiliations

### Corresponding author

## Additional information

A preliminary report of this work was appeared in 23).

## About this article

### Cite this article

Morihata, A. A Short Cut to Optimal Sequences.
*New Gener. Comput.* **29, **31–59 (2011). https://doi.org/10.1007/s00354-010-0098-4

Received:

Revised:

Published:

Issue Date:

### Keywords

- Functional Programming
- Dynamic Programming
- Program Transformation
- Shortcut Fusion