Ralf Hinze

Polytypic Functions Over Nested Datatypes †

Keywords: Functional programming, generic programming, nested datatypes, rational trees, reductions

The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying theory is beautiful and well developed. It is a curse because the initial algebra semantics is restricted to so-called regular datatypes. Recent work by R. Bird and L. Meertens [3] on the semantics of non-regular or nested datatypes suggests that an extension to general datatypes is not entirely straightforward. Here we propose an alternative that extends polytypism to arbitrary datatypes, including nested datatypes and mutually recursive datatypes. The central idea is to use rational trees over a suitable set of functor symbols as type arguments for polytypic functions. Besides covering a wider range of types the approach is also simpler and technically less involving than previous ones. We present several examples of polytypic functions, among others polytypic reduction and polytypic equality. The presentation assumes some background in functional and in polytypic programming. A basic knowledge of monads is required for some of the examples.

Introduction

A polytypic function is a function that is defined by induction on the structure of types. The archetypical example of a polytypic function is size :: f a Int, which counts the number of values of type a in a given value of type f a. The function size can sensibly be defined for each polymorphic type and it is usually a tiresome, routine matter to do so. A polytypic programming language allows to program size once and for all times. The specialization of size to concrete instances of f is then handled automatically by the system.

Polytypic programming is usually based on the initial algebra semantics of datatypes. To illustrate, consider the following definition of polymorphic lists.

data List a ✁ 1 ✂ a ✄ List a
The meaning of List a is given by the initial F a -algebra of the functor F a ☎ b✆ ✝✁ F ☎ a✞ b✆ ✟✁ 1 ✂ a ✄ b. The initial algebra can be seen as the least solution of the equation List a ✁ F ☎ a✞ List a✆ . The initial algebra approach, however, has its limitations. It fails, for example, to give a meaning to so-called non-regular or nested datatypes such as the type of perfectly balanced, binary leaf trees [START_REF] Hinze | Functional Pearl: Perfect trees and bit-reversal permutations[END_REF] data Perfect a ✁ a ✂ Perfect ☎ a ✄ a✆ ✡✠ Since the recursive call of Perfect on the right-hand side is not a copy of the declared type on the left-hand side, the equation cannot be rewritten into the form Perfect a ✁ G ☎ a✞ Perfect a✆ for some G. A way out of this dilemma is to consider initial algebras of higher-order functors [START_REF] Bird | Nested datatypes[END_REF]. If we lift coproduct ☎ ✂ ✆ and product ☎ ✄ ✆ to functors,

☎ F 1 ✂ F 2 ✆ T ✁ F 1 T ✂ F 2 T and ☎ F 1 ✄ F 2 ✆ T ✁ F 1 T ✄ F 2 T
, the above type definitions can be rewritten as functor equations:

List ✁ K1 ✂ Id ✄ List ✞ Perfect ✁ Id ✂ Perfect ☎ Id ✄ Id✆ ✞
where KT is the constant functor, Id is the identity functor, and ☎ ✆ denotes functor composition. The meaning of List and Perfect can now be defined as the initial algebra of the associated higher-order functor. While this approach shares some of the elegance and ease of the first-order approach, it also has its drawbacks. It appears that the associated fold-operations, which are at the heart of polytypic programming, are limited in expressibility. The crucial point is that fold operates on natural transformations, ie it takes polymorphic functions to polymorphic functions. For instance, the fold operator on Perfect takes a function of type ✁ a✠ a ✂ f ☎ a ✄ a✆ f a to a function of type ✁ a✠ Perfect a f a for some fixed f . This is, however, too restrictive for many applications, for instance, for summing up a tree of integers. Therefore, it is at least questionable whether initial algebras of higher-order functors can serve as a viable basis for polytypism on nested datatypes.

Back to the first-order case. In a polytypic language the function size :: f a Int is parametrised by the functor f and is defined by induction on the structure of f . As an aside, since size is parametrised by a functor, we will qualify size more precisely as a polyfunctorial function. The qualifier polytypic will be used as a general term for functions that are parametrised by functors of arbitrary arity. Now, inspired by the initial algebra semantics the structure of functors is usually given by the following grammar, see [START_REF] Meertens | Calculate polytypically![END_REF] or [START_REF] Jeuring | Polytypic programming[END_REF].

B ✁ KT ✂ Fst ✂ Snd ✂ B ✂ B ✂ B ✄ B ✂ F B F ✁ µB
The non-terminal B generates the language of bifunctors. By µB we denote the unary functor F given as the least solution of the equation F a ✁ B ☎ a✞ F a✆ . The functor F ✁ µB is also known as a type functor. This representation entails that a non-recursive, polymorphic functor F is modelled by µB with B ☎ a✞ b✆ ✝✁ F a, whereas a non-polymorphic, recursive datatype induced by a functor F is modelled by µB with B ☎ a✞ b✆ ✁ F b. Thus, µ ☎ K1 ✂ Fst✆ encodes the datatype Maybe and µ ☎ K1 ✂ Snd✆ encodes the datatype of Peano numerals.

One can reasonably argue that the definition of unary functors via minimalization of bifunctors is not the most direct way to go. An alternative that we explore in this article is to define functor expressions as rational trees [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF] over the following grammar of unary functors.

F ✁ KT ✂ Id ✂ F ✂ F ✂ F ✄ F ✂ F F
This approach is, of course, inspired by the way types are introduced in most functional programming languages. Type definitions usually take the form of recursion equations. If we interpret these equations purely syntactically, each equation defines a unique rational tree. Recall that a rational (or regular) tree is an infinite tree that has only a finite number of subtrees. rational trees. Since the set of subtrees is finite, we can always draw a rational tree as a finite tree with additional back or cross edges.

The major difference to previous approaches lies in the use of infinite instead of finite trees as type arguments for polytypic functions. This change is not as problematic as one might think at first sight. For instance, we can still define polytypic functions recursively and prove polytypic properties inductively. Of course, to make things work we must impose the usual conditions: functions must be continuous and properties must be chain complete. In essence this means that the class of functors is itself modelled by a non-strict datatype as opposed to an inductive datatype. We could even consider functors given by arbitrary infinite trees. The focus on rational trees is, however, necessary for practical considerations. It guarantees that the specialization of polytypic functions always terminates.

The rest of this article is organized as follows. Sec. 2 introduces rational trees and functor expressions. Sec. 3 and Sec. 4 give several examples of polyfunctorial functions, among others a polytypic map and polytypic reduction. We will see that nested datatypes add an interesting new dimension to polytypic programming. For instance, efficiency becomes a concern: a straightforward implementation of size has a quadratic running time for some nested datatypes. Improving its running time makes a nice example in polytypic program derivation. Sec. 5 extends the approach to n-ary functors and presents further examples, among others polytypic equality and a polytypic monadic map. This section requires a basic knowledge of monads. Finally, Sec. 6 reviews related work and points out directions for future work.

Functor expressions

There are several ways to represent rational trees, see, for instance, [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF]Sec. 4]. The most obvious and, in fact, the most convenient way is to use systems of recursion equations. Let Σ ✁ ✚✙ n ✛ 0 Σ n be a set of function symbols and X be a set of variables, we denote by T ☎ Σ✞ X ✆ the set of first-order terms over Σ and X. A system of recursion equations over Σ is of the form ✜

x 1 ✁ t 1 ✞ ✠ ✠ ✠ ✞ x n ✁ t n ✢ with t i ✣ T ☎ Σ✞ X ✆ , X ✁ ✤✜ x 1 ✞ ✠ ✠ ✠ ✞ x n ✢ , and x i ✥ ✁ x j for i ✥ ✁ j.
The elements of X are termed recursion variables. A system of recursion equations is in canonical form if the right-hand side of each equation is of the form f ☎ x 1 ✞ ✠ ✠ ✠ ✞ x n ✆ where f ✣ Σ n is an n-ary function symbol and the x i are recursion variables. Each system can be transformed into an equivalent system that is in canonical form. For instance, the system

✜ x ✁ Id ✂ x ☎ Id ✄ Id✆ ✢ has the canonical form ✜ x ✁ x 1 ✂ x 2 ✞ x 1 ✁ Id✞ x 2 ✁ x x 3 ✞ x 3 ✁ Id ✄ Id ✢ . Note that
the canonicalization introduces additional recursion variables. Furthermore, we tacitly assume that an equation of the form x ✁ x is replaced by x ✁ Ω where Ω is a new nullary function symbol representing the 'bottom' tree.

It is well-known that each canonical system of recursion equations has a unique solution in the realm of rational trees. An unrestricted system has in general only a least solution. Each tree is, for instance, a solution of the trivial system ✜ x ✁ x ✢ . Now, a functor tree is a rational tree over the following set of 'functor' symbols

F ✁ KT ✂ Id ✂ F ✂ F ✂ F ✄ F ✂ F F ✞ ie Σ ✁ Σ 0 Σ 2 with Σ 0 ✁ ✡✜ Kt ✂ t ✣ T ✢ ✜ Id ✢ and Σ 2 ✁ ✡✜ ✂ ✞ ✄ ✞ ✢ .
We agree upon that ☎ ✆ binds more tightly than

☎ ✄ ✆
, which in turn takes precedence over

☎ ✂ ✆ . For instance, F ✂ G ✄ H H means F ✂ ☎ G ✄ ☎ H H✆ ✆ .
Let us consider some examples. Finite functor trees correspond to so-called polynomial functors.

∆ ✁ Id ✄ Id Maybe ✁ K1 ✂ Id
The functor ∆ is called the diagonal or square functor, Maybe a is the type of optional values of type a.

Let us call a functor composition F G non-trivial if neither F nor G equals the identity functor. ‡ Possibly infinite functor trees where cycles only pass through the right-hand branches of non-trivial functor compositions are known as regular functors.

List ✁ K1 ✂ Id ✄ List Tree ✁ Id ✂ ∆ Tree Rose ✁ Id ✄ List Rose
The functor List corresponds to the ubiquitous datatype of polymorphic lists, Tree encompasses polymorphic, binary leaf trees, and Rose is the datatype of multi-way branching trees.

If cycles pass through the left-hand branches of non-trivial functor compositions (or through both branches), we have non-regular functors.

Perfect ✁ Id ✂ Perfect ∆ Nest ✁ K1 ✂ Id ✄ Nest ∆ Bush ✁ K1 ✂ Id ✄ Bush Bush
The meaning of these functor expressions becomes more intelligible if we unroll the definitions a few steps and massage the result using the following laws.

KT F ✁ KT (1) Id F ✁ F (2) F Id ✁ F (3) ☎ F 1 ✂ F 2 ✆ G ✁ F 1 G ✂ F 2 G (4) ☎ F 1 ✄ F 2 ✆ G ✁ F 1 G ✄ F 2 G (5) ☎ F 1 F 2 ✆ F 3 ✁ F 1 ☎ F 2 F 3 ✆ (6)
Unrolling Perfect yields

Perfect ✁ Id ✂ ☎ ∆ ✂ ☎ ∆ 2 ✂ ☎ ∆ 3 ✂ ✆ ✆ ✆ ✞ ‡
By 'equal' we mean semantic equality of functors, see below.

where F n is given by F 0 ✁ Id and F n 1 ✁ F F n . If we interpret ∆ n as the type of perfectly balanced, binary leaf trees of height n, we have that Perfect comprises perfect trees of arbitrary height.

The functor Nest has a similar reading.

Nest ✁ K1 ✂ Id ✄ ☎ K1 ✂ ∆ ✄ ☎ K1 ✂ ∆ 2 ✄ ☎ K1 ✂ ∆ 3 ✄ ✆ ✆ ✆ If we compare Nest to List ✁ K1 ✂ Id ✄ ☎ K1 ✂ Id ✄ ☎ K1 ✂ Id ✄ ☎ K1 ✂ Id ✄ ✆ ✆ ✆ ✞
we see that Nest comprises 'lists' whose i-th element is a perfect tree of height i. Alternatively, we may view values of type Nest as node-oriented perfect trees, where the i-th list element describes the sequence of labels at depth i.

Partially unrolling Bush yields

Bush ✁ K1 ✂ Id ✄ ☎ K1 ✂ Bush ✄ ☎ K1 ✂ Bush 2 ✄ ☎ K1 ✂ Bush 3 ✄ ✆ ✆ ✆ ✠
Thus, Bush contains 'lists' whose i-th element is a member of Bush i . A truly bewildering form of recursion.

Interestingly, the laws above can be used to eliminate functor composition from the definitions of regular functors. Consider the definition of rose trees, which contains the composition List Rose. Introducing a new functor for the composition, say, Forest we obtain

Rose ✁ ✁ Id ✄ Forest Forest ✁ K1 ✂ Rose ✁ ✄ Forest ✠
Since both types, Rose and Rose ✁ , have the same structure, they are equivalent from a polytypic perspective. This statement can be made precise if we interpret type equations as algebraic equations [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF]Sec. 5.1]. Then, both Rose and Rose ✁ indeed denote the same rational tree. This implies, in particular, that care must be taken to ensure that polytypic functions behave the same on both definitions (see Sec. 3). As an aside, note that mutually recursive definitions like the two above are covered by recursion equations in a natural way.

Polytypic map

Our first example of a polytypic function is the function map, which describes the action of a functor on arrows (ie functions). This is, of course, not a coincidence. As we shall see, map is an important building block for virtually all polytypic functions.

To define map we make use of the following auxiliary functions which, as a matter of fact, establish

