for the few of us.

I was trying to simulate church numerals and primitive recursion in second rank polymorphism of Haskell. However, polymorphic types in Haskell can only be instantiated with monomorphic types.

We can even define primitive recursion, only that it does not have the desired type primrec :: (N -> b -> b) -> b -> N -> b. Therefore, predecessor does not get the type pred :: N a -> N a either.

Given a list, zip its first half with the reverse of its second half, in only “one and a half” traversals of the list.

It may be surprising that variations of the maximum segment sum (MSS) problem, a textbook example for the squiggolists, are still active topics for algorithm designers. These literate Haskell scripts presents a program solving two recently studied variations: computing the maximum sum of segments not longer than an upper-bound, and the maximum density (average) of segments not shorter than a lower-bound. 2007/06/26 Update: fixed binary search.

2007/11/04 Update: linear time algorithm for MSDL.

K. Nakano and S-C. Mu. A pushdown machine for recursive XML processing. In The Fourth Asian Symposium on Programming Language and Systems, LNCS 4279, pp. 340-356, November 2006.
[PDF]

S-C. Mu, Z. Hu and M. Takeichi, Bidirectionalizing tree transformation languages: a case study. In JSSST Computer Software (コンピュータソフトウェア) Vol. 23(2), pp. 129-141, 2006.
[PDF]

R. S. Bird and S-C. Mu, Countdown: a case study in origami programming. In Journal of Functional Programming Vol. 15(5), pp. 679-702, 2005.
[GZipped Postscript]

R. S. Bird and S-C. Mu, Inverting the Burrows-Wheeler transform. In Journal of Functional Programming Vol. 14(6) Special Issue on Functional Pearls, pp. 603-612, Novermber 2004.
[GZipped Postscript]

S-C. Mu, Z. Hu and M. Takeichi. An algebraic approach to bidirectional updating. In The Second Asian Symposium on Programming Language and Systems, pp. 2-18. November 2004.
[PDF]

Z. Hu, S-C. Mu and M. Takeichi, A programmable editor for developing structured documents based on bidirectional transformations. In Partial Evaluation and Semantics-Based Program Manipulation, pp. 178-189. August 2004.
[PDF]