FUNCTIONAL PEARLS Maximum marking problems (2008)
Here are two puzzles for you to solve. First, consider the binary tree in figure 1. Take apencil (I am assuming that this is your personal copy of JFP!) and mark some of the nodes in such away that...
Here are two puzzles for you to solve. First, consider the binary tree in Figure 1. Take a pencil (I am assuming that this is your personal copy of JFP!) and mark some of the nodes in such a way that...
A fair amount has been written on the subject of reasoning about pointer algorithms. There was a peak about 1980 when everyone seemed to be tackling the formal verication of the Schorr-Waite marking...
Rebuilding a Tree From Its Traversals: A Case Study of Program Inversion (2003)
Given the inorder and preorder traversal of a binary tree whose labels are all distinct, one can reconstruct the tree. This article examines two existing algorithms for rebuilding the tree in a...
FUNCTIONAL PEARL Unfolding pointer algorithms (2001)
A fair amount has been written on the subject of reasoning about pointer algorithms. There was a peak about 1980 when everyone seemed to be tackling the formal verication of the Schorr{Waite marking...
FUNCTIONAL PEARLS Maximum marking problems (2001)
Here are two puzzles for you to solve. First, consider the binary tree in figure 1. Take a pencil (I am assuming that this is your personal copy of JFP!) and mark some of the nodes in such a way that...
Functional pearl: Unfolding pointer algorithms (2001)
A fair amount has been written on the subject of reasoning about pointer algorithms. There was a peak about 1980 when everyone seemed to be tackling the formal verification of the Schorr–Waite...
de Bruijn notation as a nested datatype (1998)
Richard S. Bird, Ross Paterson, Sir Arthur, Conan Doyle
de Bruijn notation is a coding of lambda terms in which each occurrence of a bound variable x is replaced by a natural number, indicating the `distance' from the occurrence to the abstraction...
Between Dynamic Programming and Greedy: Data Compression (1995)
The derivation of certain algorithms can be seen as a hybrid form of dynamic programming and the greedy paradigm. We present a generic theorem about such algorithms, and show how it can be applied to...