☎ ✂ ✆ and ☎ ✄ ✆ as bifunctors. § ☎ f 1 f 2 ✆ ☎ inl a 1 ✆ ✁ f 1 a 1 ☎ f 1 f 2 ✆ ☎ inr a 2 ✆ ✁ f 2 a 2 f 1 ✂ f 2 ✁ ☎ inl ✁ f 1 ✆ ☎ inr ✁ f 2 ✆ ☎ f 1 ✂ f 2 ✆ a ✁ ☎ f 1 a✞ f 2 a✆ outl ☎ a 1 ✞ a 2 ✆ ✁ a 1 outr ☎ a 1 ✞ a 2 ✆ ✁ a 2 f 1 ✄ f 2 ✁ ☎ f 1 ✁ outl✆ ✂ ☎ f 2 ✁ outr✆
The polytypic map is then given by the following definition.

map✄ f ☎ :: ☎ a b✆ ☎ f a f b✆ map✄ Kt☎ ϕ ✁ id map✄ Id☎ ϕ ✁ ϕ map✄ f ✂ g☎ ϕ ✁ map✄ f ☎ ϕ ✂ map✄ g☎ ϕ map✄ f ✄ g☎ ϕ ✁ map✄ f ☎ ϕ ✄ map✄ g☎ ϕ map✄ f g☎ ϕ ✁ map✄ f ☎ ☎ map✄ g☎ ϕ✆
The first line specifies the type of map. The notation map✄ f ☎ has been chosen to emphasize that map is parametrised by a functor. Polytypic functions are always written using angle brackets, which makes it easy to distinguish them from ordinary functions.

In general, a polyfunctorial function poly✄ f ☎ :: τ

☎ f ✆ is given by a set of functions d s :: τ ☎ f 1 ✆ ✄ ✠ ✠ ✠ ✄ τ ☎ f n ✆ τ ☎ s ☎ f 1 ✞ ✠ ✠ ✠ ✞ f n ✆ ✆ , one for each functor symbol s ✣ Σ.
We usually define the functions implicitly using equations of the form poly✄ s

☎ f 1 ✞ ✠ ✠ ✠ ✞ f n ✆ ✆☎ ✝✁ d s ☎ poly✄ f 1 ☎ ✞ ✠ ✠ ✠ ✞ poly✄ f n ☎ ✆ .
Furthermore, we assume that d Ω ✁ ✞✝ for the 'bottom' tree Ω. In the example above we have, for instance, d Id ✁ id and

d✟ ✡✠ ☛ ☎ m 1 ✞ m 2 ✆ ✟✁ m 1 ✁ m 2 .
This information is sufficient to define a unique function poly✄ f ☎ for each functor expression f [6, Prop. 2.4.2]. However, there is one further requirement. The polyfunctorial should be invariant with respect to the functor equations (1), . . . , [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF], ie

poly✄ KT F☎ ✁ poly✄ KT ☎ poly✄ Id F☎ ✁ poly✄ F☎ poly✄ F Id☎ ✁ poly✄ F☎ poly✄ ☎ F 1 ✂ F 2 ✆ G☎ ✁ poly✄ F 1 G ✂ F 2 G☎ poly✄ ☎ F 1 ✄ F 2 ✆ G☎ ✁ poly✄ F 1 G ✄ F 2 G☎ poly✄ ☎ F 1 F 2 ✆ F 3 ☎ ✁ poly✄ F 1 ☎ F 2 F 3 ✆ ✆☎ ✠
If poly✄ f ☎ violates one of these constraints, then it is sensitive to the form in which f is written, a situation which is clearly undesirable. For instance, poly✄ Rose☎ and poly✄ Rose ✁ ☎ should be identical since Rose and Rose ✁ define the same functor. It is immediate from its definition that map✄ f ☎ satisfies these conditions. § Examples are given in a pidgin based on the functional programming language Haskell 98 [START_REF] Augustsson | Haskell 98 -A non-strict, purely functional language[END_REF]. We assume, however, that primitive functions are non-curried, ie ☞ ✍✌ ✏✎ has type Bool ✑ Bool ✒ Bool rather than Bool ✒ ✞☞ Bool ✒ Bool✎ .

From the definition of map✄ f ☎ we can derive specializations for different instances of f . Here is the familiar definition of map on List. map✄ List☎ ϕ ✁ id ✂ ϕ ✄ map✄ List☎ ϕ Note that the process of specialization always terminates since the 'functor argument' is given by a rational tree, which has only a finite set of subtrees. Now, if we specialize map for non-regular functors something interesting happens.

map✄ Perfect☎ ϕ ✁ ϕ ✂ map✄ Perfect☎ ☎ ϕ ✄ ϕ✆ The type of map✄ Perfect☎ is ☎ a b✆ ☎ Perfect a
Perfect b✆ . The recursive call on the right-hand side, however, has type

☎ ∆ a ∆ b✆ ☎ Perfect ☎ ∆ a✆ Perfect ☎ ∆ b✆ ✆ , which is a substitution instance
of map✄ Perfect☎ 's type. This means that map✄ Perfect☎ is a so-called polymorphically recursive function [START_REF] Mycroft | Polymorphic type schemes and recursive definitions[END_REF]. It should be noted that the Hindley-Milner type system, which underlies most of today's functional programming languages, does not allow polymorphic recursion. Furthermore, a suitable extension of the system has been shown to be undecidable [START_REF] Henglein | Type inference with polymorphic recursion[END_REF]. The functional programming language Haskell [START_REF] Augustsson | Haskell 98 -A non-strict, purely functional language[END_REF] allows polymorphic recursion only if an explicit type signature is provided for the function. We will assume henceforth that polymorphic recursion is supported by the underlying programming language.

In general, the specialization of a polytypic function poly✄ f ☎ for a given instance of f is defined as follows. Assume that the functor is given by a canonical system of recursion equations. For each equation

f ✁ s ☎ f 1 ✞ ✠ ✠ ✠ ✞ f n ✆ a function definition of the form poly✄ f ☎ ✁ d s ☎ poly✄ f 1 ☎ ✞ ✠ ✠ ✠ ✞ poly✄ f n ☎ ✆ is generated. It is
straightforward to generalize the process of specialization to arbitrary systems of recursion equations.

To prove properties of polytypic function we can employ the principle of fixpoint induction. If P is a chain complete property of functor trees, it suffices to show

P ☎ Ω✆ P ☎ Kt✆ P ☎ Id✆ P ☎ F✆ P ☎ G✆ ✁ ✂✁ P ☎ F ✂ G✆ P ☎ F✆ P ☎ G✆ ✁ ✂✁ P ☎ F ✄ G✆ P ☎ F✆ P ☎ G✆ ✁ ✂✁ P ☎ F G✆ ✠
Using a simple fixpoint induction we can prove, for instance, the following functorial properties of map✄ f ☎ .

map✄ f ☎ id ✁ id map✄ f ☎ ☎ ϕ ✁ ψ✆ ✁ map✄ f ☎ ϕ ✁ map✄ f ☎ ψ
The proof for coproduct and product relies on the fact that ☎ ✂ ✆ and ☎ ✄ ✆ are themselves bifunctors.

☎ f 1 ✂ f 2 ✆ ✁ ☎ g 1 ✂ g 2 ✆ ✁ ☎ f 1 ✁ g 1 ✆ ✂ ☎ f 2 ✁ g 2 ✆ (7) ☎ f 1 ✄ f 2 ✆ ✁ ☎ g 1 ✄ g 2 ✆ ✁ ☎ f 1 ✁ g 1 ✆ ✝✄ ☎ f 2 ✁ g 2 ✆ (8)
Only the proof of map✄ Ω☎ id ✁ id requires a bit of fudging. We have that map✄ Ω☎ ϕ ✁ λa ✝ so we must in effect show that λa ✝ ✁ id. This equation holds, however, since Ω accommodates only the bottom element.

Polytypic reduction

A reduction is a function of type f a a that collapses a structure of values of type a into a single value of type a. Because of its destructive nature reductions are also known as crushes. The archetypical example of a reduction is the function that sums a structure of integers, for instance, a list or a tree of integers. It is well-known that reductions can be defined completely generically for all regular functors [START_REF] Meertens | Calculate polytypically![END_REF]. In the sequel we show how to generalize reductions to non-regular functors. The ability to define reductions on nested datatypes is of some importance since it is not possible to sum a nested datatype using a fold. Note that this implies that reductions are in a sense more general than folds. They are, however, also less general since, for instance, mapping functions on regular functors can be defined using folds, but cannot be expressed in the form of a crush. Thus, reductions [START_REF] Meertens | Calculate polytypically![END_REF] and folds [START_REF] Malcolm | Data structures and program transformation[END_REF] are different, incomparable generalizations of the classic reduction operator ☎ ✁ ✆ on join-lists [START_REF] Bird | Lectures on constructive functional programming[END_REF]. For a more detailed comparison we refer the interested reader to [START_REF] Meertens | Calculate polytypically![END_REF].

To define a reduction we require two ingredients: a value e :: a and a binary operation op :: ∆ a a. Usually but not necessarily e is the neutral element of op.

reduce✄ f ☎ :: a ☎ ∆ a a✆ ☎ f a a✆ reduce✄ f ☎ e op ✁ red ✄ f ☎ where red ✄ Kt☎ ✁ const e red ✄ Id☎ ✁ id red ✄ f ✂ g☎ ✁ red ✄ f ☎ red ✄ g☎ red ✄ f ✄ g☎ ✁ op ✁ ☎ red ✄ f ☎ ✟✄ red✄ g☎ ✆ red ✄ f g☎ ✁ red ✄ f ☎ ✁ map✄ f ☎ ☎ red ✄ g☎ ✆
The definition coincides with the one given by L. Meertens [START_REF] Meertens | Calculate polytypically![END_REF], the only difference is that the treatment of recursion is implicit-the specialization automatically takes care of recursion-rather than explicit.

This alone suffices to define reduce✄ f ☎ for all datatypes including nested datatypes such as Perfect.

The most interesting equation is probably the last one: to reduce a value of type f ☎ g a✆ , the reduction red ✄ g☎ is first mapped on f to give a value of type f a, which is then reduced to a value of type a. To see reduce✄ f ☎ in action let us specialize the definition to the type of perfect trees (note that red ✄ ∆☎ ✟✁ op).

red ✄ Perfect☎ ✁ id red ✄ Perfect☎ ✏✁ map✄ Perfect☎ op Assume that we want to reduce a perfect tree of height n. The function map✄ Perfect☎ op, which has type Perfect ☎ ∆ a✆ Perfect a, takes a tree of height i ✂ 1 to a tree of height i, which is then reduced by a recursive call to red ✄ Perfect☎ . After n iterations we obtain the desired value of type a. What about red ✄ Perfect☎ 's running time? Let us assume that op is a constant-time operation. The call map✄ Perfect☎ op then takes time proportional to the size of the tree. Since the size of the tree is halved in each step, we obtain a running time of

2 n ✂ 2 n✂ 1 ✂ ✂ 2 ✂ 1 ✁ Θ ☎ 2 n ✆ ✠
Thus, the red ✄ Perfect☎ takes time proportional to the size of the tree. Does this hold in general? Unfortu- nately not, as the following example shows.

Maybe ✁ Nothing ☎ K1✆ ✂ Just Id Tower ✁ End Id ✂ Recurse ☎ Tower Maybe✆
We have added fancy names for the injection functions to make the examples more readable.

☎

Just n a✆ ✆ . The reduction on Tower is given by the following equation.

red ✄ Tower☎ ✁ id red ✄ Tower☎ ✁ map✄ Tower☎ ☎ const e id✆
The crush of Recurse n ☎ End ☎ Just n a✆ ✆ proceeds essentially as before: map✄ Tower☎ ☎ const e id✆ maps the

value Recurse i ☎ End ☎ Just i 1 a✆ ✆ to Recurse i ☎ End ☎ Just i a✆ ✆
, which is then reduced by a recursive call to red ✄ Tower☎ . The major difference to the preceding example is that in each step the size of the argument is only decreased by a constant amount. Consequently, we have a total running time of

n ✂ n ✁ 1 ✂ ✂ 2 ✂ 1 ✁ Θ ☎ n 2 ✆ ✞
which shows that red ✄ Tower☎ 's running time is quadratic with respect to the size of its argument. In- terestingly, the efficiency of reduce✄ f ☎ is not a problem if f is a regular functor. In this case reduce✄ f ☎ always takes time linear to the size of the crushed structure. The argument roughly runs as follows: Recall that each regular functor has an equivalent, composition-free definition. If functor composition is not used, red ✄ f ☎ clearly runs in linear time. The asymptotic running time of red ✄ f ☎ is, however, the same for equivalent functor definitions.

Fortunately, it is straightforward to improve the efficiency of reduce✄ f ☎ . We simply define a function that combines a reduction with a map, ie we seek for a function redmap✄ f ☎ that satisfies

redmap✄ f ☎ ϕ ✁ red ✄ f ☎ ✁ map✄ f ☎ ϕ ✞ red ✄ f ☎ ✁ redmap✄ f ☎ id ✠
This idiom is, in fact, a very old one. It appears, for instance, in [START_REF] Bird | Lectures on constructive functional programming[END_REF] where it is shown that each homomorphism on lists (ie each fold) can be expressed in this form. The derivation of redmap✄ f ☎ is a simple exercise in program calculation and proceeds almost mechanically. For the two base cases we have

