Categorical Views on Computations on Trees(Extended Abstract)
Ichiro Hasuo1 , Bart Jacobs1 , and Tarmo Uustalu2
1

Institute of Computing and Information Sciences, Radboud University Nijmegen,Postbus 9010, NL-6500 GL Nijmegen, The Netherlands
http://www.cs.ru.nl/~{ichiro, bart}
2
Institute of Cybernetics at Tallinn University of Technology,
Akadeemia tee 21, EE-12618 Tallinn, Estonia
http://www.cs.ioc.ee/~tarmo

Abstract. Computations on trees form a classical topic in computing.
These computations can be described in terms of machines (typicallycalled tree transducers), or in terms of functions. This paper focuseson three flavors of bottom-up computations, of increasing generality. It
brings categorical clarity by identifying a category of tree transducers
together with two different behavior functors. The first sends a treetransducer to a coKleisli or biKleisli map (describing the contributionof each local node in an input tree to the global transformation) and thesecond to a tree function (the global tree transformation). The first behavior functor has an adjoint realization functor, like in Goguen’s early
work on automata. Further categorical structure, in the form of Hughes’s
Arrows, appears in properly parameterized versions of these structures.

1

Introduction

Tree transformations are functions sending trees to trees. Such transformations
are of broad interest in computing, notably in language processing, and are often
studied in relation to certain types of realizing machines. They form a classical
topic.
In this paper we aim at a systematic study of phenomena and constructions related to bottom-up tree transformations. We first sketch two motivating
observations: these will later be given detailed accounts.
Behavior-realization adjunction It is a fundamental idea in computer science that
we associate with a “computable” function a “machine” which realizes it. Thosemachines which realize tree transformations are often called tree transducers andhave been extensively studied as a continuation of automata theory: see [10,11,2]
and also more recently [1].
Here comes our first question. What do we mean by saying “a machine c
realizes a transformation l”? Given a transformation l, is there a machine which
realizes it? Is there a canonical choice among such realizers? We shall answer
these questions, following the idea of Goguen’s behavior-realization adjunction [3]for (a more elementary setting of) automata, see also [9].

Tree functions from local behaviors We start with relabeling bottom-up treetransformations that only change labels on each node of an input tree, like l on
the left.
b4

a4
a3

a2
a0

a1

7−→

a4

b2

l

b0

b3

a3

a2

b1

a0

a1

k

7−→ b4(1)

Now let us consider another function k which operates on the same input trees
as l does but returns the root label of the output tree of l. That is, k = ǫ ◦ lwhere ǫ extracts the root label. It may seem that k (which shall be called a local
behavior ) carries less information than l does—ǫ throws information away. But
when l is relabeling bottom-up we can recover l from k.
Our main contribution is to give an account of some classes of tree transformations in terms of diagrams like this:TT
H
Real ⊣  LBeh
LBeh

