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.
The following table shows the correspondences between the function names in the HOSC paper and those in IS.hs.
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).
The HOSC paper has discussions for checking the directions of improving sequences by using the technique of phantom types.
Copyright (c) 2012, IS Project. All rights reserved. (Last Updated: 3 June 2014)