redmap✄ Kt☎ ϕ ✁ red ✄ Kt☎ ✏✁ map✄ Kt☎ ϕ ✁ const e ✁ id ✁ const e ✞ redmap✄ Id☎ ϕ ✁ red ✄ Id☎ ✁ map✄ Id☎ ϕ ✁ id ✁ ϕ ✁ ϕ ✠
The derivation for coproducts and products rests on their properties as bifunctors, ie on equations [START_REF] Fokkinga | Monadic maps and folds for arbitrary datatypes[END_REF] and [START_REF] Henglein | Type inference with polymorphic recursion[END_REF].

redmap✄ f ✂ g☎ ϕ ✁ red ✄ f ✂ g☎ ✁ map✄ f ✂ g☎ ϕ ✁ ☎ red ✄ f ☎ red ✄ g☎ ✆ ✁ ☎ map✄ f ☎ ϕ ✂ map✄ g☎ ϕ✆ ✁ ☎ red ✄ f ☎ ✁ map✄ f ☎ ϕ✆ ☎ red ✄ g☎ ✁ map✄ g☎ ϕ✆ ✁ redmap✄ f ☎ ϕ redmap✄ g☎ ϕ redmap✄ f ✄ g☎ ϕ ✁ red ✄ f ✄ g☎ ✁ map✄ f ✄ g☎ ϕ ✁ op ✁ ☎ red ✄ f ☎ ✝✄ red ✄ g☎ ✆ ✁ ☎ map✄ f ☎ ϕ ✄ map✄ g☎ ϕ✆ ✁ op ✁ ☎ ☎ red ✄ f ☎ ✁ map✄ f ☎ ϕ✆ ✝✄ ☎ red ✄ g☎ ✁ map✄ g☎ ϕ✆ ✆ ✁ op ✁ ☎ redmap✄ f ☎ ϕ ✄ redmap✄ g☎ ϕ✆
And finally, for the composition of functors we obtain

redmap✄ f g☎ ϕ ✁ red ✄ f g☎ ✏✁ map✄ f g☎ ϕ ✁ red ✄ f ☎ ✏✁ map✄ f ☎ ☎ red ✄ g☎ ✆ ✁ map✄ f ☎ ☎ map✄ g☎ ϕ✆ ✁ red ✄ f ☎ ✏✁ map✄ f ☎ ☎ red ✄ g☎ ✁ map✄ g☎ ϕ✆ ✁ redmap✄ f ☎ ☎ redmap✄ g☎ ϕ✆ ✞ sum✄ f ☎ :: ☎ Num n✆ ✂✁ f n n sum✄ f ☎ ✁ reduce✄ f ☎ 0 ☎ ✂ ✆ and ✄ f ☎ :: f Bool Bool and ✄ f ☎ ✁ reduce✄ f ☎ True ☎ ✆ minimum✄ f ☎ :: ☎ Bounded a✞ Ord a✆ ✁ f a a minimum✄ f ☎ ✁ reduce✄ f ☎ maxBound min size ✄ f ☎ :: ☎ Num n✆ ✂✁ f a n size ✄ f ☎ ✁ reducemap✄ f ☎ 0 ☎ ✂ ✆ ☎ const 1✆ all✄ f ☎ :: ☎ a Bool✆ ☎ f a Bool✆ all✄ f ☎ p ✁ reducemap✄ f ☎ True ☎ ✆ p flatten✄ f ☎ :: f a List a flatten✄ f ☎ ✁ reducemap✄ f ☎ ✂✁ ☎ ✂ ✂ ✆
wrap where wrap a ✁ a ✁ Fig. 2: Examples of reductions.

which shows that we succeeded in eliminating the annoying call to map. Apart from improving the efficiency of reduce✄ f ☎ the synthesized function is also interesting in its own right since it captures a common pattern of recursion.

reduce✄ f ☎ e op ✁ reducemap✄ f ☎ e op id reducemap✄ f ☎ :: a ☎ ∆ a a✆ ☎ b a✆ ☎ f b a✆ reducemap✄ f ☎ e op ✁ redmap✄ f ☎ where redmap✄ Kt☎ ϕ ✁ const e redmap✄ Id☎ ϕ ✁ ϕ redmap✄ f ✂ g☎ ✁ redmap✄ f ☎ ϕ redmap✄ g☎ ϕ redmap✄ f ✄ g☎ ϕ ✁ op ✁ ☎ redmap✄ f ☎ ϕ ✄ redmap✄ g☎ ϕ✆ redmap✄ f g☎ ϕ ✁ redmap✄ f ☎ ☎ redmap✄ g☎ ϕ✆
Let us again specialize the definition to the type of perfect trees.

redmap✄ Perfect☎ ϕ ✁ ϕ redmap✄ Perfect☎ ☎ op ✁ ☎ ϕ ✄ ϕ✆ ✆
It is interesting if not revealing to contrast the two definitions of reductions on perfect trees. The first one, red ✄ Perfect☎ , essentially proceeds bottom-up. In each step the 'nodes' (ie pairs) on the lowest level are reduced. This step is repeated until the root is reached. By contrast, redmap✄ Perfect☎ operates in two stages: first a suitable reduction function is constructed, which then reduces the perfect tree in a single top-down pass. Clearly, the latter procedure is more efficient than the former. Fig. 2 lists some typical applications of reduce✄ f ☎ and reducemap✄ f ☎ . Further examples can be found, for instance, in [START_REF] Meertens | Calculate polytypically![END_REF] or [START_REF] Jansson | PolyLib-A library of polytypic functions[END_REF].

Polytypic reduction satisfies a fusion law analogous to the fusion law for folds [START_REF] Meertens | Calculate polytypically![END_REF].

h ✁ reducemap✄ f ☎ e op ϕ ✁ reducemap✄ f ☎ e ✁ op ✁ ϕ ✁ ✁ h ✁ ✝ ✁ ✞✝ h ✁ const e ✁ const e ✁ h ✁ op ✁ op ✁ ✁ ☎ h ✄ h✆ h ✁ ϕ ✁ ϕ ✁
The law can be shown using a straightforward fixpoint induction, which is left as an exercise to the reader. Instead we apply the fusion law to derive an efficient implementation of size ✄ Perfect☎ . A simple consequence of the fusion law is

reducemap✄ f ☎ 0 ☎ ✂ ✆ ☎ const n✆ ✁ mult n ✁ reducemap✄ f ☎ 0 ☎ ✂ ✆ ☎ const 1✆ where mult a b ✁ a ✁ b ✠ Now, we reason size ✄ Perfect☎ ✁ reducemap✄ Perfect☎ 0 ☎ ✂ ✆ ☎ const 1✆ ✁ const 1 reducemap✄ Perfect☎ 0 ☎ ✂ ✆ ☎ reducemap✄ ∆☎ 0 ☎ ✂ ✆ ☎ const 1✆ ✆ ✁ const 1 reducemap✄ Perfect☎ 0 ☎ ✂ ✆ ☎ const 2✆ ✁ const 1 mult 2 ✁ size ✄ Perfect☎ ✠
Defined this way size✄ Perfect☎ runs in Θ ☎ logn✆ time.

Extending the approach to n-ary functors

By now we have seen several examples of polyfunctorial functions, ie functions that are parametrised by an unary functor. In this section we extend the approach from unary to n-ary functors. It is relatively straightforward to extend functor expressions to the general case: An n-ary functor expression is a rational tree over the following set of 'functor' symbols.

F ✟ n ☛ ✁ KT ✂ P n i ☎ 1 ✂ i ✂ n✆ ✂ F ✟ n ☛ ✂ F ✟ n ☛ ✂ F ✟ n ☛ ✄ F ✟ n ☛ ✂ F ✟ k ☛ ☎ F ✟ n ☛ 1 ✞ ✠ ✠ ✠ ✞ F ✟ n ☛ k ✆ ☎ 1 ✂ k✆
The superscript in F ✟ n ☛ denotes the arity of the functor. As before, KT denotes the n-ary constant functor.

The n-ary projection functor P n i is given by

P n i ✄ T ✁ T i for ✄ T ✁ ☎ T 1 ✞ ✠ ✠ ✠ ✞ T n ✆ .
For n ✁ 1 and n ✁ 2 we use the following more familiar names:

Id ✁ P 1 1 , Fst ✁ P 2 1 , and
Snd ✁ P 2 2
The coproduct and product of n-ary functors are defined as usual:

☎ F 1 ✂ F 2 ✆ ✄ T ✁ F 1 ✄ T ✂ F 2 ✄ T and ☎ F 1 ✄ F 2 ✆ ✄ T ✁ F 1 ✄ T ✄ F 2 ✄ T . Finally, F ☎ G 1 ✞ ✠ ✠ ✠ ✞ G k ✆ denotes the composition of the k-ary functor F with k n-ary functors: ☎ F ☎ G 1 ✞ ✠ ✠ ✠ ✞ G k ✆ ✆ ✄ T ✁ F ☎ G 1 ✄ T ✞ ✠ ✠ ✠ ✞ G k ✄ T ✆ . We omit the parentheses when k ✁ 1, ie we write F F 1 instead of F ☎ F 1 ✆ .
From the definitions of KT, P n i , ☎ ✂ ✆ , ☎ ✄ ✆ , and ☎ ✆ we can easily derive the following laws.

KT ☎ F 1 ✞ ✠ ✠ ✠ ✞ F n ✆ ✁ KT P n i ☎ F 1 ✞ ✠ ✠ ✠ ✞ F n ✆ ✁ F i F ☎ P n 1 ✞ ✠ ✠ ✠ ✞ P n n ✆ ✁ F ☎ F 1 ✂ F 2 ✆ ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ✁ F 1 ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ✂ F 2 ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ☎ F 1 ✄ F 2 ✆ ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ✁ F 1 ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ✝✄ F 2 ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ☎ F ☎ G 1 ✞ ✠ ✠ ✠ ✞ G n ✆ ✆ ☎ H 1 ✞ ✠ ✠ ✠ ✞ H o ✆ ✁ F ☎ G 1 ☎ H 1 ✞ ✠ ✠ ✠ ✞ H o ✆ ✞ ✠ ✠ ✠ ✞ G m ☎ H 1 ✞ ✠ ✠ ✠ ✞ H o ✆ ✆
For n ✁ o ✁ 1 we obtain the laws given in Sec. 2.

Coproduct and product are the simplest examples of bifunctors.

Coproduct ✁ Fst ✂ Snd Product ✁ Fst ✄ It is easy to verify that Coproduct F 1 ✞ F 2 ✆ ✁ F 1 ✂ F 2 and Product ☎ F 1 ✞ F 2 ✆ ✁ F 1 ✄ F 2 ,
Branch ✁ Fst ✄ Snd ✄ Fst ST ✁ Fst ✂ Branch ☎ ST ✞ Snd✆ PST ✁ Fst ✂ PST ☎ Branch✞ Snd✆
External search trees come in two flavours: ST is the standard textbook type while PST is the type of perfect external search trees. Note that ST is right recursive whereas PST is left recursive. The classification of functors into polynomial, regular, and non-regular functors also carries over to the n-ary case. It is easy to see that Branch is a polynomial, ST a regular, and PST a non-regular bifunctor.

Polytypic and polyfunctorial functions

Our first (and our last) example of a polytypic function that is indexed by a nullary functor is polytypic equality. Besides implementing a fundamental operation the example also demonstrates the interaction between polytypic and polyfunctorial functions. Note that the definition of equality is based upon the approach taken in PolyLib [START_REF] Jansson | PolyLib-A library of polytypic functions[END_REF]. In PolyLib, however, equality is parametrised by an unary functor. Now, to be able to give the definitions in a point-free style, we make use of the auxiliary functions shown in Fig. 3. The first cases of eq✄ t☎ are straightforward. We assume that the primitive types are 1, Int, and Double and that suitable equality functions for Int and Double are predefined.

eq✄ t☎ It remains to define eq✄ t☎ for the case that t is a composition of a k-ary functor with k nullary functors. To keep the example manageable we confine ourselves to unary functors. How do we proceed if t takes the form f u? Now, two elements of f u are equal if they have the same shape and the elements of type u at corresponding positions are equal. To bring corresponding elements together we make use of an auxiliary, polyfunctorial function called zip✄ f ☎ . As the name indicates, zip✄ f ☎ ::

:: t ✄ t Bool eq✄ K1☎ ✁ const True eq✄ KInt☎ ✁ eqint eq✄ KDouble☎ ✁ eqdouble eq✄ t 1 ✂ t 2 ☎ ✁ ok ☎ eq✄ t 1 ☎ eq✄ t 2 ☎ ✆ ✁ couple eq✄ t 1 ✄ t 2 ☎ ✁ ☎ ✆ ✁ ☎ eq✄ t 1 ☎ ✟✄ eq✄ t 2 ☎ ✆ ✏✁ transpose ☎ p f ✞ g✆ a ✁ if p a then f a else g a couple ☎ inl a 1 ✞ inl b 1 ✆ ✁ Just ☎ inl ☎ a 1 ✞ b 1 ✆ ✆ couple ☎ inl a 1 ✞ inr b 2 ✆ ✁ Nothing couple ☎ inr a 2 ✞ inl b 1 ✆ ✁ Nothing couple ☎ inr a 2 ✞ inr b 2 ✆ ✁ Just ☎ inr ☎ a 2 ✞ b 2 ✆ ✆ transpose ☎ ☎ a 1 ✞ a 2 ✆ ✞ ☎ b 1 ✞ b 2 ✆ ✆ ✁ ☎ ☎ a 1 ✞ b 1 ✆ ✞ ☎ a 2 ✞ b 2 ✆ ✆ ok ϕ Nothing ✁ False ok ϕ ☎ Just a✆ ✁ ϕ a
☎ f a✞ f b✆ Maybe ☎ f ☎
a✞ b✆ ✆ turns a pair of structures into a structure of pairs. If the structures have not the same shape, zip✄ f ☎ returns Nothing, otherwise it yields Just z where z is the desired structure. Using zip✄ f ☎ the last case of eq✄ t☎ can be defined as