TF
(

6 TF↑



/ TF

(2)

W

Here, TF and LBeh are two behavior functors from the category of tree transducers (“machines”) to tree functions and to local behaviors. For relabelings,
the functor W is an isomorphism: this embodies the equivalence of the two
behaviors TF and LBeh as hinted at above; for more general types of tree transformations, it will be epi. The category TF↑ is included in TF of tree functions
in general: we shall give a categorical characterization of being “bottom-up”.
The local behaviors are coKleisli maps of certain comonads, in one case biKleisli
maps of a distributive law of a comonad over a monad, and agree with the ideaof comonadic notions of computation as those that send “values-in-contexts”
to “values” [13,12] (the latter reference deals with attribute grammars, anothertype of tree computations). The behavior-realization adjunction is presented as
Real ⊣ LBeh.
In each of the Sects. 2–4, we shall develop a situation like (2) for a specificclass of tree transformations—and hence a corresponding class of tree transducers. Namely, relabeling bottom-up tree transducers in Sect. 2; rebranching bottomup tree transducers in Sect. 3, and bottom-up tree transducers in full generality in
Sect. 4. In Sect. 5 we generalize our categorical formulation in an orthogonal direction: we uncover further compositional structures using Hughes’s Arrows [5],and thus a way to view tree transformations as “structured computations” inprogramming semantics.

2

Relabeling Bottom-Up Tree Transducers

In this section we will consider a class of tree transducers (TTs) that operate
on well-founded trees of a fixed branching type F (a set functor), with labels

at their nodes taken from a parameter set, or alphabet. These transducers takeA-labeled trees to B-labeled trees for fixed alphabets A, B, but Section 5 will
sketch a properly parameterized version. They work bottom-up by only changing
the labels of an input tree and are thus shape-preserving.
For this class of TTs, we shall turn the informal diagram (2) from the introduction into the diagram below. It has: two behavior functors LBeh and TF ; afunctor W establishing equivalence of two kinds of behavior; and an adjunction
Real ⊣ LBeh.
TT(A, B)
I
Real ⊣ LBeh
LBeh(A, B)

TF
∼
=
W

*

TF↑ (A, B) 
4(3)

/ TF(A, B)

That the branching type of our trees is expressed by a set functor F generalizes
more traditional universal-algebraic signatures, given by a set Σ of operations`f, each with an arity |f| ∈ N. Such a signature yields a functor Z 7→ f∈Σ Z |f| .
The A-labeled trees of the branching type F (for brevity, we also say A-trees)
live in the initial algebra of the functor A × F , whose carrier we denote by DA,∼=
leaving F implicit. The algebra structure A × F DA → DA will be denoted byσA . Obviously D1 is the set of unlabelled trees or tree-shapes.
Definition 2.1 A (relabeling bottom-up) tree transducer (TT) is a functioncA × F X → B × X in Sets, where the set X is called the state space. A morphismcdof such TTs from A × F X → B × X to A × F Y → B × Y is a function f : X →Y satisfying (B × f ) ◦ c = d ◦ (A × F f ).
TTs and morphisms between them form a category which we denote byTT(A, B), leaving again the dependence on F implicit. Obviously, TT(A, B) is
nothing but the comma category (A × F ↓ B × ).
Example 2.2 The operation of a TT is best described on an example. As thebranching type F we take 1 + ( )2 , describing well-founded binary trees. Concsider a TT A × (1 + X 2 ) → B × X and the leftmost tree below as an input.
(b4 , x4 )a4
a0

(b3 , x3 )

a3

a2
a1

(b0 , x0 ) (b1 , x1 )(b2 , x2 )(b3 , x3 )(b0 , x0 ) (b1 , x1 )c

The bottom-up computation starts at the leaves: let (a0 , κ1 (∗)) 7→ (b0 , x0 ),where κ1 , κ2 are coproduct injections. This assigns a label b0 and a state x0 to
the corresponding leaf of the output tree. Similar mappings at the other leaves
lead to the middle tree. At the inner position of a2 , the label on the output tree
is determined by the input label a2 as well as by the states x0 , x1 of the successor
nodes. They are already available precisely because we proceed in a bottom-upcmanner. Now we get (b2 , x2 ) from the outcome (a2 , κ2 (x0 , x1 )) 7→ (b2 , x2 ). Weccontinue this way and get the tree on the right from (a4 , κ2 (x2 , x3 )) 7→ (b4 , x4 ).

By forgetting about the states xi , we finally obtain the output tree of thecomputation. It is obvious that the shape of the input tree is preserved. This
will change in the next section.
For a TT c, we shall now define two behaviors TF (c) and LBeh(c). The
former is a function that carries an A-tree to a B-tree; the latter carries an
A-tree to an element in B, as hinted at in the introduction.
cDefinition 2.3 A TT A × F X → B × X induces its tree function behavior
TF (c) : DA → DB and its local behavior LBeh(c) : DA → B via the following
two diagrams, both using the initiality of σA .
A × F DA _ _ _ _/ A × F (DB × X)
σA ∼
c̆
=


DA _ _ _ _ _ _ _/ DB × X
 π1
/ DB
TF (c)

A × F DA _ _ _ _/ A × F (B × X)
 A × F π2σA ∼=A × FXc
DA _ _ _ _ _ _ _/ B × X
 π1/B
LBeh(c)where the algebra structure c̆ on the left is given by the composite
A × F (DB × X)

hF π1 ,F π2 i

−→

σ

c

B
DB × XA × F DB × F X −→ B × F DB × X −→the underlining indicating what the maps act on.
The mapping A 7→ DA carries a comonad structure. It is the cofree recursive
comonad on F [14]. A local behavior LBeh(c) : DA → B is a morphism A → B
in the coKleisli category of the comonad D. This is a general phenomenon.
By a simple diagram chase it can be seen that a morphism of TTs is indeed
a “behavior-preserving map” wrt. the above two behaviors.
Lemma 2.4 Assume we have a morphism f from one TT c to another d. Then
LBeh(c) = LBeh(d) and TF (c) = TF (d).
⊓⊔In Example 2.2 we have illustrated how a TT acts in a bottom-up fashion ontrees. Before we can show that the TF behavior from Def. 2.3 is indeed “bottomup” we need a characterization of bottom-up tree functions. Intuitively, these
are the functions l : DA → DB such that:

l



a
t1

t2



is of the forml(t1 )l(t2 ).

The following definition captures this intuition in categorical terms.

Definition 2.5 A tree function l : DA → DB is said to be (relabeling) bottomup if it is a morphism of coalgebras, as in:
Fl

F DA
O
π2
A × FO DA
−1
∼
= σA
DA

l

/ F DBO
π2
B × FO DB∼= σ −1/ DB B(4)c

Lemma 2.6 For a TT A × F X → B × X, the induced tree function TF (c) :DA → DB is bottom-up.
⊓⊔
Now we can define the three semantic domains appearing in (3). We write:– LBeh(A, B) for the set of maps DA → B, i.e., LBeh(A, B) = HomC (DA, B);– TF(A, B) for the set of maps DA → DB, i.e., TF(A, B) = HomC (DA, DB);
– TF↑ (A, B) ֒→ TF(A, B) for the subset of bottom-up maps DA → DB.
These three sets are considered as discrete categories. This enables us to consider
behavior mappings as functors from TT(A, B), in a degenerate fashion.
Lemma 2.7 The mappings LBeh and TF in Def. 2.3 extend to functors
LBeh : TT(A, B) → LBeh(A, B)

and

TF : TT(A, B) → TF(A, B) .

The functor TF factors through the embedding TF↑ (A, B) ֒→ TF(A, B).

⊓⊔

A realization functor Real : LBeh(A, B) → TT(A, B) is defined to send a
local behavior k : DA → B to the TT hk, DAi ◦ σA : A × F DA → B × DA.
This TT has a canonical state space, namely the set DA of all A-trees; in all
but degenerate cases, this state space is infinite. In fact Real yields the initial
realization and we get a behavior-realization adjunction in the spirit of [3].
Theorem 2.8 We have Real ⊣ LBeh, and since the category LBeh(A, B) is
discrete, this adjunction is actually a coreflection.
Proof. The statement is equivalent to the following. For a given local behaviork
DA → B, the realization Real(k) is the initial one among those which yield k asctheir LBeh behavior. Let A × F X → B × X be one of such TTs. The following
fact is shown by diagram chasing.
f

DA → X is a morphism of TTs from Real (k) to c if and only if hk, f i isan algebra homomorphism from the initial algebra σA to c ◦ (A × F π2 ) :A × F (B × X) → B × X.
Initiality of σA yields existence and uniqueness of such f , hence the initiality ofReal (k).
⊓⊔Next we shall establish an isomorphism between the two (local and tree function) behaviors, which we already discussed in the introduction. By Lemma 2.7,
Theorems 2.8 and 2.9 we have established the situation (3).
Theorem 2.9 The following composite W of functors is an isomorphism.


Real
TF
W = LBeh(A, B) −→ TT(A, B) −→ TF↑ (A, B)
Proof. The functor W sends a map k : DA → B to its coKleisli extension Dk ◦
δA : DA → DDA → DB. Let E : TF↑ (A, B) → LBeh(A, B) be the functor
carrying a bottom-up tree function l : DA → DB to ǫB ◦ l : DA → DB → B.
Thus E post-composes the tree function with extraction of the root label. ThenE ◦ W = Id because D is a comonad. For the opposite direction W ◦ E = Id,
bottom-upness is crucial.
⊓⊔

3

Rebranching Bottom-Up Tree Transducers

In this section we pursue the same idea as in the previous section, but for amore general class of bottom-up TTs, namely rebranching TTs. They no longer
preserve tree shapes, in fact they take trees of one branching type F to trees of a
possibly different branching type G, by reorganizing the branching of any nodeof the input tree from type F to type G.
We shall establish the following situation, which is almost the same as (3).
The main differences are: 1) the fixed parameters are now functors F, G forbranching types (instead of sets A, B of labels) meaning that we consider transformations of F -branching trees (F -trees for short) into G-trees; 2) the isomorphism between LBeh and TF↑ is not present.
TT(F, G) ZZZZZTFZZZZZ,
IReal ⊣ LBeh
d2 2 TF↑ (F, G)
d
d
d
d
d
d
dd
W
LBeh(F, G)/ TF(F, G)(5)

A novelty in this section is what we call “placeholders-via-naturality”. TTs
are conventionally systems of transition rules in which placeholders appear explicitly. In our categorical approach, they have quite a different presentation as
natural transformations (Def. 3.1). The correspondence between these seemingly
different notions will be described via the Yoneda lemma.
Let us first present the conventional notion of rebranching TTs. Let Σ and∆ be universal-algebraic signatures: we consider transformations of Σ-trees into∆-trees. Conventionally, a rebranching TT with a state space X is presented as
an element of the set


`
Q
|f|
(6)
−→ ( g∈∆ |f||g| ) × X .
f∈Σ X

It is illustrative to think of the cardinality |f| as a set {y1 , . . . , y|f| } of placeholders,of the set X |f| on the left as the set of graphs of functions from |f| to X and of theset |f||g| on the right as the set of length-|g| lists over |f|. For example, assume thatsome f is binary and a TT (6) carries (f, ((y1 , x1 ), (y2 , x2 ))) to ((g, (y2 , y1 , y1 )), x)
with a ternary g. This is understood graphically as follows.
f
x1 y1

x

7−→
y2

x2 y2

g
y1

(7)
y1

This is “bottom-up” because the state x is determined by the states x1 , x2
assigned to its successor nodes. Placeholders y1 , y2 designate how the subtrees
are reorganized in the bottom-up construction of a tree function behavior l.
f
t1

g

l

7−→
t2

l(t2 )l(t1 )l(t1 )The name rebranching comes from the fact that, on the right hand side of (7),exactly one function symbol occurs, so that a layer in a input tree is sent toexactly one layer of the output tree, and only the branching within the layerchanges. In Sect. 4 we will abandon also this requirement.
We now present our categorical definition of TTs.
Definition 3.1 A (rebranching bottom-up) TT is a natural transformationγ
F ( × X) =⇒ G × X between set functors. The set X is called its state space.
γδA morphism of TTs from F ( × X) =⇒ G × X to F ( × Y ) =⇒ G × Y isa function f : X → Y satisfying (G × f ) ◦ γ = δ ◦ F ( × f ). We denote byTT(F, G) the category of TTs and morphisms.
This categorical formulation may seem very different from the conventional
one (6). But somewhat remarkably the two agree for functors arising from traditional signatures.
signatures Σ, ∆: namely, F =` by universal-algebraic` Let F,|f|G be induced
|g|
)
and
G
=
)
.
The
followingcalculation shows the equiva(
(
f∈Σ
g∈∆
lence between (6) and Def. 3.1 via the Yoneda lemma.

Q
`
|f|
→ ( g∈∆ |f||g| ) × Xf∈Σ XX |f|
Q= f∈Σ G|f| × X
by definition of GQ|f| 
by Yoneda= f∈Σ ( )|f| ⇒ (G × X)X

Q
|f|
|f|
= f∈Σ ( × X) ⇒ G × X
by × X |f| ⊣ ( )X

`
|f|
⇒G ×X
=
f∈Σ ( × X)
= F ( × X) ⇒ G × X
by definition of F .
On the third line the set of placeholders (the first occurrence of |f| on the secondline) is absorbed into naturality, hence “placeholders-via-naturality”.

We now proceed to the tree function behavior of our TTs. The tree functions
here take F -trees to G-trees. Going slightly more general than necessary for thissection (but preparing for the next), we write F ∗ Z for the carrier of the initial(Z + F )-algebra, i.e., the set of unlabelled F -trees with variables (graft-points)∼=from a set Z. For the algebra structure F (F ∗ Z) →F ∗ Z we write αF
Z . F -trees
simpliciter (i.e., those without variables) arise as the special case F ∗ 0. The set(or discrete category) of tree functions F ∗ 0 → G∗ 0 will be denoted by TF(F, G).
γDefinition 3.2 A TT F ( × X) ⇒ G × X induces its tree-function behavior
TF (γ) ∈ TF(F, G) by the following algebra initiality diagram.
F F ∗ 0 _ _ _ _ _ _/ F (G∗ 0 × X)
 γG∗ 0∼αF
GG∗ 0 × X
0 =∼=  αGγe0 ×X
F ∗ 0 _ _ _ _ _ _ _/ G∗ 0 × X π1/ G∗ 0TF (γ)(8)

Here again, similarly to the situation for relabelings, not all the tree functions
F ∗ 0 → G∗ 0 are induced by a TT but only “bottom-up” ones are.
l

Definition 3.3 A tree function F ∗ 0 → G∗ 0 is said to be (rebranching) bottomω
up, if there exists a natural transformation called a witness F ( × F ∗ 0) =⇒ G
which makes the following diagram commute.
Gl

GFO ∗ 0ωF ∗ 0F (F ∗ 0 × F ∗ 0)O
F hid, idi
F F ∗0−1 O ∼
(αF
)
=
0
F ∗0

/ GG∗ 0
O
−1
∼
= (αG
0 )

(9)

/ G∗ 0l

By TF↑ (F, G) we denote the set (discrete category) of tree functions F ∗ 0 → G∗ 0
which are rebranching bottom-up. We have TF↑ (F, G) ֒→ TF(F, G).
Witnesses are not necessarily unique. A simple example is the tree functionthat sends an unlabelled binary tree to the unlabelled unary tree of its height.
γ

Lemma 3.4 For a TT F ( × X) ⇒ G × X, the induced tree function TF (γ) :F ∗ 0 → G∗ 0 is (rebranching) bottom-up.
Proof. Take ω = π1 ◦ γ ◦ F ( × (π2 ◦ γe)), where γ
e is from (8).
γ⊓⊔Definition 3.5 Given a TT F ( × X) ⇒ G × X, we define its local behavior
ω
LBeh(γ) to be F ( × F ∗ 0) ⇒ G from the proof of Lemma 3.4.

In Sect. 2 we observed that a local behavior DA → B is a coKleisli map.
This is also the case in this section. In fact, the mapping F 7→ F (F ∗ 0 × )extends to a comonad on the functor category [Sets, Sets], so that any naturalωtransformation F (F ∗ 0 × ) ⇒ G is therefore a coKleisli map from F to G. We
denote their set (discrete category) by LBeh(F, G).
Lemma 3.6 The operations LBeh and TF in Definitions 3.5 and 3.2 extend tofunctors LBeh : TT(F, G) → LBeh(F, G) and TF : TT(F, G) → TF↑ (F, G).
⊓⊔
Theorem 3.7 We have an adjunction (actually a coreflection) Real ⊣ LBeh,
where the realization functor for local behaviors Real : LBeh(F, G) → TT(F, G)ωsends a local behavior F ( × F ∗ 0) ⇒ G to a TT with Z-components
F (Z × F ∗ 0)hωZ ,F π2 i→

GZ × F F ∗ 0

GZ×αF
0

→

GZ × F ∗ 0 .

Real

⊓
⊔

TF

Proposition 3.8 The functor W = ( LBeh(F, G) → TT(F, G) → TF↑ (F, G) )is an epimorphism.
⊓⊔

4

Relayering Bottom-Up Tree Transducers

In this section we will consider our most general class of bottom-up tree transformations, which can send a layer in an input tree to a truncated subtree inthe output tree. For reasons of space, we must be fairly brief. We establish thesame situation as in the previous section, except that we do not have to single
out any condition of bottom-upness of tree functions. As we do not restrict state
spaces to be finite, any tree function can arise as the behavior of a relayeringbottom-up TT.
A categorical presentation of relayering TTs is obtained much like that ofrebranching TTs in Sect. 3, using “placeholders-via-naturality”. We recall thenotation F ∗ Z for the carrier of the initial (Z + F )-algebra. It is now importantfor us that the functor F ∗ carries a monad structure, in particular a multiplication µF : F ∗ F ∗ ⇒ F ∗ that can be defined via initiality.
Definition 4.1 A (relayering bottom-up) TT is a natural transformation of theγform F ( × X) =⇒ G∗ × X. Such TTs form a category TT(F, G) together
with an obvious notion of morphism.
The difference from Def. 3.1 is that we have G∗ instead of G in the codomain.
This corresponds to allowing terms over placeholders rather than applicationsof single function symbols in the right-hand sides of transition rules (7): forexample,
f
x1 y1

x2 y2

x

7−→

g′
y2

y1
y1

(10)

g
y2

γ

Definition 4.2 A TT F ( × X) ⇒ G∗ × X induces its tree-function behavior
TF (γ) : F ∗ 0 → G∗ 0 by the following algebra initiality diagram.
F F ∗ 0 _ _ _ _ _ _/ F (G∗ 0 × X)
 γG∗ 0
∗ ∗
∼
αF
=
G
G
0
×X
0
 µG

γ
e
0 ×X
F ∗ 0 _ _ _ _ _ _ _/ G∗ 0 × X π1/ G∗ 0TF (γ)(11)

For relayering TTs any tree function is bottom-up: a tree function l : F ∗ 0 →G 0 is realized by the TT whose Z-component is
∗

Fπ

αF

hl,F ∗ 0i0
F ∗ 0 −→ G∗ 0 × F ∗ 0
F (Z × F ∗ 0) −→2 F F ∗ 0 −→G∗ !×F ∗ 0−→

G∗ Z × F ∗ 0 ,where ! denotes the empty map 0 → Z. This realization however does not givean adjunction.
The local behavior induced by a TT γ is a natural transformation LBeh(γ) :F ( × F ∗ 0) ⇒ G∗ . Such natural transformations are biKleisli maps of a distributive law of the comonad F 7→ F ( × F ∗ 0) of the previous section over thefree monad delivering monad F 7→ F ∗ . We denote their set (discrete category)by LBeh(F, G).
For a realization functor for local behaviors Real : LBeh(F, G) → TT(F, G)
we obtain an adjunction (actually a coreflection) Real ⊣ LBeh, similarly to therebranching case.

5

Allowing Parameters to VaryIn Sect. 2 we saw the fundamental diagram (3) relating tree transducers, local
behaviors and tree functions. In that diagram we kept the alphabets A, B fixed.
In this section we shall identify additional mathematical structure that emerges
by allowing the alphabets to vary. For this purpose we utilize the notion of
Arrows—as introduced by Hughes [5], but described more abstractly as monoids
in categories of bifunctors in [4]—and also Freyd categories (or as fibered spans).
Arrows were devised for the purpose of reconciling impure “structured computations” with purely functional computation. Commonly an Arrow A(−, +)is a bifunctor Cop × C → Sets: in this case A(A, B) is the set of structured
computations (of the kind designated by A) from the type A to B. Since wewant to consider TT(A, B) of relabeling transducers as a category of structured computation, we shall use Cat-valued Arrows instead: these are bifunctors
Cop ×C → Cat with additional structure arr and >>>.3 The notion of Cat-valued
Arrows are in fact the same thing as Freyd categories [8] (enriched by Cat in3

For the sake of brevity, we ignore here the compatibility with products which isusually given by an operation first.

a suitable way): this was shown in [7]. Moreover, a Cat-valued Arrow—as a bifunctor Cop ×C → Cat—induces a fibered span via the generalized Grothendieckconstruction (see, e.g., [6, Ch. 9]).
In the remainder of the section we shall parameterize the diagram (3) andobtain the corresponding situation for Arrows. In this case we have C = Sets as
the base category. We do this only for relabelings due to limited space.
The bifunctor TT(−, +) is such that TT(A, B) is the category of relabelings
from A-trees to B-trees. It sends a morphism (α, β) : (A, B) → (C, D) in Cop ×
C—hence α : C → A and β : B → D—to the functor TT(A, B) → TT(C, D)
given as follows. On objects:


β×F X
c
α×F X
c
A × FX → B × X −7 → C × F X −→ A × F X → B × F X −→ D × F X

and on morphisms it is the identity.
>>>
arr
Interestingly, there is also a monoid structure TT ⊗ TT → TT ← I on
the bifunctor TT—this makes TT an Arrow (see [4]). We shall describe it a bitcdmore concretely. For TTs A × F X −→ C × X and C × F Y −→ B × Y withmatching output/input, their composition c >>> d has X × Y as its state space:
A × F (X × Y )hF π1 ,F π2 i

−→

d

c

A × F X × F Y −→ C × X × F Y −→ B × X × Y .
f

The operation arr for TT carries a morphism A → B in C to a TT with a trivial∼fπ=state space 1: namely A × F 1 →1 A → B → B × 1. It is easy to check that arr
and >>> satisfy the appropriate naturality and monoid equations.
Just like TT(−, +) carries the structure of an Arrow we can identify similar
structure on LBeh(−, +), TF(−, +) and TF↑ (−, +). It then turns out that the
diagram (3), but then without the fixed alphabets, also exists in parameterized
form, even with preservation of this Arrow structure. For example, the behaviorrealization adjunction is now described as an adjunction between Arrows.
Theorem 5.1 We have the following situation in the 2-category Arrow.
TT(−, +)I
Real ⊣ LBeh
LBeh(−, +)TF*
TF↑ (−, +) 4

/ TF(−, +)

(12)

W
⊓
⊔

6

Conclusions and Future Work

We have given a categorical account of three classes of bottom-up tree transformations. Notably, we have generalized traditional signatures to functors andreplaced traditional descriptions of TTs based on placeholder notation with natural transformations, winning simplicity and clarity. In future work, we will
elaborate on our basic picture in a form where, in addition to “extensional” tree

functions, we also have “intensional” tree functions, capable of tracking which
node in an input tree goes where in the output tree. And we will also include
top-down computations, using the theory of containers, as well as bottom-up
and top-down computations with look-ahead.
Acknowledgement T. Uustalu was partially supported by the Estonian Science
Foundation grants No. 5567 and 6940.

References
1. Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., andTommasi, M.: Tree automata techniques and applications. Book draft (2005)
2. Engelfriet, J.: Bottom-up and top-down tree transformations—a comparison.
Math. Syst. Theory 9(3) (1975) 198–231
3. Goguen, J.: Minimal realization of machines in closed categories. Bull. Amer.
Math. Soc. 78(5) (1972) 777–783
4. Heunen, C., Jacobs, B.: Arrows, like monads, are monoids. In Brookes, S., Mislove,M., eds.: Proc. of 22nd Conf. on Math. Found. of Program. Semantics, MFPS-XXII,
Vol. 158 of Electr. Notes in Theor. Comput. Sci., Elsevier (2006) 219–236
5. Hughes, J.: Generalising monads to arrows. Sci. of Comput. Program. 37(1–3)(2000) 67–111
6. Jacobs, B.: Categorical Logic and Type Theory. North Holland (1999)
7. Jacobs, B., Hasuo, I.: Freyd is Kleisli, for arrows. In McBride, C., Uustalu, T., eds.:
Proc. of Wksh. on Mathematically Structured Functional Programming, MSFP ’06,
Electron. Wkshs. in Comput. Sci., BCS (2006)
8. Power, J., Robinson, E.: Premonoidal categories and notions of computation. Math.
Struct. in Comput. Sci. 7(5) (1997) 453–468
9. Rosebrugh, R. D., Sabadini, N., Walters, R. F. C.: Minimal realization in bicategories of automata. Math. Struct. in Comput. Sci. 8(2) (1998) 93–116
10. Rounds, W. C.: Mappings and grammars on trees. Math. Syst. Theory 4(3) (1970)
257–287
11. Thatcher, J. W.: Generalized sequential machine maps. J. Comput. Syst. Sci. 4(4)(1970) 339–367
12. Uustalu, T., Vene, V.: Comonadic functional attribute evaluation. In van Eekelen,M., ed.: Trends in Functional Programming 6, Intellect (2007) 145–162
13. Uustalu, T., Vene, V.: The essence of dataflow programming. In Horváth, Z., ed.:
Revised Selected Lectures from 1st Central European Functional Programming
School, CEFP 2005, Vol. 4164 of Lect. Notes in Comput. Sci., Springer (2006)
135–167
14. Uustalu, T., Vene, V.: The dual of substitution is redecoration. In Hammond, K.,
Curtis, S., eds.: Trends in Functional Programming 3, Intellect (2002) 99–110