






%
%
\makeatletter
\@ifundefined{lhs2tex.lhs2tex.sty.read}%
  {\@namedef{lhs2tex.lhs2tex.sty.read}{}%
   \newcommand\SkipToFmtEnd{}%
   \newcommand\EndFmtInput{}%
   \long\def\SkipToFmtEnd#1\EndFmtInput{}%
  }\SkipToFmtEnd

\newcommand\ReadOnlyOnce[1]{\@ifundefined{#1}{\@namedef{#1}{}}\SkipToFmtEnd}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{stmaryrd}
\DeclareFontFamily{OT1}{cmtex}{}
\DeclareFontShape{OT1}{cmtex}{m}{n}
  {<5><6><7><8>cmtex8
   <9>cmtex9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmtex10}{}
\DeclareFontShape{OT1}{cmtex}{m}{it}
  {<-> ssub * cmtt/m/it}{}
\newcommand{\texfamily}{\fontfamily{cmtex}\selectfont}
\DeclareFontShape{OT1}{cmtt}{bx}{n}
  {<5><6><7><8>cmtt8
   <9>cmbtt9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmbtt10}{}
\DeclareFontShape{OT1}{cmtex}{bx}{n}
  {<-> ssub * cmtt/bx/n}{}
\newcommand{\tex}[1]{\text{\texfamily#1}}	% NEU

\newcommand{\Sp}{\hskip.33334em\relax}


\newcommand{\Conid}[1]{\mathit{#1}}
\newcommand{\Varid}[1]{\mathit{#1}}
\newcommand{\anonymous}{\kern0.06em \vbox{\hrule\@width.5em}}
\newcommand{\plus}{\mathbin{+\!\!\!+}}
\newcommand{\bind}{\mathbin{>\!\!\!>\mkern-6.7mu=}}
\newcommand{\rbind}{\mathbin{=\mkern-6.7mu<\!\!\!<}}% suggested by Neil Mitchell
\newcommand{\sequ}{\mathbin{>\!\!\!>}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\usepackage{polytable}

%mathindent has to be defined
\@ifundefined{mathindent}%
  {\newdimen\mathindent\mathindent\leftmargini}%
  {}%

\def\resethooks{%
  \global\let\SaveRestoreHook\empty
  \global\let\ColumnHook\empty}
\newcommand*{\savecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\savecolumns[#1]}}
\newcommand*{\restorecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\restorecolumns[#1]}}
\newcommand*{\aligncolumn}[2]%
  {\g@addto@macro\ColumnHook{\column{#1}{#2}}}

\resethooks

\newcommand{\onelinecommentchars}{\quad-{}- }
\newcommand{\commentbeginchars}{\enskip\{-}
\newcommand{\commentendchars}{-\}\enskip}

\newcommand{\visiblecomments}{%
  \let\onelinecomment=\onelinecommentchars
  \let\commentbegin=\commentbeginchars
  \let\commentend=\commentendchars}

\newcommand{\invisiblecomments}{%
  \let\onelinecomment=\empty
  \let\commentbegin=\empty
  \let\commentend=\empty}

\visiblecomments

\newlength{\blanklineskip}
\setlength{\blanklineskip}{0.66084ex}

\newcommand{\hsindent}[1]{\quad}% default is fixed indentation
\let\hspre\empty
\let\hspost\empty
\newcommand{\NB}{\textbf{NB}}
\newcommand{\Todo}[1]{$\langle$\textbf{To do:}~#1$\rangle$}

\EndFmtInput
\makeatother
%

\begingroup\par\noindent
\haskellfont\(
\begin{pboxed}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{8}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\text{\hkw{module}}\;\text{UnVarGraph}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}({}\<[8]%
\>[8]{}\text{UnVarSet}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{emptyUnVarSet},\;\text{mkUnVarSet},\;\text{varEnvDom},\;{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{unionUnVarSet},\;\text{unionUnVarSets}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{delUnVarSet}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{elemUnVarSet},\;\text{isEmptyUnVarSet}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{UnVarGraph}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{emptyUnVarGraph}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{unionUnVarGraph},\;\text{unionUnVarGraphs}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{completeGraph},\;\text{completeBipartiteGraph}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{neighbors}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{},\;{}\<[8]%
\>[8]{}\text{delNode}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{})\;\text{\hkw{where}}{}\<[E]%
\ColumnHook
\end{pboxed}
\)\par\noindent\endgroup\resethooks
\\
\begingroup\par\noindent
\haskellfont\(
\begin{pboxed}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{7}{@{}>{\hspre}l<{\hspost}@{}}%
\column{9}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}c<{\hspost}@{}}%
\column{11E}{@{}l@{}}%
\column{14}{@{}>{\hspre}l<{\hspost}@{}}%
\column{20}{@{}>{\hspre}l<{\hspost}@{}}%
\column{24}{@{}>{\hspre}c<{\hspost}@{}}%
\column{24E}{@{}l@{}}%
\column{25}{@{}>{\hspre}l<{\hspost}@{}}%
\column{27}{@{}>{\hspre}l<{\hspost}@{}}%
\column{34}{@{}>{\hspre}l<{\hspost}@{}}%
\column{52}{@{}>{\hspre}l<{\hspost}@{}}%
\column{63}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\text{\hkw{import}}\;\text{Id}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{VarEnv}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{UniqFM}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{Outputable}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{\text{Data}.List}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{Bag}{}\<[E]%
\\
\>[B]{}\text{\hkw{import}}\;\text{Unique}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{\hkw{import}}\;\text{qualified}\;\text{\text{Data}.IntSet}\;\text{as}\;\text{S}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{\hkw{newtype}}\;\text{UnVarSet}\mathrel{=}\text{UnVarSet}\;(\text{\text{S}.IntSet}){}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\text{\hkw{deriving}}\;\text{Eq}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{k}\mathbin{::}\text{Var}\rightarrow \text{Int}{}\<[E]%
\\
\>[B]{}\text{k}\;\text{v}\mathrel{=}\text{getKey}\;(\text{getUnique}\;\text{v}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{emptyUnVarSet}\mathbin{::}\text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{emptyUnVarSet}\mathrel{=}\text{UnVarSet}\;\text{\text{S}.empty}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{elemUnVarSet}\mathbin{::}\text{Var}\rightarrow \text{UnVarSet}\rightarrow \text{Bool}{}\<[E]%
\\
\>[B]{}\text{elemUnVarSet}\;\text{v}\;(\text{UnVarSet}\;\text{s})\mathrel{=}\text{k}\;\text{v}\mathbin{`\text{\text{S}.member}`}\text{s}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{isEmptyUnVarSet}\mathbin{::}\text{UnVarSet}\rightarrow \text{Bool}{}\<[E]%
\\
\>[B]{}\text{isEmptyUnVarSet}\;(\text{UnVarSet}\;\text{s})\mathrel{=}\text{\text{S}.null}\;\text{s}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{delUnVarSet}\mathbin{::}\text{UnVarSet}\rightarrow \text{Var}\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{delUnVarSet}\;(\text{UnVarSet}\;\text{s})\;\text{v}\mathrel{=}\text{UnVarSet}\mathbin{\$}\text{k}\;\text{v}\mathbin{`\text{\text{S}.delete}`}\text{s}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{mkUnVarSet}\mathbin{::}[\mskip1.5mu \text{Var}\mskip1.5mu]\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{mkUnVarSet}\;\text{vs}\mathrel{=}\text{UnVarSet}\mathbin{\$}\text{\text{S}.fromList}\mathbin{\$}\text{map}\;\text{k}\;\text{vs}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{varEnvDom}\mathbin{::}\text{VarEnv}\;\text{a}\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{varEnvDom}\;\text{ae}\mathrel{=}\text{UnVarSet}\mathbin{\$}\text{ufmToSet\char95 Directly}\;\text{ae}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{unionUnVarSet}\mathbin{::}\text{UnVarSet}\rightarrow \text{UnVarSet}\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{unionUnVarSet}\;(\text{UnVarSet}\;\text{set1})\;(\text{UnVarSet}\;\text{set2}){}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\mathrel{=}\text{UnVarSet}\;(\text{set1}\mathbin{`\text{\text{S}.union}`}\text{set2}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{unionUnVarSets}\mathbin{::}[\mskip1.5mu \text{UnVarSet}\mskip1.5mu]\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{unionUnVarSets}\mathrel{=}\text{foldr}\;\text{unionUnVarSet}\;\text{emptyUnVarSet}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{\hkw{instance}}\;\text{Outputable}\;\text{UnVarSet}\;\text{\hkw{where}}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\text{ppr}\;(\text{UnVarSet}\;\text{s})\mathrel{=}\text{braces}\mathbin{\$}{}\<[E]%
\\
\>[5]{}~~{}\<[9]%
\>[9]{}\text{hcat}\mathbin{\$}\text{punctuate}\;\text{comma}\;[\mskip1.5mu \text{ppr}\;(\text{getUnique}\;\text{i})\mathrel{|}\text{i}\leftarrow \text{\text{S}.toList}\;\text{s}\mskip1.5mu]{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{\hkw{data}}\;\text{Gen}{}\<[11]%
\>[11]{}\mathrel{=}{}\<[11E]%
\>[14]{}\text{CBPG}\;{}\<[20]%
\>[20]{}\text{UnVarSet}\;\text{UnVarSet}{}\<[E]%
\\
\>[11]{}\mathrel{|}{}\<[11E]%
\>[14]{}\text{CG}\;{}\<[20]%
\>[20]{}\text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{\hkw{newtype}}\;\text{UnVarGraph}\mathrel{=}\text{UnVarGraph}\;(\text{Bag}\;\text{Gen}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{emptyUnVarGraph}\mathbin{::}\text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{emptyUnVarGraph}\mathrel{=}\text{UnVarGraph}\;\text{emptyBag}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{unionUnVarGraph}\mathbin{::}\text{UnVarGraph}\rightarrow \text{UnVarGraph}\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{unionUnVarGraph}\;(\text{UnVarGraph}\;\text{g1})\;(\text{UnVarGraph}\;\text{g2}){}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\mathrel{=}\text{UnVarGraph}\;(\text{g1}\mathbin{`\text{unionBags}`}\text{g2}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{unionUnVarGraphs}\mathbin{::}[\mskip1.5mu \text{UnVarGraph}\mskip1.5mu]\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{unionUnVarGraphs}\mathrel{=}\text{foldl'}\;\text{unionUnVarGraph}\;\text{emptyUnVarGraph}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{completeBipartiteGraph}\mathbin{::}\text{UnVarSet}\rightarrow \text{UnVarSet}\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{completeBipartiteGraph}\;\text{s1}\;\text{s2}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\mathrel{=}\text{prune}\mathbin{\$}\text{UnVarGraph}\mathbin{\$}\text{unitBag}\mathbin{\$}\text{CBPG}\;\text{s1}\;\text{s2}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{completeGraph}\mathbin{::}\text{UnVarSet}\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{completeGraph}\;\text{s}\mathrel{=}\text{prune}\mathbin{\$}\text{UnVarGraph}\mathbin{\$}\text{unitBag}\mathbin{\$}\text{CG}\;\text{s}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{neighbors}\mathbin{::}\text{UnVarGraph}\rightarrow \text{Var}\rightarrow \text{UnVarSet}{}\<[E]%
\\
\>[B]{}\text{neighbors}\;(\text{UnVarGraph}\;\text{g})\;\text{v}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\mathrel{=}\text{unionUnVarSets}\mathbin{\$}\text{concatMap}\;\text{go}\mathbin{\$}\text{bagToList}\;\text{g}{}\<[E]%
\\
\>[B]{}~~{}\<[3]%
\>[3]{}\text{\hkw{where}}{}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CG}\;\text{s}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}(\text{\hkw{if}}\;\text{v}\mathbin{`\text{elemUnVarSet}`}\text{s}\;{}\<[52]%
\>[52]{}\text{\hkw{then}}\;[\mskip1.5mu \text{s}\mskip1.5mu]\;{}\<[63]%
\>[63]{}\text{\hkw{else}}\;[\mskip1.5mu \mskip1.5mu]){}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CBPG}\;\text{s1}\;\text{s2}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}(\text{\hkw{if}}\;\text{v}\mathbin{`\text{elemUnVarSet}`}\text{s1}\;{}\<[52]%
\>[52]{}\text{\hkw{then}}\;[\mskip1.5mu \text{s2}\mskip1.5mu]\;{}\<[63]%
\>[63]{}\text{\hkw{else}}\;[\mskip1.5mu \mskip1.5mu])\mathbin{++}{}\<[E]%
\\
\>[27]{}(\text{\hkw{if}}\;\text{v}\mathbin{`\text{elemUnVarSet}`}\text{s2}\;{}\<[52]%
\>[52]{}\text{\hkw{then}}\;[\mskip1.5mu \text{s1}\mskip1.5mu]\;{}\<[63]%
\>[63]{}\text{\hkw{else}}\;[\mskip1.5mu \mskip1.5mu]){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{delNode}\mathbin{::}\text{UnVarGraph}\rightarrow \text{Var}\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{delNode}\;(\text{UnVarGraph}\;\text{g})\;\text{v}\mathrel{=}\text{prune}\mathbin{\$}\text{UnVarGraph}\mathbin{\$}\text{mapBag}\;\text{go}\;\text{g}{}\<[E]%
\\
\>[B]{}~~{}\<[3]%
\>[3]{}\text{\hkw{where}}{}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CG}\;\text{s}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}\text{CG}\;(\text{s}\mathbin{`\text{delUnVarSet}`}\text{v}){}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CBPG}\;\text{s1}\;\text{s2}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}\text{CBPG}\;(\text{s1}\mathbin{`\text{delUnVarSet}`}\text{v})\;(\text{s2}\mathbin{`\text{delUnVarSet}`}\text{v}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{prune}\mathbin{::}\text{UnVarGraph}\rightarrow \text{UnVarGraph}{}\<[E]%
\\
\>[B]{}\text{prune}\;(\text{UnVarGraph}\;\text{g})\mathrel{=}\text{UnVarGraph}\mathbin{\$}\text{filterBag}\;\text{go}\;\text{g}{}\<[E]%
\\
\>[B]{}~~{}\<[3]%
\>[3]{}\text{\hkw{where}}{}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CG}\;\text{s}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}\text{not}\;(\text{isEmptyUnVarSet}\;\text{s}){}\<[E]%
\\
\>[3]{}~~{}\<[7]%
\>[7]{}\text{go}\;(\text{CBPG}\;\text{s1}\;\text{s2}){}\<[24]%
\>[24]{}\mathrel{=}{}\<[24E]%
\>[27]{}\text{not}\;(\text{isEmptyUnVarSet}\;\text{s1})\mathbin{\&\&}{}\<[E]%
\\
\>[27]{}\text{not}\;(\text{isEmptyUnVarSet}\;\text{s2}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\text{\hkw{instance}}\;\text{Outputable}\;\text{Gen}\;\text{\hkw{where}}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\text{ppr}\;(\text{CG}\;\text{s}){}\<[25]%
\>[25]{}\mathrel{=}\text{ppr}\;\text{s}{}\<[34]%
\>[34]{}\mathbin{<>}\text{char}\;{\tt '{}²{}'}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\text{ppr}\;(\text{CBPG}\;\text{s1}\;\text{s2}){}\<[25]%
\>[25]{}\mathrel{=}\text{ppr}\;\text{s1}\mathbin{<+>}\text{char}\;{\tt '{}x{}'}\mathbin{<+>}\text{ppr}\;\text{s2}{}\<[E]%
\\
\>[B]{}\text{\hkw{instance}}\;\text{Outputable}\;\text{UnVarGraph}\;\text{\hkw{where}}{}\<[E]%
\\
\>[B]{}~~{}\<[5]%
\>[5]{}\text{ppr}\;(\text{UnVarGraph}\;\text{g}){}\<[25]%
\>[25]{}\mathrel{=}\text{ppr}\;\text{g}{}\<[E]%
\ColumnHook
\end{pboxed}
\)\par\noindent\endgroup\resethooks