eq✄ f u☎ ✁ ok ☎ all✄ f ☎ ☎ eq✄ u☎ ✆ ✆ ✁ zip✄ f ☎ ✞
which is more or less a translation of the english description above. The auxiliary function zip✄ f ☎ makes a nice example of polytypic, monadic programming. Before we discuss its definition let us briefly review the basics of monads. For a more in-depth treatment we refer the interested reader to P. Wadler's papers [START_REF] Wadler | Comprehending monads[END_REF][START_REF] Wadler | The essence of functional programming[END_REF][START_REF] Wadler | Monads for functional programming[END_REF], which also contain supplementary pointers to relevant work. One can think of a monad as an abstract type for computations. In The essential idea of monads is to distinguish between computations and values. This distinction is reflected on the type level: an element of m a represents a computation that yields a value of type a. A computation may involve, for instance, state, exceptions, or nondeterminism. The trivial computation that immediately returns the value a is denoted by return a. The operator

☎ ✁ ✁ ✆ commonly called 'bind', combines two computations: m ✁ ✁ k applies k to the result of the computation m.
The monadic operations must be related by the following so-called monad laws.

return a ✂ ✁ k ✁ k a (9) m ✂ ✁ return ✁ m ( 10
) ☎ m ✁ ✁ k✆ ✂ ✁ ☎✄ ✁ m ✁ ✁ ☎ λa k a ✁ ✁ ☎✄ ✆ (11)
Roughly speaking return is the neutral element of

☎ ✂ ✁ ✆ and ☎ ✁ ✁ ✆
is associative. The monoidal structure becomes more apparent if the laws are rephrased in terms of the monadic composition, see below.

Haskell supports monadic programming by providing a more readable, first-order syntax for

☎ ✁ ✁ ✆
, the so-called do-notation. The syntax and semantics of do-expressions are given by the following identities:

do ✜ x m; e ✢ ✁ m ✁ ✁ λx do ✜ e ✢ do ✜ e ✢ ✁ e ✠
Several datatypes have a computational content. For instance, the type Maybe can be used to model exceptions: Just x represents a 'normal' or successful computation yielding the value x while Nothing represents an exceptional or failing computation-zip✄ ☎ employs Maybe in this sense. The following instance declaration shows to define return

☎ ✁ ✁ ✆
for Maybe.

instance Monad Maybe where return

✁ Just Nothing ✁ ✁ k ✁ Nothing Just a ✂ ✁ k ✁ k a Thus, m ✂ ✁
k can be seen as a strict postfix application: if m is an exception, the exception is propagated; if m succeeds, then k is applied to the resulting value.

In the previous examples we have made heavy use of general combining forms such as

☎ ✁ ✆ , ☎ ✂ ✆
, and

☎ ✄ ✆
. The function zip✄ f ☎ can be defined quite succinctly if we raise these combinators to procedures. A procedure is by definition a function that maps values to computations, ie it is a function of type a m b where m is a monad.

☎ h 1 ✁ h 2 ✆ a ✁ do ✜ b h 2 a; h 1 b ✢ ☎ h 1 ✂ h 2 ✆ ☎ a 1 ✞ a 2 ✆ ✁ do ✜ b 1 h 1 a 1 ; b 2 h 2 a 2 ; return ☎ b 1 ✞ b 2 ✆ ✢ ☎ h 1 ✄ h 2 ✆ ☎ inl a 1 ✆ ✁ do ✜ b 1 h 1 a 1 ; return ☎ inl b 1 ✆ ✢ ☎ h 1 ✄ h 2 ✆ ☎ inr a 2 ✆ ✁ do ✜ b 2 h 2 a 2 ; return ☎ inr b 2 ✆ ✢
While the definitions for ☎ ✁ ✆ and ☎ ✄ ✆ are inevitable, there is a choice to be made in the case of ☎ ✂ ✆ . The two computations h 1 a 1 and h 2 a 2 can be sequenced in two possible ways, either h 1 a 1 before h 2 a 2 or vice versa. Fortunately, the two definitions coincide for m ✁ Maybe. ¶ From the definitions above we can easily derive the following equations:

f ✁ ☎ g ✁ h✆ ✁ ☎ f ✁ g✆ ✁ h (12) f ✁ return ✁ f (13) return ✁ f ✁ f (14) f ✁ ☎ g ✁ h✆ ✁ ☎ f ✁ g✆ ✁ h (15) ☎ f 1 ✄ f 2 ✆ ✁ ☎ g 1 ✄ g 2 ✆ ✁ ☎ f 1 ✁ g 1 ✆ ✄ ☎ f 2 ✁ g 2 ✆ (16) ☎ f 1 ✂ f 2 ✆ ✁ ☎ g 1 ✂ g 2 ✆ ✁ ☎ f 1 ✁ g 1 ✆ ✂ ☎ f 2 ✁ g 2 ✆ if m is commutative (17)
¶ We tacitly assume that computations do not diverge. Otherwise this property does not hold, take, for instance, h 1 a 1 ☎ Nothing and h 2 a 2 ☎ ✝✆ .

Note that equations ( 13), [START_REF] Malcolm | Data structures and program transformation[END_REF], and (15) are the monad laws stated in terms of the monadic composition ☎ ✁ ✆ . These equations furthermore show that procedures (for a fixed m) form the morphisms of a category, the so-called Kleisli category, where the identity is return and the composition is ☎ ✁ ✆ . The last equation only holds for so-called commutative monads that satisfy

do ✜ a 1 m 1 ; a 2 m 2 ; return ☎ a 1 ✞ a 2 ✆ ✢ ✁ do ✜ a 2 m 2 ; a 1 m 1 ; return ☎ a 1 ✞ a 2 ✆ ✢ ✠
For instance, the identity monad, the Maybe monad, and reader monads all have this property. On the other hand, the list monad, the state monads, and the IO monad are not commutative. This implies that

☎ ✄ ✆
is not a bifunctor in the corresponding Kleisli category. Now for the definition of zip✄ t☎ . The first case falls back on the equality of values. Thus, eq✄ t☎ and zip✄ f ☎ are mutually recursive functions, which is not surprising since F ✟ 0 ☛ and F ✟ 1 ☛ are mutually recursive as well (we tacitly identify nullary functors, F ✟ 0 ☛ , and types, T).

zip✄ f ☎ :: f a ✄ f b Maybe ☎ f ☎ a ✄ b✆ ✆ zip✄ Kt☎ ✁ ☎ eq✄ t☎ return ✁ outl✞ const Nothing✆ zip✄ Id☎ ✁ return zip✄ f ✂ g☎ ✁ ☎ zip✄ f ☎ ✄ zip✄ g☎ ✆ ✁ couple zip✄ f ✄ g☎ ✁ ☎ zip✄ f ☎ ✂ zip✄ g☎ ✆ ✏✁ transpose zip✄ f g☎ ✁ mapM ✄ f ☎ ☎ zip✄ g☎ ✆ ✁ zip✄ f ☎
The last case is again the most interesting one. To zip two values of type f ☎ g a✆ and f ☎ g b✆ we first apply zip✄ f ☎ , which yields a value of type Maybe ☎ f ☎ g a ✄ g b✆ ✆ . To obtain a value of the desired type, Maybe ☎ f ☎ g ☎ a ✄ b✆ ✆ ✆ , we then map zip✄ g☎ on f . However, since we are working within a monad we cannot use the 'ordinary' map operation as defined in Sec. 3. Instead we must employ a monadic map [START_REF] Fokkinga | Monadic maps and folds for arbitrary datatypes[END_REF], which is defined as follows (note that mapM ✄ f ☎ is termed mapl in [18]). mapM ✄ f ☎ ::

☎ Monad m✆ ✂✁ ☎ a m b✆ ☎ f a m ☎ f b✆ ✆ mapM ✄ Kt☎ ϕ ✁ return mapM ✄ Id☎ ϕ ✁ ϕ mapM ✄ f ✂ g☎ ϕ ✁ mapM ✄ f ☎ ϕ ✄ mapM✄ g☎ ϕ mapM ✄ f ✄ g☎ ϕ ✁ mapM ✄ f ☎ ϕ ✂ mapM✄ g☎ ϕ mapM ✄ f g☎ ϕ ✁ mapM ✄ f ☎ ☎ mapM ✄ g☎ ϕ✆
Abstractly speaking, mapM ✄ f ☎ defines the action on arrows in the Kleisli category induced by m. If we specialize m to Id, the identity monad, we obtain the 'ordinary' map operation. Since mapM ✄ f ☎ is the morphism part of a functor, it satisfies the following two functorial laws.

mapM ✄ f ☎ return ✁ return mapM ✄ f ☎ ☎ ϕ ✁ ψ✆ ✁ mapM ✄ f ☎ ϕ ✁ mapM✄ f ☎ ψ if m is commutative
Since the proof of the last law employs equation [START_REF] Meijer | Bananas in space: Extending fold and unfold to exponential types[END_REF], it is restricted to commutative monads, as well. The monadic map is surprisingly versatile. It may be used, for example, to thread a monad through a structure, see [START_REF] Jansson | PolyLib-A library of polytypic functions[END_REF].

thread ✄ f ☎ :: ☎ Monad m✆ ✂✁ f ☎ m a✆ m ☎ f a✆ thread ✄ f ☎ ✁ mapM ✄ f ☎ id
What about the running time of zip✄ f ☎ ? From the last equation of zip✄ f ☎ we are lead to suspect that zip✄ f ☎ suffers from the same problems as reduce✄ f ☎ . And this indeed is the case. Consider the specialization of zip✄ f ☎ to Tower (note that zip✄ Maybe☎ ✁ couple). zip✄ Tower☎ ✁ ☎

return ✄ mapM ✄ Tower☎ couple ✁ zip✄ Tower☎ ✆ ✁ couple
It is not hard to see that zipping

☎ Recurse n ☎ End ☎ Just n a✆ ✆ ✞ Recurse n ☎ End ☎ Just n b✆ ✆ ✆ takes Θ ☎ n 2 ✆ time.
However, we can easily improve the efficiency by combining a monadic map with a zip.

zipWith✄ f ☎ ϕ ✁ mapM ✄ f ☎ ϕ ✁ zip✄ f ☎ zip✄ f ☎ ✁ zipWith✄ f ☎ return
The derivation of zipWith✄ f ☎ is again a simple exercise in program calculation. It pays off that we have defined zip✄ f ☎ in terms of the admittedly abstract operators on procedures.

zipWith✄ Kt☎ ϕ ✁ mapM ✄ Kt☎ ϕ ✁ zip✄ Kt☎ ✟✁ return ✁ zip✄ Kt☎ ✝✁ zip✄ Kt☎ zipWith✄ Id☎ ϕ ✁ mapM ✄ Id☎ ϕ ✁ zip✄ Id☎ ✟✁ ϕ ✁ return ✁ ϕ zipWith✄ f ✂ g☎ ϕ ✁ mapM ✄ f ✂ g☎ ϕ ✁ zip✄ f ✂ g☎ ✁ ☎ mapM ✄ f ☎ ϕ ✄ mapM ✄ g☎ ϕ✆ ✁ ☎ zip✄ f ☎ ✄ zip✄ g☎ ✆ ✁ couple ✁ ☎ mapM ✄ f ☎ ϕ ✁ zip✄ f ☎ ✄ mapM✄ g☎ ϕ ✁ zip✄ g☎ ✆ ✁ couple ✁ ☎ zipWith ✄ f ☎ ϕ ✄ zipWith✄ g☎ ϕ✆ ✁ couple
The derivation for products and compositions relies on the commutativity of Maybe.

zipWith✄ f ✄ g☎ ϕ ✁ mapM ✄ f ✄ g☎ ϕ ✁ zip✄ f ✄ g☎ ✁ ☎ mapM ✄ f ☎ ϕ ✂ mapM✄ g☎ ϕ✆ ✁ ☎ zip✄ f ☎ ✂ zip✄ g☎ ✆ ✏✁ transpose ☎ mapM ✄ f ☎ ϕ ✁ zip✄ f ☎ ✂ mapM ✄ g☎ ϕ ✁ zip✄ g☎ ✆ ✁ transpose ☎ zipWith✄ f ☎ ϕ ✂ zipWith✄ g☎ ϕ✆ ✁ transpose zipWith✄ f g☎ ϕ ✁ mapM ✄ f g☎ ϕ ✁ zip✄ f g☎ ✁ mapM ✄ f ☎ ☎ mapM ✄ g☎ ϕ✆ ✁ mapM ✄ f ☎ ☎ zip✄ g☎ ✆ ✁ zip✄ f ☎ ✁ mapM ✄ f ☎ ☎ mapM ✄ g☎ ϕ ✁ zip✄ g☎ ✆ ✁ zip✄ f ☎ ✁ zipWith✄ f ☎ ☎ zipWith✄ g☎ ϕ✆
Putting things together we obtain

