# Macros with binary trees as arguments

I would like to have some macros which have binary trees as arguments. For the purpose of these macros, a binary tree is either root or it is {branch1}{branch2} for two binary trees branch1 and branch2 and these macros should be defined recursively. My thought was that such a macro would look like

\newcommand{\macro}[1]{\bintree@induction{#1}{\macro@root{#1}}{\macro@branches{#1}}
\newcommand{\macro@root}[1]{%describes what to do in the case of a root
<some code>}
\newcommand{\macro@branches}[1]{%describes what to do in the case of branches.
%Can use {\bintree@branchone #1} and {\bintree@branchtwo #1}
%here to access the branches
<some code>}

\newcommand{\bintree@induction}[3]{
\ifx{}{\bintree@root #1}
%the binary tree is of the form {branch1}{branch2}
#3
\else
%the binary tree is of the form root
#2
\fi}

%when it finds two branches, it gobbles both of them
\newcommand{\bintree@root}{\@ifnextchar\bgroup{\@bintree@root}{}}
\newcommand{\@bintree@root}[1]{\@ifnextchar\bgroup{\@gobble}{#1}}

%To define the macro recursively, we will usually need to handle the two
%branches. Here's the mechanism that selects them.
%This selects the first branch if there is one; all else it does is irrelevant
\newcommand{\bintree@branchone}{\@ifnextchar\bgroup{\@bintree@branchone}{}}
\newcommand{\@bintree@branchone}[1]{#1\@gobble}

%Gobbles the first branch, takes the second out of its braces
\newcommand{\bintree@branchtwo}{\@ifnextchar\bgroup{\@bintree@branchtwo}{}}
\newcommand{\@bintree@branchtwo}[1]{\@ifnextchar\bgroup{\@@bintree@branchtwo}{}}
\newcommand{\@@bintree@branchtwo}[1]{#1}


But this doesn't work. I believe it's because \bintree@root #1 isn't truly empty in the case the argument #1 is of the form {branch1}{branch2}. How can I accomplish this? Below I attach a MWE where I need this. There I've found some workarounds, but I don't see how I can define a macro by induction on binary trees in general in a similar way. So my question is: how I can do the macro \bintree@induction correctly.

If anybody knows of a different approach to this problem I'd be very pleased to know about that too. I have the feeling my code is very clumsy with the overuse of all the @'s.

\documentclass{article}
\usepackage{amsmath}
\usepackage{comment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% General induction on binary trees.
%%%% This is used for the macro \jhom@dom@wk below only. For the others
%%%% I found an ad hoc method to get things working...

\makeatletter
\newcommand{\bintree@induction}[3]{
\ifx{}{\bintree@root #1}
%the binary tree is of the form {branch1}{branch2}
#3
\else
%the binary tree is of the form root
#2
\fi}

%when it finds two branches, it gobbles both of them
\newcommand{\bintree@root}{\@ifnextchar\bgroup{\@bintree@root}{}}
\newcommand{\@bintree@root}[1]{\@ifnextchar\bgroup{\@gobble}{#1}}

%To define the macro recursively, we will usually need to handle the two
%branches. Here's the mechanism that selects them.
%This selects the first branch if there is one; all else it does is irrelevant
\newcommand{\bintree@branchone}{\@ifnextchar\bgroup{\@bintree@branchone}{}}
\newcommand{\@bintree@branchone}[1]{#1\@gobble}

%Gobbles the first branch, takes the second out of its braces
\newcommand{\bintree@branchtwo}{\@ifnextchar\bgroup{\@bintree@branchtwo}{}}
\newcommand{\@bintree@branchtwo}[1]{\@ifnextchar\bgroup{\@@bintree@branchtwo}{}}
\newcommand{\@@bintree@branchtwo}[1]{#1}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\jterm}[3]{#1 \vdash #3:#2}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%% To get a feeling of how the command works, here are a few examples.
%%%% \ctxext{A}{B} will print A.B
%%%% \ctxext{{A}{B}}{C} will print (A.B).C
%%%% \ctxext{{{A}{B}}{C}}{{D}{E}} will print ((A.B).C).(D.E)

\makeatletter
\newcommand{\ctxext}[2]{\@ctxext@ctx #1.\@ctxext@type #2}
\newcommand{\@ctxext}{\@ifnextchar\bgroup{\@@ctxext}{}}
\newcommand{\@ctxext@ctx}{\@ifnextchar\ctxext{\@ctxext@nested}{\@ifnextchar    \ctxwk{\@ctxwk@nested}{\@ctxext}}}
\newcommand{\@ctxext@type}{\@ifnextchar\ctxext{\@ctxext@nested}{\@ifnextchar\subst{\@subst@nested}{\@ctxext}}}
\newcommand{\@@ctxext}[1]{\@ifnextchar\bgroup{\@ctxext@parens{#1}}{#1}}
\newcommand{\@ctxext@parens}[2]{(\ctxext{#1}{#2})}
\newcommand{\@ctxext@nested}[3]{\@ctxext@parens{#2}{#3}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%

\makeatletter
\newcommand{\ctxwk}[2]{\langle\@ctxwk@act #1\rangle\@ctxwk@pass #2}
\newcommand{\@ctxwk}{\@ifnextchar\bgroup{\@@ctxwk}{}}
\newcommand{\@@ctxwk}[1]{\@ifnextchar\bgroup{\ctxwk{#1}}{#1}}
\newcommand{\@ctxwk@act}{\@ctxwk}
\newcommand{\@ctxwk@pass}{\@ifnextchar\ctxext{\@ctxext@nested}{\@ifnextchar\subst{\@subst@nested}{\@ctxwk}}}
\newcommand{\@ctxwk@parens}[2]{(\ctxwk{#1}{#2})}
\newcommand{\@ctxwk@nested}[3]{\@ctxwk@parens{#2}{#3}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\makeatletter
\newcommand{\jhom}[3]{\jterm{\jhom@dom@ext{#1}}{\jhom@dom@wk{#1}{#2}}{#3}}

%%%% First define \jhom@dom@ext
\newcommand{\jhom@dom@ext}[1]{\@jhom@dom@ext #1}
\newcommand{\@jhom@dom@ext}{\@ifnextchar\bgroup{\@@jhom@dom@ext}{}}
\newcommand{\@@jhom@dom@ext}[1]{\@ifnextchar\bgroup{\@@@jhom@dom@ext{#1}}{#1}}
\newcommand{\@@@jhom@dom@ext}[2]{\ctxext{\jhom@dom@ext@nested #1}{\ctxwk{\jhom@dom@ext{#1}}{\jhom@dom@ext@nested #2}}}

%%%% The later occurences of context extension should be with parentheses
\newcommand{\jhom@dom@ext@nested}{\@ifnextchar\bgroup{\@jhom@dom@ext@nested}{}}
\newcommand{\@jhom@dom@ext@nested}[1]{\@ifnextchar\bgroup{\@@jhom@dom@ext@nested{#1}}{#1}}
\newcommand{\@@jhom@dom@ext@nested}[2]{\@ctxext@parens{\jhom@dom@ext@nested #1}{\ctxwk{\jhom@dom@ext{#1}}{\@jhom@dom@ext@nested #2}}}

%%%% Now define \jhom@dom@wk. Here I don't see how I can do something similar as
%%%% before. Hence try the more general approach that doesn't really work...
\newcommand{\jhom@dom@wk}[2]{\bintree@induction{#1}{\jhom@dom@wk@root{#1}{#2}}
{\jhom@dom@wk@branches{#1}{#2}}}
\newcommand{\jhom@dom@wk@root}[2]{\ctxwk{\bintree@root #1}{#2}}
\newcommand{\jhom@dom@wk@branches}[2]{\ctxwk{\jhom@dom@ext{\bintree@branchone #1}}{\jhom@dom@wk{\bintree@branchtwo #1}{#2}}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
The following output

\begin{align*}
& \jhom{\Gamma}{\Delta}{f}\\
& \jhom{{\Gamma_1}{\Gamma_2}}{\Delta}{f}\\
& \jhom{{{\Gamma_{11}}{\Gamma_{12}}}{\Gamma_2}}{\Delta}{f}\\
& \jhom{{\Gamma_1}{{\Gamma_{21}}{\Gamma_{22}}}}{\Delta}{f}
\end{align*}
should be the same as
\begin{align*}
& \jterm{\Gamma}{\Delta}{f}\\
& \jterm{\ctxext{\Gamma_1}{\ctxwk{\Gamma_1}{\Gamma_2}}}{\ctxwk{\Gamma_1}{{\Gamma_2}{\Delta}}}{f}\\
& \jterm{\ctxext{{\Gamma_{11}}{\ctxwk{\Gamma_{11}}{\Gamma_{12}}}}
{\ctxwk{\ctxext{\Gamma_{11}}{\ctxwk{\Gamma_{11}}{\Gamma_{12}}}}
{\Gamma_2}}}
{\ctxwk{\ctxext{\Gamma_{11}}{\ctxwk{\Gamma_{11}}{\Gamma_{12}}}}{{\Gamma_2}{\Delta}}}{f}\\
& \jterm{\ctxext{\Gamma_1}{\ctxwk{\Gamma_1}{\ctxext{\Gamma_{21}}{\ctxwk{\Gamma_{21}}{\Gamma_{22}}}}}}{\ctxwk{\Gamma_1}{{\ctxext{\Gamma_{21}}{\ctxwk{\Gamma_{21}}{\Gamma_{22}}}}{\Delta}}}{f}
\end{align*}

\end{document}


The following is perhaps too simple to be very robust:

\def\ctxext#1#2{\@ctxext#1.\@ctxext#2}
\def\@ctxext{\@ifnextchar\bgroup{\@@ctxext}{}}
\def\@@ctxext#1#2{(\@ctxext#1.\@ctxext#2)}


Then

\ctxext{A}{B}

\ctxext{{A}{B}}{C}

\ctxext{{{A}{B}}{C}}{{A}{D}}


produces

Any errors in input tend to produce either infinite recursion or "file ended while scanning use of \@@cxext.

• Simple solutions are usually the best. Do you have anything specific in mind when you say it might not be very robust? Another remark I'd like to make is that I was hoping for a more general approach. This works well with the \ctxext command (and also with the \ctxwk macro in my MWE) but when the macro is more involved (as with the macro \jhom@dom@wk in the MWE) I don't see how I can do it in a similar way. – Egbert Nov 4 '13 at 15:39