Improving Sequences Library

What is Improving Sequences?

An improving sequence is a monotonic sequence of approximation values of a final value that are improved gradually according to some ordering relation. A computation using improving sequences proceeds by demanding for the next approximation value. If an approximation value in the middle of the improving sequence has sufficient information to yield the result of some part of the program, the computations that produce the remaining values can be pruned. By combining suitable improving sequences and primitive functions defined for the sequences, we can write efficient programs in the same form as simple and naive programs.

For details, please read the first paper (HOSC paper) listed below.

Publications

Iwasaki, H., Morimoto, T., Takano, Y.
Pruning with Improving Sequences in Lazy Functional Programs
Higher-Order and Symbolic Computation Vol.24, No.4, pp.281-309, 2011. (published in 2012) DOI: 10.1007/s10990-012-9086-3

Morimoto, T., Takano, Y., Iwasaki, H.
Instantly Turning a Naive Exhaustive Search into Three Efficient Searches with Pruning
Proc. 9th International Symposium on Practical Aspects of Declarative Languages (PADL 2007), Lecture Notes in Computer Science 4354, Springer-Verlag, pp.65-79, 2007. DOI: 10.1007/978-3-540-69611-7_4

Modules in Haskell

IS.hs is a module of improving sequences. (Figures 1, 2, and 3 in the HOSC paper.)
The following table shows the correspondences between the function names in the HOSC paper and those in IS.hs.
Game.hs is a module that implements algorithms for game tree searches. (Figures 7 and 9 in the HOSC paper.)
The following table shows the correspondences between the function names in the HOSC paper and those in Game.hs.

Functions for binary game tree searches (Figure 7 in the HOSC paper).

Functions for general game tree searches (Figure 9 in the HOSC paper).

Programs that use phantom types

The HOSC paper has discussions for checking the directions of improving sequences by using the technique of phantom types.

ISPhantom.hs is a phantom type version of IS.hs.
GamePhantom.hs is a phantom type version of Game.hs.