zip✄ f ☎ ✁ zipWith ✄ f ☎ return zipWith ✄ f ☎ :: ☎ a ✄ b Maybe c✆ ☎ f a ✄ f b Maybe ☎ f c✆ ✆ zipWith ✄ Kt☎ ϕ ✁ ☎ eq✄ t☎ return ✁ outl✞ const Nothing✆ zipWith ✄ Id☎ ϕ ✁ ϕ zipWith ✄ f ✂ g☎ ϕ ✁ ☎ zipWith ✄ f ☎ ϕ ✄ zipWith✄ g☎ ϕ✆ ✁ couple zipWith ✄ f ✄ g☎ ϕ ✁ ☎ zipWith ✄ f ☎ ϕ ✂ zipWith✄ g☎ ϕ✆ ✏✁ transpose zipWith ✄ f g☎ ϕ ✁ zipWith ✄ f ☎ ☎ zipWith✄ g☎ ϕ✆ ✠
Interestingly, the two definitions of zip✄ f ☎ are equivalent for arbitrary monads, not just for Maybe. To see why this is the case note that zip✄ f ☎ and zipWith✄ f ☎ are related by zip✄ f g☎ ✁ zipWith✄ f ☎ ☎ zip✄ g☎ ✆ ✠ Setting g ✁ Id yields the desired result.

Polybifunctorial functions

The definition of polybifunctorial functions contains little surprise. The main difference to polyfunctorial functions is that we must consider two projection functors, Fst and Snd, instead of one. Here is the definition of bimap✄ f ☎ , which describes the action of a bifunctor on arrows. bimap✄ f ☎ ::

☎ a 1 b 1 ✆ ☎ a 2 b 2 ✆ ☎ f a 1 a 2 f b 1 b 2 ✆ bimap✄ Kt☎ ϕ 1 ϕ 2 ✁ id bimap✄ Fst☎ ϕ 1 ϕ 2 ✁ ϕ 1 bimap✄ Snd☎ ϕ 1 ϕ 2 ✁ ϕ 2 bimap✄ f ✂ g☎ ϕ 1 ϕ 2 ✁ bimap✄ f ☎ ϕ 1 ϕ 2 ✂ bimap✄ g☎ ϕ 1 ϕ 2 bimap✄ f ✄ g☎ ϕ 1 ϕ 2 ✁ bimap✄ f ☎ ϕ 1 ϕ 2 ✄ bimap✄ g☎ ϕ 1 ϕ 2 bimap✄ f g☎ ϕ 1 ϕ 2 ✁ map✄ f ☎ ☎ bimap✄ g☎ ϕ 1 ϕ 2 ✆ bimap✄ f ☎ g 1 ✞ g 2 ✆ ☎ ϕ 1 ϕ 2 ✁ bimap✄ f ☎ ☎ bimap✄ 1 ☎ ϕ 1 ϕ 2 ✆ ☎ bimap✄ g 2 ☎ ϕ 1 ϕ 2 ✆
Note the interplay of map✄ f ☎ and bimap✄ f ☎ . For reasons of symmetry the following equation should be added to the definition of map✄ f ☎ .

map✄ f ☎ g 1 ✞ g 2 ✆ ☎ ϕ ✁ bimap✄ f ☎ ☎ map✄ g 1 ☎ ϕ✆ ☎ map✄ g 2 ☎ ϕ✆
The example of map✄ f ☎ illustrates a problem inherent with all polytypic definitions. If an unary functor, say, f is defined in terms of a ternary functor, then map✄ f ☎ is undefined. The reason is simply that the relevant case f

☎ g 1 ✞ g 2 ✞ g 3 ✆ is missing in map✄ f ☎ 's definition. Moreover, since f ☎ g 1 ✞ ✠ ✠ ✠ ✞ g k ✆ is an element of F ✟ n ☛ for all k 1,
we cannot define map✄ f ☎ exhaustively. Clearly, further research is required here. The generalization of polytypic reductions to binary functors is left as an exercise to the reader. Note that, in general, a reduction is a function of type f a ✠ ✠ ✠ a a.

Related and future work

The impetus for writing this article came while reading the article "Nested Datatypes" by R. Bird and L. Meertens [START_REF] Bird | Nested datatypes[END_REF]. The authors state that "It is possible to define reductions completely generically for all regular types [. . . ], but we do not know at present whether the same can be done for nested datatypes." We have shown that the answer to this question is in the affirmative. Moreover, the solution presented is surprisingly simple. To define a polytypic function it suffices to specify its action on polynomial functors. The extension to (mutually) recursive datatypes-which is uniquely defined-is then handled automatically by the system. This does not only simplify matters for the generic programmer, it also removes some of the redundancy present in the classical approach. In the polytypic programming language PolyP [START_REF] Jansson | PolyP-a polytypic programming language extension[END_REF], for instance, the user must supply definitions for both polynomial and type functors. There is, however, no guarantee that the corresponding functions behave in related ways.

Very recently, R. Bird and R. Paterson [4] introduced so-called generalised folds, which overcome some of the problems mentioned in the introduction to this article. Generalised folds, which can be constructed systematically for each first-order polymorphic datatype, possess a uniqueness property analogous to that of ordinary folds. Their work is largely complementary to ours. While generalised folds are more general than the reductions defined in Sec. 4, it is not clear how to define functions like sum generically using generalised folds.

An obvious disadvantage of our approach is that it is not possible to define general recursion schemes like cata-and anamorphisms (ie folds and unfolds) [16]. The reason is simply that type recursion is left implicit rather than made explicit. The situation can be saved, however, by introducing an operation on functors that maps a type functor to its base functor. Inventing a notation we define F Ironically, hylomorphisms can be defined without any additions since their type does not involve type functors. hylo✄ f ☎ ::

☎ f a a✆ ☎ b f b✆ ☎ b a✆ hylo✄ f ☎ ϕ ψ ✁ ϕ ✁ map✄ f ☎ ☎ hylo✄ f ☎ ϕ ψ✆ ✁ ψ
Polytypic functions are values that depend on types. For that reason they cannot be expressed in languages such as Haskell or Standard ML. The question naturally arises as to whether polytypic definitions can be easily added to languages that incorporate dependent types such as Cayenne [START_REF] Augustsson | Cayenne -a language with dependent types[END_REF]. Now, since polytypic functions perform pattern matching on types, this would entail the addition of a typecase [START_REF] Abadi | Dynamic typing in polymorphic languages[END_REF]. A typecase was, however, left out of Cayenne by design and the consequences of adding such a construct to the language are unclear (personal communication with L. Augustsson). The transformational approach taken here-to specialize a polytypic function for each given instance-appears to be simpler and also more efficient since the repeated matching of the type argument (which is statically known at compile time) is avoided.

Directions for future work suggest themselves. It remains to broaden the approach to include exponentials and higher-order polymorphism [START_REF] Mark | Functional programming with overloading and higher-order polymorphism[END_REF]. The former extension should be fairly straightforward, see [START_REF] Sheard | A fold for all seasons[END_REF] or [START_REF] Meijer | Bananas in space: Extending fold and unfold to exponential types[END_REF]. The latter extension is far more challenging. To illustrate, consider the following generalization of rose trees.

data GRose f a ✁ Node a

☎ f ☎ GRose f a✆ ✆
This datatype is used, for instance, to extend an implementation of collections (sequences or priority queues) with an efficient operation for combining two collections (catenate or meld), see [START_REF] Okasaki | Purely Functional Data Structures[END_REF]. From a categorical point of view we could interpret GRose as a higher-order functor of type Fun a✠ GRose f a GRose g a✆ Unfortunately, this is a rank-2 type, which is not legal Haskell. An alternative view is to interpret GRose as a higher-order functor of type Cat The first operates on the base collection f of the 'bootstrapped' collection GRose f the second operates on the elements contained in a collection. However, it is far from clear how to define these maps generically for all higher-order datatypes.

Fig. 1 Fig. 1 :

 11 Fig. 1: Types interpreted as rational trees.

  which shows that we could have added ☎ ✂ ✆ and ☎ ✄ ✆ as constants to F ✟ 2 ☛ . The infix notation is, however, more convenient to use. External search trees make nice examples of bifunctors. An external search tree of type ST a b has external nodes (ie leafs) labelled with values of type a and internal nodes (ie branches) labelled with values of type b.

Fig. 3 :

 3 Fig. 3: Auxiliary functions for polytypic equality.

  Haskell monads are captured by the following class declaration. class Monad m where return :: a m a

☎

  C✆ is the category that has as objects functors of type C C and as arrows natural transformations between them. Equating natural transformations and polymorphic functions it follows that GRose's map functional has the type ☎ ✁ a✠ f a g a✆ ☎ ✁

☎☎

  C✆ is category that has as the only object the category C and as arrows functors of type C C. This suggests to define a higher-order map of type GRose f a GRose f b✆ ✆ . Both maps are clearly useful:

  Now, elements of type Tower are either of the form Recurse n ☎ Just m Nothing✆ ✆ with m n or of the form Recurse n ☎

	End

End

