Und fürs Minimalbeispiel hats geklappt, weil ich da einfach von bloodworks code ausgegangen bin.
Danke dir, damit ist der rechte Abstand verschwunden

Dennoch habe ich noch eine kleine Unsauberheit in diesem Beispiel und zwei allgemeinere Fragen:
1. Ich habe jetzt mein Frame wie folgt abgeändert und benutze das lstset von bloodworks.
\lstset{ basicstyle=\ttfamily, numbers=left, language=Haskell, commentstyle=\itshape\color{darkgray}, keywordstyle=\bfseries\color{red}, stringstyle=\color{green}, breaklines=false, breakautoindent=true, columns=flexible, frame=single, captionpos=b, } ... \begin{frame}[fragile] \frametitle{Size-Change Graphs} \begin{itemize} \item Help us to keep track of decreasing data values \item Capture information about one function call \end{itemize} Examples: \begin{columns} \column[tt]{0.5\textwidth} \begin{beamercolorbox}[ht=3.75cm, rounded=true, shadow=true]{block body} \centering %fügt keinen Abstand ein, \begin{center} schon \begin{lstlisting}[mathescape=true, linewidth=\textwidth, numbers = none, frame = none, basicstyle=\small] f(a,b) = ... else 1:g(a,b-1,a) \end{lstlisting} \scalebox{0.8}{ \begin{tikzpicture} \tikzstyle{every state}=[minimum size=10pt,fill=white,text=black, node distance=1cm] \tikzstyle{every pin edge}=[<-,shorten <=1pt] \node[state,shape=circle] (a) {$a$}; \node[state,shape=circle] (b) at (0, -1.5) {$b$}; \node[state,shape=circle] (c) at (1.5,0.75) {$c$}; \node[state,shape=circle] (d) at (1.5,-0.75) {$d$}; \node[state,shape=circle] (e) at (1.5,-2.25) {$e$}; \path[->] (a) edge node[above] {$\downarrow$} (c) (a) edge node[above, very near end] {$\downarrow$} (e) (b) edge node[above, near end] {$\downarrow$} (d) ; \end{tikzpicture}} \end{beamercolorbox} \column[tt]{0.5\textwidth} \begin{beamercolorbox}[ht=3.75cm, rounded=true, shadow=true]{block body} \centering \begin{lstlisting}[mathescape=true, linewidth = \textwidth, numbers = none, frame = none, basicstyle=\small] g(c,d,e) = ... else 2:g(c,d-1,e$\cdot$c) \end{lstlisting} \scalebox{0.8}{ \begin{tikzpicture} \tikzstyle{every state}=[minimum size=16pt,fill=white,text=black, node distance=1.5cm] \tikzstyle{every pin edge}=[<-,shorten <=1pt] \node[state,shape=circle] (c) {$c$}; \node[state,shape=circle] (d) [below of = c] {$d$}; \node[state,shape=circle] (e) [below of = d] {$e$}; \node[state,shape=circle] (c1)[right of = c] {$c$}; \node[state,shape=circle] (d1)[right of = d] {$d$}; \node[state,shape=circle] (e1) [right of = e] {$e$}; \path[->] (c) edge node[above] {$\downarrow$} (c1) (d) edge node[above] {$\downarrow$} (d1) ; \end{tikzpicture}} \end{beamercolorbox} \end{columns} \begin{itemize} \item hier ist ein Item \item und hier noch eines \end{itemize} \end{frame}

Es ist also fast so, wie ich es gerne hätte! Das einzige, was mich wundert, ist, dass das linke Listing nicht zentriert erscheint und beide Listings auf leicht unterschiedlicher Höhe sind.
2. Wenn Umgebungen wie \begin{center}, \begin{itemize} vertikalen Abstand einfügen, wie kriege ich diesen Abstand wieder weg? Das Problem hatte ich nämlich schon öfter.
3. Warum richten sich die beiden blocks unten aneinander aus, wenn ich zB eine Box 3cm und die andere 5cm groß mache? Sollten die sich nicht durch das der columns Umgebung oben ausrichten?
Gruß,
Guenter