\documentclass[a4paper]{article}

\usepackage{xy}
% For dvips driver, uncomment the next.
% \xyoption{dvips}
\usepackage{ifthen}

\title{Nice trees in XY-pic}

\author{Beno{\^\i}t Valiron}


%%----------------------------------------------------------------------
%% MACROS FOR TREES
%% Version: 0.2
%% Date: June 4, 2010
%% Copyright: Benoit Valiron <benoit.valiron@monoidal.net>
%%
%% Require packages : xy, ifthen
%% 


% height of each level (if you choose positive numbers you reverse
% the direction of the tree)
\def\btheight{-4ex}


% Some definitions...
\def\bentreeroot#1{\begin{array}{c}\xy\save(0,0)*{}="a"#1{a}%
\restore\endxy\end{array}}
\def\bentreenodeonethree#1#2#3#4#5{\save
  "#5";
  "#5"+<#1,\btheight>*{}="#5a"**\dir{-},
  "#5"+<#2,\btheight>*{\cdots}**\dir{-},
  "#5"+<#3,\btheight>*{\cdots}**\dir{-}
  #4{#5a}
  \restore}
\def\bentreenodeonetwo#1#2#3#4{\save
  "#4";
  "#4"+<#1,\btheight>*{}="#4a"**\dir{-},
  "#4"+<#2,\btheight>*{\cdots}**\dir{-}
  #3{#4a}
  \restore}  
\def\bentreenodeoneone#1#2#3{\save
  "#3";
  "#3"+<#1,\btheight>*{}="#3a"**\dir{-},
  #2{#3a}
  \restore}  
\def\bentreeleaf#1#2#3{\save
  "#3"*!#1{#2}
  \restore}

\def\bentreenodethree#1#2#3#4#5#6#7{\save
  "#7";
  "#7"+<#1,\btheight>*{}="#7a"**\dir{-},
  "#7"+<#2,\btheight>*{}="#7b"**\dir{-},
  "#7"+<#3,\btheight>*{}="#7c"**\dir{-}
  #4{#7a}
  #5{#7b}
  #6{#7c}
  \restore}
\def\bentreenodetwo#1#2#3#4#5{\save
  "#5";
  "#5"+<#1,\btheight>*{}="#5d"**\dir{-},
  "#5"+<#2,\btheight>*{}="#5e"**\dir{-}
  #3{#5d}
  #4{#5e}
  \restore}

% A few shortcuts