☎

  corresponds to the type constructor FunctorOf used in PolyP). Of course, F ✁ is only defined if F is a regular functor. Given two functions in :: t

							✁
							✁	B for F ✁ µB
	(the operation
							✁	✁
							t t and out :: t t	t we can now define
		✁
		☎					☎
	cata✄ t☎ cata✄ t☎ ϕ ✁ ::	t ϕ ✁ map✄ t a a✆	✁	☎	☎	t a✆ cata✄ t☎ ϕ✆ ✁ out
		✁
		☎					☎
	ana✄ t☎ ana✄ t☎ ψ ✁ ::	a t in ✁ map✄ t a✆	✁	☎	☎	a t✆ ana✄ t☎ ψ✆ ✁ ψ ✠

☎

-✆ ✁

Acknowledgements

Thanks are due to Richard Bird for his helpful comments on an earlier draft of this article. I am also grateful to Philip Wadler and two anonymous referees for suggesting numerous improvements regarding contents and presentation.


Ross M Mcconnell

Jeremy P Spinrad

Ordered Vertex Partitioning †

Keywords: Modular Decomposition, Substitution Decomposition, Transitive Orientation

A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple O n ✁ mlogn✂ algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not Ω n 2 ✂ . The best known time bounds for the problems are O n ✁ m✂ , but they involve sophisticated techniques.

Motivation

Computing the modular decomposition of an undirected graph and a transitive orientation, when one exists, are problems that come up in a large number of combinatorial problems on perfect graphs and other graph classes. In this paper, we show how both problems reduce quite easily to a procedure called vertex partitioning. The resulting algorithm has an O✄ n ☎ m log n✆ time bound, where n is the number of vertices, and m is the number of edges. Vertex partitioning is the only obstacle to a linear time bound. If no transitive orientation exists, the result still gives the modular decomposition. Neither of these results is optimal, since these problems can be solved in linear time [START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF], but the linear-time algorithms are quite involved and challenging to understand.

A reduction of modular decomposition and transitive orientation to vertex partitioning was first given in an unpublished work that was circulated in 1985 [START_REF] Spinrad | Graph partitioning[END_REF]. The simplified reduction we give here is a combination of ideas from that paper, and from [START_REF] Ehrenfeucht | An O(n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs[END_REF]. It was circulated as an unpublished result in 1994. The linear time bound of transitive orientation of [START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF] was an outgrowth of it. Other subsequent papers have adopted its approach [START_REF] Habib | Transitive orientation, interval graph recognition, and consecutive ones testing[END_REF][START_REF] Habib | Partition refining techniques[END_REF]. In the final section, we discuss its somewhat weaker role of the approach in the parallel and sequential algorithms of [START_REF] Dahlhaus | Efficient parallel modular decomposition. 21 st Int[END_REF][START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF]. Because it is not the main focus of any of these papers, the simplicity of the basic approach has not been explained publicly. As we explain below, we believe that the underlying insights still hold promise for future progress in the area.

Fig. 1: A graph and its modules. A module is a set X of vertices such that for each y V G✂ ✂✁ X, either y is adjacent to every element of X, or y is nonadjacent to every element of X.

Introduction

We view an undirected graph as a special case of a directed graph, where each undirected edge ✄ x✄ y✆ is composed of two directed arcs ✄ x✄ y✆ and ✄ y✄ x✆ . A digraph is transitive if, removal of exactly one of ✄ x✄ y✆ or ✄ y✄ x✆ for each undirected edge ✄ x✄ y✆ . A transitive orientation is one where the resulting digraph is transitive. Comparability graphs are the class of graphs that have a transitive orientation.

A module of G is a set X of nodes such that for any node x not in X, either x is adjacent to every node of X, or x is nonadjacent to every node of X. V ✄ G✆ and its singleton subsets are the trivial modules. All graphs have the trivial modules; a graph is prime if it has no nontrivial modules. Figure 1 depicts a graph and its modules. The following is easily verified: Theorem 2. [START_REF] Cormen | Algorithms[END_REF] If X and Y are disjoint modules of a graph, then either every element of X is adjacent to every element of Y , or no element of X is adjacent to any element of Y .

Thus, any pair of disjoint modules can be classified as "adjacent" or as "nonadjacent." It follows that if P is a partition of the nodes of G such that each member of P is a module, the adjacency relationships of the members of P to each other is itself described by a graph, as shown in Figure 2. This graph is called the quotient G ☎ P , and P is called a congruence partition. Note that if X is a set obtained by selecting one representative node from each member of P , then G ✆ X is isomorphic to G ☎ P . Theorems about quotients can be applied to induced subgraphs of this type, a fact that we will occasionally use in our proofs.

The quotient G ☎ P completely specifies those edges of the graph that are not in any subgraph G✆ X induced by any X ✝ P . Thus, the quotient, together with the subgraphs induced by the members of P , gives a complete representation of the original graph.

The modular decomposition is a way to represent compactly all modules of a graph. Two modules X and Y overlap if they intersect, but neither contains the other. A strong module is a module that overlaps no other. The decomposition is a rooted tree. The nodes of this tree are the strong modules of the graph, and the transitive reduction of the containment relation on the strong modules gives the edges of the tree. By MD✄ G✆ , we denote the modular decomposition of G.

An equivalent definition of the modular decomposition is the following recursive one. Note that at least one of G and its complement is connected. is an edge or none is. Thus, X and Y may be viewed as adjacent or nonadjacent. If P is a partition of the vertices a graph into modules, the adjacencies of members of P can be described by a quotient graph G☎ P . The quotient graph and the subgraphs induced by members of P completely specify G.

1. (parallel case) If G is disconnected, its connected components are a congruence partition, every union of components is a module, and no module overlaps a component. Thus, the modules of G can be divided into two sets: those that are a union of components and those that are a subset of a single component. Those that are a subset of a component C can be found by recursion on G✆ C.

(series case)

If the complement of G is disconnected, apply step 1 to the complement.

3. (prime case) Otherwise, let the highest submodules be those modules that are not contained in any other module except V ✄ G✆ . When both G and its complement are connected, the highest submodules are a congruence partition. The modules of G are V ✄ G✆ and those modules that are subsets of highest modules. Those that are a subset of a highest submodule M may be found by recursion on G ✆ M.

At each step of the recursion, this algorithm finds a congruence partition. The recursion tree, together with the quotients induced by these congruence partitions, uniquely specify G. Figure 3 gives an example.

If X is a node of the tree and Y is its children, the child quotient is ✄ G✆ X ✆ ☎ Y . The name of the prime case of the modular decomposition is derived from the fact that if X is a prime node then its child quotient is prime.

The number of modules of a graph may be exponential, as in the case of a complete graph. However, it is easy to see from Theorem 3.1, below, that a set of vertices is a module of G if and only if it is a node of the decomposition tree or a union of children of a series or parallel node. Thus, the modular decomposition gives an implicit representation of the modules of G.

A directed graph is transitive if, whenever ✄ a✄ b✆ and ✄ b✄ c✆ are arcs, ✄ a✄ c✆ is also an arc. An orientation of an undirected graph is a directed graph obtained by assigning a direction to each undirected edge. A graph is a comparability graph if there exists an orientation that is transitive. A transitive orientation can be found in O✄ n ☎ m✆ time [START_REF] Mcconnell | Linear-time transitive orientation[END_REF], but this algorithm is difficult to understand. Cographs, and the complements of interval graphs are examples of comparability graphs. The fastest algorithm for recognizing permutation graphs takes advantage of the fact that a graph is a permutation graph if and only if it both the graph and its complement are comparability graphs. [START_REF] Mcconnell | Linear-time transitive orientation[END_REF].

Strategy of the algorithm

It has long been recognized that there is a type of duality between the modules of a comparability graph and its transitive orientations [START_REF] Gallai | Transitiv orientierbare graphen[END_REF]. In particular, the orientation of one edge in a transitive orientation dictates the orientation of another if and only if no module contains the endnodes of one of the two edges, but not of the other. Most approaches to transitive orientation compute the modular decomposition first. On the other hand, the modular decomposition can be constructed easily if it is known which edges force orientations of each other. The approach of our algorithm is to solve these dual problems concurrently.

The following two theorems, which are widely known, are fundamental [START_REF] Möhring | Algorithmic aspects of comparability graphs and interval graphs[END_REF]: Theorem 3.1 If X is a module of G, then the modules of G that are subsets of X are the modules of G✆ X.

Theorem 3.2 If P is a congruence partition on G, then X is a module of G ☎ P if and only if X is a module of G.
Let G be an undirected graph and let v be a vertex. A maximal module of G that does not contain v is a module X such that X does not contain v, but for every module Y such that X is a proper subset of Y , Y contains v. Let P ✄ G✄ v✆ be ✁ v✂ and the maximal modules of G that do not contain v. {a,b} {i,j,k,l} {i,j,k}

(1) {a,b,c} (0) (0) (1)
(1) {g,h}

V(R) (0)
G ✆ Y is disconnected if and only if G ✆ Z is. Thus, Y is a parallel (series) node if and only if Z is.
In this case, we say that Y is superfluous, since it is not needed to represent the modules of G. Adding superfluous nodes incrementally yields a tree with multiple superfluous nodes; this tree gives a type of modular decomposition, but it is not in reduced form. We will call such a tree an unreduced modular decomposition if it is not necessarily in reduced form. It has all the nodes of the modular decomposition, in addition to a (possibly empty) set of superfluous nodes. Given an unreduced decomposition, it is trivial to derive the reduced modular decomposition, by deleting series (parallel) nodes that are children of series (parallel) nodes in postorder. Thus, in the remainder of the paper, we consider only the problem of how to produce an unreduced decomposition.

Let P be a congruence partition. Let T ✁ be a modular decomposition of G ☎ P that is not necessarily in reduced form, and let T X denote a modular decomposition of G✆ X for X ✝ P that is not necessarily in reduced form. Each X ✝ P is a leaf of T ✁ . T ✁ gives all modules of G that are unions of members of P , while each T X gives the modules of G that are contained in a member of P . We can obtain a single tree that has all of this information by performing the composition of this trees. This is obtained by visiting each leaf ✁ X ✂ of T ✁ and attaching T X as a subtree. To be precise, the composition of T ✁ and ✁ T X :

X ✝ P ✂ is given by ✁ Y : Y ✝ T ✁ ✂ ✄✂ ✁ T X : X ✝ P ✂ .

Lemma 3.4 Let P be a congruence partition on an arbitrary graph G, let T

✁ be an unreduced modular decomposition of G ☎ P , and let T X be an unreduced modular decomposition of G✆ X for X ✝ P . Then the composition of T ✁ and ✁ T X : X ✝ P ✂ is an unreduced modular decomposition of G.

Proof: If M is a strong module, then it overlaps no member of P , by definition. Thus, M is either contained in a member of P or is a union of members of P . If it is contained in a member X of P , then it is a strong module of G✆ X, by Theorem 3.1, so it appears as a node of T X , hence as a node of the composition. If M is a union of a set M ☎ P , then M is a strong module of G ☎ P , by Theorem 3.2, and appears as a node of T ✁ . It follows that M appears as a node of the composition. Thus, every strong module of G is a node of the composition, from which the result follows.

Our strategy, which is summarized by Algorithm 1, is to find an unreduced decomposition of G ☎ P ✄ G✄ v✆ , find an unreduced decomposition of G ✆ X for each X ✝ P ✄ G✄ v✆ , and return the composition of these trees.

The vertices may be numbered arbitrarily with distinct integers.

Algorithm 1: UMD(G) Strategy for computing modular decomposition.

Let v be the lowest-numbered vertex of G; if G has only one vertex then return ✁ ✁ v✂ ✂ ; else Let T ✁ be the modular decomposition of

G ☎ P ✄ G✄ v✆ ; foreach member Y of P ✄ G✄ v✆ do T Y : UMD✄ G✆ Y ✆ ; return the composition of T ✁ and ✁ T Y : Y ✝ P ✄ G✄ v✆ ✂ .
The correctness is immediate from Lemma 3.4. This high-level strategy was employed by the algorithm of [START_REF] Ehrenfeucht | An O(n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs[END_REF]. However that algorithm had an O✄ n 2 ✆ bound, and for some time it was not clear how to improve the bound.

Data structures

We represent a linear order on a set V by labeling the elements of V with unique integer keys, which need not be consecutive. Sorting V in ascending order of these labels gives the represented order. The restriction of π to X ☎ V , denoted π ✆ X, is just a sort of X in ascending order of these labels.

Let a module tree be any set of modules where the transitive reduction of the containment relation is a tree, and where the root is V and the leaves are its singleton subsets. The canonical modular decomposition is one example among many. The module tree is ordered if there is a left-to-right order on the children of each internal node. If X ☎ V ✄ G✆ , let the restriction of a module tree T to X, denoted T ✆ X, have as its nodes the set ✁ Y ✁ X : Y is a node of T ✂ . The transitive reduction of the containment relation gives the parent relation. If T is an ordered module tree, then the restriction to X, is also ordered; this is done in the unique way that its leaves ✁ ✁ x✂ : x ✝ X ✂ have the same relative order that they do in T . This is always possible, since any node of T is a set that is consecutive on the leaf order of T , hence any node of T ✆ X is also consecutive in its leaf order.

To implement a module tree, we let an O✄ 1✆ -size node stand for each node. This node carries a doublylinked list of pointers to its children. If the node is a leaf, it carries a pointer to the corresponding vertex of G. The set corresponding to an internal node is then just given by its leaf descendants.

Using this representation, we obtain the following: Bucket sorting a list of m items by integer keys in the range from 1 to n takes O✄ n ☎ m✆ time, even if an initialized set of buckets is provided. However, if one only wishes to group the items into groups that have identical keys, the operation may be carried out in O✄ m✆ time if the initialized buckets are already available. While inserting the items to buckets, one must simply maintain a list of nonempty buckets. When all items are inserted, the list may be used to visit only the nonempty buckets, retrieving one group at each of them. The operation takes only O✄ m✆ time. To distinguish this operation from bucket sorting, we will call it bucket grouping. Similarly, if a list of m items must be sorted by a pair of keys in the range from 1 to n, this takes O✄ n ☎ m✆ time by a radix sort that makes one call to bucket sort for each of the keys [START_REF] Cormen | Algorithms[END_REF]. If one wishes only to partition the items into groups that share identical pairs of keys, the calls to bucket sort may be replaced by bucket groupings, and the partition takes O✄ m✆ time. We will call this operation radix grouping.

The data structure for the graph is an adjacency-list representation, where the vertices are numbered from 1 to n, and where the adjacency lists are doubly-linked lists. The adjacency list associated with vertex x has each arc of the form ✄ x✄ y✆ . Each such arc ✄ x✄ y✆ , in turn, has a pointer to the occurrence of its "twin" ✄ y✄ x✆ in the adjacency list of y. We also keep a partition P of the vertices. Each partition class of P is implemented with a doubly-linked list, and each vertex has a pointer to its occurrence in one of these lists, as well as a pointer to the beginning of this list.

The Gamma relation

An undirected graph may be viewed as a special case of a (symmetric) digraph, where each edge ✄ x✄ y✆ is represented by two arcs, ✄ x✄ y✆ and ✄ y✄ x✆ . An orientation of the graph is a choice of one arc from each such pair.

Let Γ be a relation on the arcs of a digraph, where ✄ u✄ w✆ Γ✄ x✄ y✆ if and only if u x and w and y are nonadjacent, or w y and u and x are nonadjacent [START_REF] Gallai | Transitiv orientierbare graphen[END_REF][START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Möhring | Algorithmic aspects of comparability graphs and interval graphs[END_REF]. Let Γ be the transitive reflexive closure of Γ. It is easy to see that ✄ u✄ w✆ Γ✄ x✄ y✆ in a comparability graph, then in each transitive orientation, ✄ u✄ w✆ and ✄ x✄ y✆ are either both present or both absent. Transitively, it follows that ✄ u✄ w✆ Γ ✄ x✄ y✆ implies this also. Since Γ is an equivalence relation, this partitions the edges into groups such that for each group, either every member of the group is included in a transitive M orientation or none is. These groups are the implication classes. In fact, this characterizes comparability graphs: an undirected graph is a comparability graph if and only if for each implication class I, I is disjoint from I ✁ 1 [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]. We also make use of the following well-known result, which can be found in [START_REF] Möhring | Algorithmic aspects of comparability graphs and interval graphs[END_REF]:

Theorem 5.1 If all edges of G are in a single color class, then all nontrivial modules of G are independent sets.

6 Computing G ☎ P ✆ G✝ v✞ and its modular decomposition

We now describe a procedure called vertex partitioning, which we use to compute P ✄ G✄ v✆ in Algorithm 1.

The input to the procedure is a partition of the vertices, and it finds a refinement of the partition that gives the maximal modules of G that are subsets of one of the original partition classes.

The most basic operation in vertex partitioning is the pivot. An input is a partition P of the vertices of the graph, a vertex x, and the edges from x to some subset Q of members of P . The operation produces a refinement P ✁ such that every module that is a subset of a class in P is also a subset of a class of P ✁ , and, in addition, any class of P ✁ that is a subset of a member of Q consists only of neighbors or only of non-neighbors of x.

To implement a pivot, let X be the class of P that contains x. For each neighbor y of x in a member of Q , identify the set Y ✝ P that contains y, and move y to a twin list Y We now describe what we will call the split operation, which we will denote Split ✄ X ✄ P ✆ . Let P be a partition of the vertices, and let X ✝ P . Given the arcs E ✁ that have one end in X and the other in V X, we may use them to subdivide X and the members of P ✁ X ✂ to obtain a refinement P ✁ of P . This refinement has the property that for any x ✝ X, each class Y of P ✁ contained in V ✄ G✆ X consists only of neighbors or only of non-neighbors of X, and for any z ✝ V ✄ G✆ X, each class Z of P ✁ contained in X consists only of neighbors or only of non-neighbors of z.

To implement the split operation, we bucket group all arcs ✄ x✄ y✆ in E ✁ by starting vertex x. Each group gives the neighbors of some x ✝ X in V ✄ G✆ X. We perform a pivot on x to split up those members of P that are subsets of V ✄ G✆ X. This refines P . Pivots on the other groups give further successive refinements of P . After this has been done, each class of P that is a subset of V ✄ G✆ X has the required properties. We then use the twin pointers of arcs in E ✁ to find the arcs in ✄ V ✄ G✆ X ✆ ✁ X, and perform the foregoing steps on them to refine X. When we are done, each class of P that is a subset of X has the desired properties. The procedure returns the refined partition, listing those classes that are subsets of X separtely from those that are not. If the arcs E

✁ E ✁ ✄ X ✁ ✄ V ✄ G✆ X ✆ ✆ are given, the operation takes O✄ 1 ☎ ✆ E ✁ ✆ ✆
. If they are not given, it takes O✄ ✆ X ✆ ☎ deg✄ X ✆ ✆ , where deg ✄ X ✆ is the sum of degrees of members of X, since the adjacency lists of members of X must be searched to find the members of E ✁ . The vertex partitioning algorithm is given by Algorithm 2.

Algorithm 2: Partition✄ G✄ P ✆ , Vertex partitioning.

if ✆ P ✆ 1 then return P ; else Let X be a member of P that is not larger than all others;

Let E be the edges of

G in X ✁ ✄ V ✄ G✆ X ✆ ; P ✁ Split ✄ X ✄ P ✆ ; G : G E;
Let Q be the classes of P ✁ contained in X;

Let Q ✁ be the classes of P ✁ contained in V ✄ G✆ X; return Partition✄ G✆ X ✄ Q ✆ ✂ Partition✄ G X ✄ Q ✁ ✆ ;
To prove the correctness, we show that every member of the returned partition is a module. Since refinements are caused by pivots and no pivot can split up a module, it follows that the returned partition consists of the maximal modules of G that are subsets of a class in the initial partition. As a base case, if ✆ P ✆ 1, its sole member, V ✄ G✆ , is trivially a module in G. Otherwise, assume by induction that the first recursive call returns a partition of X whose partition classes are modules in G ✆ X and subsets of classes in Q . If Y is one of the returned partition classes, every node of X Y is either a neighbor of every element of Y or a non-neighbor of every element of Y . If Z is the member of Q that contains Y , then because of the call to Split, each element of V ✄ G✆ X is either a neighbor of every element of Z or a non-neighbor of every element of Z, hence the same can be said about Y . Thus, Y is a module in G. A symmetric argument shows that each partition class returned by the second recursive call is a module.

For the time bound, note that the call to Split takes O✄ ✆ X ✆ ☎ deg✄ X ✆ ✆ time, since the edges from X to V ✄ G✆ X are not supplied. We charge the cost of this by assessing O✄ 1✆ to each member of X and each edge incident to X. Since ✆ X ✆ ✆ V ✄ G✆ ✆ ☎ 2, a vertex and its edges are charged only if its partition class has at most half of the vertices passed by the call to the procedure. Since this is also true in the recursive calls, the next time x ✝ X and its incident edges are charged charged in a recursive call, the partition class that contains it will have size at most ✆ X ✆ ☎ 2. We conclude that no element of the graph is charged more than log 2 n times, which gives an O✄ ✄ n ☎ m✆ logn✆ time bound. An O✄ ✄ n ☎ m✆ logn✆ bound can be reduced to an O✄ n ☎ m log n✆ bound by spending O✄ n ☎ m✆ preprocessing time finding the connected components of G, applying the algorithm on each component, and combining the results in a trivial way, using the fact that any union of components is a module.

Ordered vertex partition

Recall that a graph is prime if it has only trivial modules. We may transitively orient prime comparability graphs and recognize arbitrary prime graphs by revising the above approach so that it keeps the partition classes in an ordered list as they are refined. Algorithm 3 gives an important subroutine, which appeared in [START_REF] Mcconnell | Linear-time modular decomposition and efficient transitive orientation of comparability graphs[END_REF].

Algorithm 3: OV P✄ G✄ P ✆

Run Algorithm 2, with the following changes. A linear order on the members of P is given initially. Maintain a linear order on P as it is refined, using the following rule: When a pivot on a vertex p ✝ Y ✝ P splits X ✝ P into a set X a of adjacent vertices and a set X n of nonadjacent vertices, make X a and X n consecutive at the former position of X in the linear order, with X n the nearer of the two to Y in the linear order. Return the final partition and its linear order.

The significance of this ordering will soon become clear. The initial parameter P will always be ✄ ✁ v✂ ✄ V ✁ v✂ ✆ for a vertex v, which we call the seed. To facilitate the computation of the ordering, we maintain labels on the partition classes so that a class Y is labeled with ✄ i✄ j✆ , where i is one plus the sum of cardinalities of classes that precede Y and j is one less than the sum of cardinalities of classes that follow; these labels are trivial to update during a pivot, and they allow one to find out quickly whether the pivot's class precedes or follows Y . This allows us to find the correct relative order for X a and X n in O✄ 1✆ time, so the time bound for OV P is the same as that for Partition, O✄ n ☎ m logn✆ . Let the edges exposed by a partition of vertices be those edges that are not contained in a single partition class. Suppose that P is ordered so that all arcs that go from earlier to later members of P are in a single implication class. In this case, we say that the ordering on P is consistent with a transitive orientation of G. Using this as an inductive hypothesis, it is easy to verify that when a class is split according to the above ordering rules, the refinement of P and its ordering is also consistent with a transitive orientation: if a pivot p splits X into a set X a of adjacent vertices, and X n of nonadjacent vertices, then all members of ✁ p✂ ✁ X a are in one implication class, and these force all members of X n ✁ X a that are edges into this implication class. The inductive hypothesis continues to hold after the class splits. It follows that if the initial ordering of P is consistent with a transitive orientation, then so is the final ordering. Thus, if G is prime and v is a source vertex in a transitive orientation, then calling the algorithm with initial ordered partition ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ gives a linear extension of the transitive orientation [START_REF] Mcconnell | Linear-time modular decomposition and efficient transitive orientation of comparability graphs[END_REF].

The problem of transitively orienting a prime comparability graph thus reduces to identifying a source vertex in a transitive orientation. Suppose P is ordered so that for each vertex x in the last class X, all edges of ✁ x✂ ✁ V ✄ G✆ X are in one implication class. Then if a an argument similar to the one above shows that if a pivot p splits X into X a and X n , all edges of ✁ x✂ ✁ ✄ V ✄ G✆ X a ✆ are in one implication class. By induction, if the ordered partitioning algorithm is called with initial ordered partition ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ for arbitrary v, the last partition class in the final ordering is a source in a transitive orientation.

Algorithm 5 summarizes the procedure for finding a transitive orientation of a prime comparability graph [START_REF] Mcconnell | Linear-time modular decomposition and efficient transitive orientation of comparability graphs[END_REF]: Algorithm 5: TO(G) Transitive orientation of a prime comparability graph.

Let v be an arbitrary vertex ;

P : OV P✄ G✄ ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ ✆ ;
Let ✁ w✂ be the rightmost class in P ;

return OV P✄ G✄ ✄ ✁ w✂ ✄ V ✄ G✆ ✁ w✂ ✆ ✆ .
We now show that the same algorithm recognizes whether an arbitrary graph is prime [START_REF] Mcconnell | Linear-time modular decomposition and efficient transitive orientation of comparability graphs[END_REF]. Performing these two vertex partitions without encountering a nontrivial module proves that all edges of the graph are in a single color class. By Theorem 5.1, this implies that any nontrivial modules are independent sets. The first vertex partition finds a nontrivial module if one is a subset of V ✄ G✆ v. The second finds one if one is a subset of V ✄ G✆ w. Thus, any nontrivial modules contain both v and w. However, w is adjacent to v, since it was rightmost in the final partition, hence was among the neighbors of v, which were moved to the right when the pivot on v split V ✁ v✂ . Thus, any nontrivial module is an independent set, and any nontrivial module contains the edges ✄ w✄ v✆ . There can be no nontrivial module.

Finding the modular decomposition of G P ✁ G✂ v✄

We have shown how to compute P ✄ G✄ v✆ and to compute the composition of unreduced modular decomposition trees. The only remaining problem in Algorithm 1 is computing the modular decomposition of

G ☎ P ✄ G✄ v✆ .
Let a graph G be nested if all nontrivial modules are ancestors of a particular vertex v in MD✄ G✆ . We call v and its siblings the innermost vertices. Thus, the remaining step of Algorithm 1 reduces to computing the modular decomposition of nested graphs.

Lemma 6.1 For any undirected graph G and any vertex v, G

☎ P ✄ G✄ v✆ is nested, and ✁ v✂ is an innermost vertex in it. Proof: If M is a nontrivial module of G ☎ P ✄ G✄ v✆ that does not contain ✁ v✂ , then M is a nontrivial module of G that does not contain v,
Algorithm 5 simultaneously recognizes prime graphs and transitively orients them if they are comparability graphs. Recognizing a prime graph can be viewed as a special case of finding modular decomposition, which works only if the graph is prime. We generalize it so that it simultaneously computes the modular decomposition of nested graphs, and finds a transitive orientation when they are comparability graphs.

We use a variant of OV P, which is given by Algorithm 6. This procedure applies itself recursively inside each of the modules found by OV P. The vertices of G are assumed to be numbered; this determines selection of the seed vertices in calls to OV P.

Algorithm 6: ROP✄ G✆ , recursive application of OVP (Algorithm 3)

if G has an isolated vertex then let w be that vertex; else let w be the highest numbered vertex; if G has only one vertex then return ✁ w✂ ; else

✄ X 1 ✄ X 2 ✄ ✂ ✂ ✂ ✄ X k ✆ : OV P✄ G✄ ✄ ✁ w✂ ✄ V ✄ G✆ ✁ w✂ ✆ ✆ ;
Let T be a module tree with one node V ✄ G✆ ; foreach set X i do Let ROP✄ G✆ X i ✆ be the i th child of V ✄ G✆ ; return T Lemma 6. [START_REF] Dahlhaus | Efficient parallel modular decomposition. 21 st Int[END_REF] The ROP algorithm takes O✄ ✄ n ☎ m✆ logn✆ time.

Proof: Using the data structure of Section 4, it takes O✄ 1✆ time to attach each child to V ✄ G✆ . Since the final tree has n leaves and every internal node has at least two children, this step takes has O✄ n✆ , all steps except the calls to OV P contribute O✄ n✆ to the running time of ROP. The running time for the calls to OV P is bounded by the time spend on pivots in Algorithm 2 inside these calls. In this procedure, no pivot on a vertex x occurs unless it is in a class that is at most half as large as the class that contained it the last time a pivot was performed on x in Algorithm 2 and in a class that is half as large as the class that contained it at the beginning of the call to Algorithm 2. From this last observation, we may conclude that whenever a pivot is performed on v, it is in a class that is half as large as the class that contained it the previous time a pivot occurred on it in any call to OV P generated by ROP. Since the cost of the pivot is O✄ 1 ☎ d ✄ v✆ ✆ the total cost of all pivots in all calls to OV P is O✄ ✄ n ☎ m✆ logn✆ .

Corollary 6.3

The total time spent in UMD (Algorithm 1) by calls it makes to OV P is O✄ ✄ n ☎ m✆ log n✆ .

Proof: These are the same as the calls to OV P generated by a call to ROP. Algorithm 7 finds the modular decomposition in nested graphs, if an innermost vertex v is given.

We now demonstrate the correctness. Since all modules of G contain v, the call to OV P✄ G✄ ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ simply assigns an ordering to the vertices of G via the ordering of the returned singleton sets. This

Efficient implementation of Algorithm 1

The following gives an efficient implementation of Algorithm time. G ☎ P ✄ G✄ v✆ has at most one edge for every edge of G not contained in a member of P ✄ G✄ v✆ . We may charge the cost of this to O✄ log n✆ set costs for each member of P ✄ G✄ v✆ , and O✄ log n✆ edge costs for each edge not contained in one of its members. The edges charged are disjoint from those charged in recursive calls, so Step 3 contributes O✄ m log n✆ edge charges. The containment relation on sets incurring a set cost in some recursive call of UMD is a tree, so there are O✄ n✆ of them. The total contributed by Step 3 to the running time of UMD is O✄ ✄ n ☎ m✆ logn✆ .

Computing the composition of the trees takes O✄ 1✆ for each member of P ✄ G✄ v✆ , by Lemma 4.1. This contributes an additional O✄ 1✆ cost to each set incurring a set cost in Step 3. Computing compositions of trees thus contributes O✄ n✆ to the running time of the algorithm.

The total running time is O✄ ✄ n ☎ m✆ log n✆ . However, this bound for any modular decomposition algorithm can be reduced to an O✄ n ☎ m log n✆ bound by spending O✄ n ☎ m✆ preprocessing time to find the connected components, and if there are k 1 of them applying the algorithm separately to each component, and making the resulting k trees children of V ✄ G✆ .

Conclusions

Another closely-related variant of this algorithm is to perform ordered vertex partitioning, and then to perform it recursively inside each nontrivial module that is found. The final result is an ordering of the vertices. A linear extension of a transitive orientation is obtained by performing a second pass of this recursive algorithm, except that in each recursive call on a set X of vertices, the initial pivot vertex must be the rightmost member of X in the ordering produced by the first pass. Every strong module of G is identified as a module in one of the two passes. Every module that is found in one of the passes and is not strong is found to overlap a module found in the other pass. It is therefore a simple matter to obtain the modular decomposition by discarding those modules from the two passes that overlap. The proof of correctness is quite similar to the one we give above.

Another promising idea is to try to obtain the result of the vertex partitioning step without actually performing vertex partitioning. This is the approach of the parallel and sequential algorithms of [START_REF] Dahlhaus | Efficient parallel modular decomposition. 21 st Int[END_REF][START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF]. This elegant strategy, which is due to Dahlhaus, makes recursive calls on subgraph induced by the neighbors of v and the subgraph induced by the non-neighbors of v, and then deletes portions of these two trees to obtain the members of P ✄ G✄ v✆ and their modular decompositions. However, up until now, turning this idea into an O✄ n ☎ mα✄ m✄ n✆ ✆ algorithm requires conceptually difficult tricks, such as letting some parent pointers in the tree get out of date, and maintaining a union-find data structure to help simulate them. It also requires careful charging arguments to prove the time bound. The linear-time variant uses sophisticated union-find data structures.

One of the important points illustrated by the algorithm is that finding a simple linear-time vertex partitioning algorithm would give simple linear-time solutions to modular decomposition and transitive orientation. There is reason to hope that one might exist. In the first place, the basis of the difficult transitive orientation algorithm of [START_REF] Mcconnell | Linear-time transitive orientation[END_REF] is a (difficult) linear-time implementation of Algorithm 6. Thus, there is no inherent barrier to a linear time bound. It is also worth noting that the algorithm we give here is actually linear on many classes of graphs. For instance, on graphs with fixed degree bound k, it is easy to verify that, at any point during a call to OV P✄ G✄ ✁ v✂ ✄ V ✄ G ✁ v✂ ✆ , only one partition class can have size greater than c. The proof of this is by induction on the number of pivots performed so far. In the proof of ROP, we saw that each time a pivot occurs on a vertex, it is in a class that is half as large as the class that contained it the previous time it was a pivot. This gives an O✄ ✄ n ☎ m✆ log k✆ O✄ n ☎ m✆ bound for ROP. Since ROP is the bottleneck for the time bound of Algorithm 8, this gives a linear time bound in this case.

A similar argument shows that on graphs where the ratio of the maximum degree k to the minimum degree k ✁ is at most c, the time bound is linear. Suppose k ✁ is the minimum degree. Let us say a vertex is confined if it is in a class of size at most k ☎ 2, and a pivot is confined if the pivot vertex is confined at the time. Consider a confined pivot on a vertex p. The OV P algorithm removes all edges from p to other classes during a pivot. Let d be the number edges still incident to p, and let j be the size of the class that currently contains it. If d j then the cost of the pivot is O✄ j✆ . If d j, we charge O✄ d j✆ of the O✄ d✆ cost of the pivot to the d j edges thrown out of G during the pivot, at O✄ 1✆ per deleted edge. The total of charged costs over all confined pivots on p is O✄ 1✆ for each edge originally incident to p. The uncharged cost of the pivot is O✄ j✆ . Since the value of j drops by a factor of two each time a pivot occurs on p, the uncharged cost of pivots on p after it is confined is O✄ k

✁ ☎ 2 ☎ k ✁ ☎ 4 ☎ k ✁ ☎ 8 ☎ ✂ ✂ ✂ ☎ 2 ☎ 1✆ O✄ k ✁ ✆
, which is O✄ 1✆ for each edge originally incident to p. Thus, confined pivots contribute O✄ m✆ time to the running time of ROP. Since the size of a class containing p drops by a factor of two each time it is used as a pivot, and no pivot occurs on it when it is in a class larger than k, there are O✄ log k

Fig. 2 :

 2 Fig. 2: A quotient on the graph of Figure 1. For any pair X ✁ Y ✂ of disjoint modules, either every element of X ✄ Y

Fig. 3 :

 3 Fig. 3:The modular decomposition of the graph of Figure1. The leaves are the vertices of the graph. The internal nodes are the strong modules, and their members are their leaf descendants. An internal node is a parallel node (labeled 0) if the set it denotes induces a disconnected graph, and its children are its connected components. It is a series node (labeled 1) if the complement of the graph it induces is a disconnected graph, and its children are the connected components of the complement. It is a prime node if it induces a graph that is connected and whose complement is connected; its children are the maximal modules it contains. A set of vertices is a module if and only if it is a node of the tree or a union of children of a single parallel or degenerate node.

Lemma 4 . 1

 41 The composition step of Algorithm 1 takes O✄ ✆ P ✄ G✄ v✆ ✆ ✆ time.Proof:The composition is obtained by replacing each leaf ✁ Y ✂ of the decomposition of G ☎ P ✄ G✄ v✆ with the tree T Y . This requires one pointer operation. The decomposition of G ☎ P ✄ G✄ v✆ has one leaf for each member of P ✄ G✄ v✆ .

  If I is a set of arcs, let I ✁ 1 denote the class ✁ ✄ y✄ x✆ : ✄ x✄ y✆ ✝ I ✂ ✄✂ By symmetry, whenever I is an implication class in an arbitrary graph, I ✁ 1 is also an implication class. It is easy to see that, in any undirected graph, either I ✁ 1 I or I ✁ 1 is disjoint from I. Let a color class be I ✂ I ✁ 1 for an implication class I. The color classes are a partition of the undirected edges of G. A graph is a comparability graph only if every implication class I is disjoint from I ✁ 1 ; otherwise no orientation of the graph can contain the implication class.

✁

  for Y . Start a new list for Y ✁ if Y doesn't already have a twin list. In the process, keep a list of the members of P in which this happens. When this is finished, Y contains only non-neighbors of x, and its twin Y ✁ contains only neighbors. Establish Y and Y ✁ as classes in the refinement P ✁ . If there are k edges from x to members of Q , this operation takes O✄ 1 ☎ k✆ time.

Algorithm 4 :

 4 Compute G ☎ P ✄ G✄ v✆ . Algorithm 2, hence Algorithm 3 explicitly removes those edges that are not contained in a member of P ✄ G✄ v✆ . Let m ✁ be the number of removed edges. The data structures of Section 4 for implementing a partition allow us to find which partition class a vertex belongs to in O✄ 1✆ time. Radix group the removed edges according to the two partition classes. This takes O✄ m ✁ ✆ time. Discard all but one representative edge in each group; the representative edges give the edges of G ☎ P ✄ G✄ v✆ . The entire operation takes O✄ m ✁ ✆ time, in addition to the time required by the call to OV P.

  p. Each pivot takes O✄ 1✆ time for each edge incident to p, so the total contribution of unconfined pivots to the running time of ROP is O✄ m log k ☎ k ✁ ✆ O✄ m✆ for graphs where the ratio k ☎ k ✁ of maximum to minimum degree is bounded by a constant.

  ✄ G✄ v✆ is a partition of the vertices of G, hence a congruence partition.The nodes of the decomposition tree are the strong modules. However, the containment relation on the nodes is still a tree if we add a weak module to the nodes. This module is a union of a set X of children of a series or parallel node; the containment relation dictates that it becomes a child of this node, and that the members of X become its children. If Y is the new node and Z is the parent, G

	Lemma 3.3 A set is a member of P ✄ G✄ v✆ if and only if one of the following applies:
	1. It is ✁ v✂ ;
	2. It is a child of a prime ancestor of ✁ v✂ in the decomposition tree that does not contain v;
	3. It is the union of those children of a series or parallel ancestor of v that do not contain v.
	Proof: This is immediate from the fact that a set is a module if and only if it is a child of a prime node,
	or any union of one or more children of a degenerate node.
	Thus, P
	node is a parallel node
	(labeled 0) if the set it denotes induces a disconnected graph, and its children are its connected components. It is
	a series node (labeled 1) if the complement of the graph it induces is a disconnected graph, and its children are
	the connected components of the complement. It is a prime node if it induces a graph that is connected and whose
	complement is connected; its children are the maximal modules it contains. A set of vertices is a module if and only
	if it is a node of the tree or a union of children of a single parallel or degenerate node.

✆ Y is disconnected if and only if G✆ Z is, and

✄

  by Theorem 3.2. No member of M is a maximal module of G not containing v, which contradicts the definition of P . If A and B are overlapping modules of G G✄ v✆ , then either A, B, or A∆B is a nontrivial module of G

☎ P ☎ P

✄

  G✄ v✆ that does not contain ✁ v✂ , which we have just seen cannot happen. Thus, all modules of G ☎ P are strong and contain ✁ v✂ , from which the result follows.

  [START_REF] Cormen | Algorithms[END_REF]. Algorithm 8 takes O✄ n ☎ m logn✆ . The set of instances of Step 1 over all recursive calls to UMD is just the set of calls to OV P generated by a single call to ROP. Since that algorithm is O✄ n ☎ m logn✆ , Step 1 contributes O✄ n ☎ m logn✆ to the running time of UMD. G✄ v✆ in the main call takes O✄ 1✆ time for each edge of G not contained in a member of P ✄ G✄ v✆ . We charge this cost to these edges. The edges charged in recursive calls are disjoint from these, so the total contributed by step 2 to the running time of UMD is O✄ m✆ .A call to Algorithm 7 on a nested graph with n

	Algorithm 8: Final modular decomposition algorithm.
	Implement UMD✄ G✆ as follows:
	Compute P ✄ G✄ v✆ with a call to Algorithm 3;
	Compute G	☎ P ✄ G✄ v✆ with a call to Algorithm 4;
	Compute the modular decomposition of G	☎ P ✄ G✄ v✆ with a call to Algorithm 7.
	Lemma 7.1 By Lemma 4, computing G
			✁	✁
			☎	m	✆ log n

Proof: ☎ P ✄ ✁ vertices and m ✁ edges takes O✄ ✄ n ✁ ✆

† This work has been made possible NSF Grant 98-20840. 1365-8050 c ✝ 2000 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France

Algorithm 7: Chain✄ G✄ v✆ , Modular decomposition in a nested graph. P : OV P✄ G✄ ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ ; Number the vertices of G in order of their appearance in P ; return ROP✄ G✆ . ordering is not unique, since it depends on choices of pivots during execution of the algorithm. However, not all permutations are possible. Let us say that an ordering is a valid result for the call if there is a sequence of pivot choices that causes it to produce that ordering.

Lemma 6.4 If all nontrivial modules of G contain vertex v, X is a module that contains v, and π is the ordering of vertices produced by a call to OV P✄ G✄

Proof: A vertex y ✝ V ✄ G✆ X is adjacent to all members of X or nonadjacent to all of them. Thus, during a call to OV P✄ G✄ ✄ ✁ v✂ ✄ V ✄ G✆ ✁ v✂ ✆ ✆ , if two members of X are in a single partition class before a pivot on y, they remain in a single class after the pivot, so the pivot on y has no effect on their relative order. The final ordering of X is determined exclusively by pivots on members of X and their adjacencies in G✆ X. The production of this ordering can thus be simulated by a call to

In the modular decomposition of a nested graph, each internal node of the decomposition tree has at most one non-singleton child, namely, the one that contains v. Also, a series or parallel node has exactly two children; otherwise the union of two that do not contain v results in a nontrivial module that does not contain v. Let w ✁ be the seed vertex selected to fill the role of w in the main call to ROP that is generated in Chain. If the root of the tree is a parallel node, then V ✄ G✆ has two children, one of which is an isolated node, and w ✁ is selected to be this node. If the root is a series node, then V ✄ G✆ has two children, one of which is an isolated node in the complement of G. The ordering rule in the call to OV P ensures that this node will receive the highest number of any node, and w ✁ is selected to be this node. Otherwise, the rightmost class in the numbering produced by OV P is a singleton class ✁ w✂ . As in the proof of Algorithm 5, all edges out of ✁ w✂ are in the same implication class, and w is adjacent to v. Thus, all nontrivial modules that contain w contain v. It follows that ✁ w✂ is again a child of the root, since all nontrivial modules contain v. The call to OV P✄ G✄ ✄ ✁ w

generated in this highest-level call to ROP then finds the maximal modules that do not contain w ✁ , and since ✁ w ✁ ✂ is a child of the root, this call to OV P just returns the children of the root.

We now show that the recursive call generated inside ROP finds the remainder of the tree. Algorithm 7 obviously works correctly when G has only one vertex. Adopt as an inductive hypothesis that G is a nested graph with n vertices and the algorithm works on nested graphs graphs with fewer vertices. Let X be the non-singleton child of V ✄ G✆ , the one that contains ✁ v✂ . By Theorem 3.1, G ✆ X is nested with v as an innermost vertex, so a call to Chain on G✆ X could be used to compute the rest of the tree. Such a call would first call OV P to assign an ordering to X, and then call ROP on G ✆ X. By Lemma 6.4, the vertex numbering of X is already available in the numbering of vertices of X, so the call to ROP on G ✆ X returns exactly what such call to Chain on G ✆ X would. By the inductive hypothesis, this is the remainder of the modular decomposition of G, namely, the subtree rooted at X. Lemma 6.5 Chain can be run in O✄ ✄ n ☎ m✆ logn✆ time.

Proof: This is immediate from the fact that OV P and ROP both have this time bound.