\def\btroot{\bentreeroot}
\def\btleaf{\bentreeleaf}
\def\btdots{\btleaf{U}{\cdots}}
\def\bt#1node{\ifthenelse{#1=1}%
{\bentreenodeoneone}{\ifthenelse{#1=2}%
{\bentreenodetwo}{\ifthenelse{#1=3}%
{\bentreenodethree}{\ifthenelse{#1=0}%
{\bentreeleaf}{~}}}}}


%% 
%% END MACROS FOR TREES  
%% ----------------------------------------------------------------------




\begin{document}

\maketitle



  This is a small wrapping around xypic to write some trees.
  
  
  \section{Result}
  
  One can do it directly
  \[
  \left(\lambda y.\left(
  \begin{array}{c}\xy
    (0,0)*{}="a";
    "a"+<3ex,-4ex>*{\cdots}**\dir{-},
    "a"+<-3ex,-4ex>*{}="b"**\dir{-},
    "a"+<-9ex,-4ex>*{\cdots}**\dir{-},
    "b";
    "b"+<-4ex,-4ex>*{\cdots}**\dir{-},
    "b"+<10ex,-4ex>*{\cdots}**\dir{-},
    "b"+<3ex,-4ex>*{\lambda x.x}**\dir{-},
    \endxy
  \end{array}
  \right)\right)\lambda z.z
  \]
  %
  Or one can use some definitions, to make it more convenient to use:
  \begin{itemize}
  \item {\tt {\verb+\+}btroot\{...\}} : the root
  \item {\tt {\verb+\+}bt1node\{displ\}\{...\}}: one node, with an horizontal
    displacement of {\tt displ} with respect to the parent node.
  \item {\tt {\verb+\+}bt2node\{displ\}\{displ\}\{...\}\{...\}}: for 2 children nodes
  \item {\tt {\verb+\+}bt3node\{displ\}\{displ\}\{displ\}\{...\}\{...\}\{...\}}:
    for 3 nodes.
  \item {\tt {\verb+\+}btleaf\{U|UL|UR|D|DR|DL|D|R\}\{formula\}}: a node. The
    letter code stands for up, down, right or left (xy-notation), for
    adjusting the placement.
  \item {\tt {\verb+\+}btdots}: shortcut for ${\tt {\verb+\+}btleaf\{U\}\{{\verb+\+}cdots\}}$
  \end{itemize}
  One variable {\tt{\verb+\+}btheight} can be redefine using {\tt
    {\verb+\+}def{\verb+\+}btheight\{size\}}. It stands for the height
  between a parent and its children in the tree.
  
  %
  A first example :
  \[
  \left(
    % THE ROOT
    \btroot{
      % IT HAS 2 CHILDREN
      \bt2node{6ex}{-6ex}{
         % CHILD 1
        \btleaf{U}{\lambda x.x}
      }{ % CHILD 2
        \btdots % shortcut for \btleaf{U}{\cdots}
      }
    }
  \right)
    \qquad
  \left(
    \btroot{
      \bt3node{3ex}{9ex}{-3ex}{
         % CHILD 1
        \btleaf{U}{\cdots}
      }{ % CHILD 2
        \btdots % shortcut for \btleaf{U}{\cdots}
      }{ % CHILD 3
        \bt2node{-2ex}{7ex}{
           % SUBCHILD 1
          \btdots
        }{ % SUBCHILD 2
          \bt1node{1ex}{
            % ONLY ONE CHILD FOR bt1node
            \btleaf{U}{\lambda x.x}
          }
        }
      }
    }
  \right)
  \]
  %
  A more advanced one:
  \[
  \left(
      \btroot{
        \bt3node{-17ex}{3ex}{15ex}{
          \bt3node{5ex}{11ex}{-3ex}{
            \btdots
          }{
            \btdots
          }{
            \btleaf{U}{\lambda x.x}
          }
        }{
          % Note: You can change the height of the tree inline
          % Careful not to place a space between the \def and the rest
          % of the line.
          \def\btheight{-1ex}\bt2node{7ex}{-2ex}{
            \btdots
          }{
          % Now we can get wild
            \def\btheight{-5ex}\bt2node{-4ex}{10ex}{
              \def\btheight{-4ex}\bt3node{5ex}{1ex}{-3ex}{
                \btdots
              }{
                \btdots
              }{
                \bt2node{8ex}{-2ex}{
                  \btdots
                }{
                  \btleaf{U}{\lambda z.z}
                }
              }
            }{
              \def\btheight{-8ex}\bt3node{6ex}{1ex}{-3ex}{
                \btdots
              }{
                \btdots
              }{
                \bt2node{2ex}{-7ex}{
                  \btleaf{U}{\lambda e.e}
                }{
                  \btdots
                }
              }
            }
          }
        }{
          \btleaf{UL}{\lambda z.z}%
        }
      }%
 \right)
  \]
  A reversed tree (with positive {\tt{\verb+\+}btheight}):
  \[
  \btroot{
    \def\btheight{4ex}\bt2node{-6ex}{6ex}{
      \bt2node{-3ex}{3ex}{
        \btleaf{D}{\cdots}
      }{
        \btleaf{D}{\cdots}
      }
    }{
      \bt1node{4ex}{
        \btleaf{D}{\lambda x.x} % we use D instead of U. Try U to see !
      }
    }
  }
  \]
  
  
  \section{Installation}
  
  You merely need to copy the MACROS part of the tex-source of this
  file into your header. The (sparse) documentation sits inside the
  source, in the examples.
  
  
  \paragraph{Note:} This is all made in XY-pic. By default, everything
  is rendered in DVI. Although this is arguably more portable, you
  might want to use a PS driver:
  \begin{verbatim}
\usepackage[dvips]{xy}
\usepackage[dvitops]{xy}
  \end{verbatim}
  depending on the backend program you use to transform your DVI into
  PS.
  If you use the {\tt dvips} driver, to get a PDF you need to produce
  the following sequence of moves:
 \begin{verbatim}
$ latex myfile.tex
$ dvips [-t a4|letter|...] [-t landscape] -o myfile.ps myfile.dvi
$ ps2pdf myfile.ps
\end{verbatim}
  Talk to you local guru in case of problem...
  
\end{document}