<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ -->
<title>src/full/Agda/TypeChecking/Rules/LHS/Unify.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# LANGUAGE CPP, MultiParamTypeClasses, FlexibleInstances, TupleSections,
<a name="line-2"></a> GeneralizedNewtypeDeriving,
<a name="line-3"></a> DeriveDataTypeable, DeriveFunctor, DeriveFoldable, DeriveTraversable #-}</span>
<a name="line-4"></a>
<a name="line-5"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Rules</span><span class='hs-varop'>.</span><span class='hs-conid'>LHS</span><span class='hs-varop'>.</span><span class='hs-conid'>Unify</span> <span class='hs-keyword'>where</span>
<a name="line-6"></a>
<a name="line-7"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Arrow</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varop'>***</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>&&&</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-8"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Applicative</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>empty</span><span class='hs-layout'>)</span>
<a name="line-9"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span><span class='hs-varop'>.</span><span class='hs-conid'>State</span>
<a name="line-10"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span><span class='hs-varop'>.</span><span class='hs-conid'>Reader</span>
<a name="line-11"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span><span class='hs-varop'>.</span><span class='hs-conid'>Error</span>
<a name="line-12"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span><span class='hs-varop'>.</span><span class='hs-conid'>Writer</span> <span class='hs-layout'>(</span><span class='hs-conid'>WriterT</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>MonadWriter</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monoid</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-13"></a>
<a name="line-14"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Map</span> <span class='hs-layout'>(</span><span class='hs-conid'>Map</span><span class='hs-layout'>)</span>
<a name="line-15"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Map</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>Map</span>
<a name="line-16"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>sort</span><span class='hs-layout'>)</span>
<a name="line-17"></a>
<a name="line-18"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Typeable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Typeable</span><span class='hs-layout'>)</span>
<a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span><span class='hs-layout'>)</span>
<a name="line-20"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Traversable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Traversable</span><span class='hs-layout'>,</span><span class='hs-varid'>traverse</span><span class='hs-layout'>)</span>
<a name="line-21"></a>
<a name="line-22"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Syntax</span><span class='hs-varop'>.</span><span class='hs-conid'>Common</span>
<a name="line-23"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Syntax</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span>
<a name="line-24"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Syntax</span><span class='hs-varop'>.</span><span class='hs-conid'>Literal</span>
<a name="line-25"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Syntax</span><span class='hs-varop'>.</span><span class='hs-conid'>Position</span>
<a name="line-26"></a>
<a name="line-27"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span>
<a name="line-28"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span><span class='hs-varop'>.</span><span class='hs-conid'>Exception</span>
<a name="line-29"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Conversion</span> <span class='hs-comment'>-- equalTerm</span>
<a name="line-30"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Constraints</span>
<a name="line-31"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Level</span> <span class='hs-layout'>(</span><span class='hs-varid'>reallyUnLevelView</span><span class='hs-layout'>)</span>
<a name="line-32"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Reduce</span>
<a name="line-33"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Pretty</span>
<a name="line-34"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Substitute</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-conid'>Substitution</span><span class='hs-layout'>)</span>
<a name="line-35"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Substitute</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>S</span>
<a name="line-36"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Telescope</span>
<a name="line-37"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Free</span>
<a name="line-38"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Records</span>
<a name="line-39"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Primitive</span> <span class='hs-layout'>(</span><span class='hs-varid'>constructorForm</span><span class='hs-layout'>)</span>
<a name="line-40"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>MetaVars</span> <span class='hs-layout'>(</span><span class='hs-varid'>assignV</span><span class='hs-layout'>,</span> <span class='hs-varid'>newArgsMetaCtx</span><span class='hs-layout'>)</span>
<a name="line-41"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>EtaContract</span>
<a name="line-42"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Interaction</span><span class='hs-varop'>.</span><span class='hs-conid'>Options</span> <span class='hs-layout'>(</span><span class='hs-varid'>optInjectiveTypeConstructors</span><span class='hs-layout'>)</span>
<a name="line-43"></a>
<a name="line-44"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>TypeChecking</span><span class='hs-varop'>.</span><span class='hs-conid'>Rules</span><span class='hs-varop'>.</span><span class='hs-conid'>LHS</span><span class='hs-varop'>.</span><span class='hs-conid'>Problem</span>
<a name="line-45"></a>
<a name="line-46"></a><span class='hs-cpp'>#include "../../../undefined.h"</span>
<a name="line-47"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Utils</span><span class='hs-varop'>.</span><span class='hs-conid'>Impossible</span>
<a name="line-48"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Agda</span><span class='hs-varop'>.</span><span class='hs-conid'>Utils</span><span class='hs-varop'>.</span><span class='hs-conid'>Size</span>
<a name="line-49"></a>
<a name="line-50"></a><a name="Unify"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-layout'>{</span> <span class='hs-varid'>unUnify</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ReaderT</span> <span class='hs-conid'>UnifyEnv</span> <span class='hs-layout'>(</span><span class='hs-conid'>WriterT</span> <span class='hs-conid'>UnifyOutput</span> <span class='hs-layout'>(</span><span class='hs-conid'>ExceptionT</span> <span class='hs-conid'>UnifyException</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateT</span> <span class='hs-conid'>UnifyState</span> <span class='hs-conid'>TCM</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>a</span> <span class='hs-layout'>}</span>
<a name="line-51"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Monad</span><span class='hs-layout'>,</span> <span class='hs-conid'>MonadIO</span><span class='hs-layout'>,</span> <span class='hs-conid'>Functor</span><span class='hs-layout'>,</span> <span class='hs-conid'>Applicative</span><span class='hs-layout'>,</span> <span class='hs-conid'>MonadException</span> <span class='hs-conid'>UnifyException</span><span class='hs-layout'>,</span> <span class='hs-conid'>MonadWriter</span> <span class='hs-conid'>UnifyOutput</span><span class='hs-layout'>)</span>
<a name="line-52"></a>
<a name="line-53"></a><a name="instance%20MonadReader%20TCEnv%20Unify"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>MonadReader</span> <span class='hs-conid'>TCEnv</span> <span class='hs-conid'>Unify</span> <span class='hs-keyword'>where</span>
<a name="line-54"></a> <span class='hs-varid'>ask</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-conid'>ReaderT</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ask</span>
<a name="line-55"></a> <span class='hs-varid'>local</span> <span class='hs-varid'>cont</span> <span class='hs-layout'>(</span><span class='hs-conid'>U</span> <span class='hs-layout'>(</span><span class='hs-conid'>ReaderT</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-conid'>ReaderT</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>local</span> <span class='hs-varid'>cont</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-56"></a>
<a name="line-57"></a><a name="UnifyMayPostpone"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>UnifyMayPostpone</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>MayPostpone</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>MayNotPostpone</span>
<a name="line-58"></a>
<a name="line-59"></a><a name="UnifyEnv"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>UnifyEnv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>UnifyMayPostpone</span>
<a name="line-60"></a><a name="emptyUEnv"></a><span class='hs-definition'>emptyUEnv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>MayPostpone</span>
<a name="line-61"></a>
<a name="line-62"></a><a name="noPostponing"></a><span class='hs-definition'>noPostponing</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span>
<a name="line-63"></a><span class='hs-definition'>noPostponing</span> <span class='hs-layout'>(</span><span class='hs-conid'>U</span> <span class='hs-layout'>(</span><span class='hs-conid'>ReaderT</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>.</span> <span class='hs-conid'>ReaderT</span> <span class='hs-varop'>.</span> <span class='hs-varid'>const</span> <span class='hs-varop'>$</span> <span class='hs-varid'>f</span> <span class='hs-conid'>MayNotPostpone</span>
<a name="line-64"></a>
<a name="line-65"></a><a name="askPostpone"></a><span class='hs-definition'>askPostpone</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>UnifyMayPostpone</span>
<a name="line-66"></a><span class='hs-definition'>askPostpone</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>.</span> <span class='hs-conid'>ReaderT</span> <span class='hs-varop'>$</span> <span class='hs-varid'>return</span>
<a name="line-67"></a>
<a name="line-68"></a><a name="UnifyOutput"></a><span class='hs-comment'>-- | Output the result of unification (success or maybe).</span>
<a name="line-69"></a><a name="UnifyOutput"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>UnifyOutput</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Unifiable</span>
<a name="line-70"></a>
<a name="line-71"></a><a name="emptyUOutput"></a><span class='hs-definition'>emptyUOutput</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>UnifyOutput</span>
<a name="line-72"></a><span class='hs-definition'>emptyUOutput</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mempty</span>
<a name="line-73"></a>
<a name="line-74"></a><a name="Unifiable"></a><span class='hs-comment'>-- | Were two terms unifiable or did we have to postpone some equation such that we are not sure?</span>
<a name="line-75"></a><a name="Unifiable"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Unifiable</span>
<a name="line-76"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Definitely</span> <span class='hs-comment'>-- ^ Unification succeeded.</span>
<a name="line-77"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Possibly</span> <span class='hs-comment'>-- ^ Unification did not fail, but we had to postpone a part.</span>
<a name="line-78"></a>
<a name="line-79"></a><a name="instance%20Monoid%20Unifiable"></a><span class='hs-comment'>-- | Conjunctive monoid.</span>
<a name="line-80"></a><a name="instance%20Monoid%20Unifiable"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Monoid</span> <span class='hs-conid'>Unifiable</span> <span class='hs-keyword'>where</span>
<a name="line-81"></a> <span class='hs-varid'>mempty</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Definitely</span>
<a name="line-82"></a> <span class='hs-varid'>mappend</span> <span class='hs-conid'>Definitely</span> <span class='hs-conid'>Definitely</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Definitely</span>
<a name="line-83"></a> <span class='hs-varid'>mappend</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Possibly</span>
<a name="line-84"></a>
<a name="line-85"></a><a name="reportPostponing"></a><span class='hs-comment'>-- | Tell that something could not be unified right now,</span>
<a name="line-86"></a><span class='hs-comment'>-- so the unification succeeds only 'Possibly'.</span>
<a name="line-87"></a><span class='hs-definition'>reportPostponing</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-88"></a><span class='hs-definition'>reportPostponing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tell</span> <span class='hs-conid'>Possibly</span>
<a name="line-89"></a>
<a name="line-90"></a><a name="ifClean"></a><span class='hs-comment'>-- | Check whether unification proceeded without postponement.</span>
<a name="line-91"></a><span class='hs-definition'>ifClean</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span>
<a name="line-92"></a><span class='hs-definition'>ifClean</span> <span class='hs-varid'>m</span> <span class='hs-varid'>t</span> <span class='hs-varid'>e</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-93"></a> <span class='hs-varid'>ok</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>snd</span> <span class='hs-varop'><$></span> <span class='hs-varid'>listen</span> <span class='hs-varid'>m</span>
<a name="line-94"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>of</span>
<a name="line-95"></a> <span class='hs-conid'>Definitely</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span>
<a name="line-96"></a> <span class='hs-conid'>Possibly</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>e</span>
<a name="line-97"></a>
<a name="line-98"></a><a name="Equality"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Equality</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Equal</span> <span class='hs-conid'>TypeHH</span> <span class='hs-conid'>Term</span> <span class='hs-conid'>Term</span>
<a name="line-99"></a><a name="Sub"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>Sub</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Map</span> <span class='hs-conid'>Nat</span> <span class='hs-conid'>Term</span>
<a name="line-100"></a>
<a name="line-101"></a><a name="UnifyException"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>UnifyException</span>
<a name="line-102"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ConstructorMismatch</span> <span class='hs-conid'>Type</span> <span class='hs-conid'>Term</span> <span class='hs-conid'>Term</span>
<a name="line-103"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>StronglyRigidOccurrence</span> <span class='hs-conid'>Type</span> <span class='hs-conid'>Term</span> <span class='hs-conid'>Term</span>
<a name="line-104"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>GenericUnifyException</span> <span class='hs-conid'>String</span>
<a name="line-105"></a>
<a name="line-106"></a><a name="instance%20Error%20UnifyException"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Error</span> <span class='hs-conid'>UnifyException</span> <span class='hs-keyword'>where</span>
<a name="line-107"></a> <span class='hs-varid'>noMsg</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>strMsg</span> <span class='hs-str'>""</span>
<a name="line-108"></a> <span class='hs-varid'>strMsg</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GenericUnifyException</span>
<a name="line-109"></a>
<a name="line-110"></a><a name="UnifyState"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>UnifyState</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>USt</span> <span class='hs-layout'>{</span> <span class='hs-varid'>uniSub</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Sub</span>
<a name="line-111"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>uniConstr</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Equality</span><span class='hs-keyglyph'>]</span>
<a name="line-112"></a> <span class='hs-layout'>}</span>
<a name="line-113"></a>
<a name="line-114"></a><a name="emptyUState"></a><span class='hs-definition'>emptyUState</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>USt</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>empty</span> <span class='hs-conid'>[]</span>
<a name="line-115"></a>
<a name="line-116"></a><a name="constructorMismatch"></a><span class='hs-definition'>constructorMismatch</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span>
<a name="line-117"></a><span class='hs-definition'>constructorMismatch</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>throwException</span> <span class='hs-varop'>$</span> <span class='hs-conid'>ConstructorMismatch</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-118"></a>
<a name="line-119"></a><a name="constructorMismatchHH"></a><span class='hs-definition'>constructorMismatchHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span>
<a name="line-120"></a><span class='hs-definition'>constructorMismatchHH</span> <span class='hs-varid'>aHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>constructorMismatch</span> <span class='hs-layout'>(</span><span class='hs-varid'>leftHH</span> <span class='hs-varid'>aHH</span><span class='hs-layout'>)</span>
<a name="line-121"></a> <span class='hs-comment'>-- do not report heterogenity</span>
<a name="line-122"></a>
<a name="line-123"></a><a name="instance%20MonadState%20TCState%20Unify"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>MonadState</span> <span class='hs-conid'>TCState</span> <span class='hs-conid'>Unify</span> <span class='hs-keyword'>where</span>
<a name="line-124"></a> <span class='hs-varid'>get</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>$</span> <span class='hs-varid'>get</span>
<a name="line-125"></a> <span class='hs-varid'>put</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>put</span>
<a name="line-126"></a>
<a name="line-127"></a><a name="instance%20MonadTCM%20Unify"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>MonadTCM</span> <span class='hs-conid'>Unify</span> <span class='hs-keyword'>where</span>
<a name="line-128"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span> <span class='hs-varop'>.</span> <span class='hs-varid'>lift</span>
<a name="line-129"></a>
<a name="line-130"></a><a name="instance%20Subst%20Equality"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Subst</span> <span class='hs-conid'>Equality</span> <span class='hs-keyword'>where</span>
<a name="line-131"></a> <span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-layout'>(</span><span class='hs-conid'>Equal</span> <span class='hs-varid'>a</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-132"></a> <span class='hs-conid'>Equal</span> <span class='hs-layout'>(</span><span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-133"></a>
<a name="line-134"></a><a name="onSub"></a><span class='hs-definition'>onSub</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Sub</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>a</span>
<a name="line-135"></a><span class='hs-definition'>onSub</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-varid'>gets</span> <span class='hs-varop'>$</span> <span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>uniSub</span>
<a name="line-136"></a>
<a name="line-137"></a><a name="modSub"></a><span class='hs-definition'>modSub</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Sub</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Sub</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-138"></a><span class='hs-definition'>modSub</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-varid'>modify</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>s</span> <span class='hs-layout'>{</span> <span class='hs-varid'>uniSub</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varop'>$</span> <span class='hs-varid'>uniSub</span> <span class='hs-varid'>s</span> <span class='hs-layout'>}</span>
<a name="line-139"></a>
<a name="line-140"></a><a name="checkEqualities"></a><span class='hs-definition'>checkEqualities</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Equality</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-conid'>()</span>
<a name="line-141"></a><span class='hs-definition'>checkEqualities</span> <span class='hs-varid'>eqs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>noConstraints</span> <span class='hs-varop'>$</span> <span class='hs-varid'>mapM_</span> <span class='hs-varid'>checkEq</span> <span class='hs-varid'>eqs</span>
<a name="line-142"></a> <span class='hs-keyword'>where</span>
<a name="line-143"></a> <span class='hs-varid'>checkEq</span> <span class='hs-layout'>(</span><span class='hs-conid'>Equal</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>equalTerm</span> <span class='hs-varid'>a</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span>
<a name="line-144"></a> <span class='hs-varid'>checkEq</span> <span class='hs-layout'>(</span><span class='hs-conid'>Equal</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>typeError</span> <span class='hs-varop'>$</span> <span class='hs-conid'>HeterogeneousEquality</span> <span class='hs-varid'>s</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>t</span> <span class='hs-varid'>a2</span>
<a name="line-145"></a>
<a name="line-146"></a><a name="checkEquality"></a><span class='hs-comment'>-- | Force equality now instead of postponing it using 'addEquality'.</span>
<a name="line-147"></a><span class='hs-definition'>checkEquality</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-conid'>()</span>
<a name="line-148"></a><span class='hs-definition'>checkEquality</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>noConstraints</span> <span class='hs-varop'>$</span> <span class='hs-varid'>equalTerm</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-149"></a>
<a name="line-150"></a><a name="checkEqualityHH"></a><span class='hs-comment'>-- | Try equality. If constraints remain, postpone (enter unsafe mode).</span>
<a name="line-151"></a><span class='hs-comment'>-- Heterogeneous equalities cannot be tried nor reawakened,</span>
<a name="line-152"></a><span class='hs-comment'>-- so we can throw them away and flag "dirty".</span>
<a name="line-153"></a><span class='hs-definition'>checkEqualityHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-154"></a><span class='hs-definition'>checkEqualityHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-155"></a> <span class='hs-varid'>ok</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>noConstraints</span> <span class='hs-layout'>(</span><span class='hs-conid'>True</span> <span class='hs-varop'><$</span> <span class='hs-varid'>equalTerm</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- no constraints left</span>
<a name="line-156"></a> <span class='hs-varop'>`catchError`</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>False</span>
<a name="line-157"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>addEquality</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-158"></a><span class='hs-definition'>checkEqualityHH</span> <span class='hs-varid'>aHH</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-comment'>-- reportPostponing -- enter "dirty" mode</span>
<a name="line-159"></a> <span class='hs-varid'>addEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-comment'>-- postpone, enter "dirty" mode</span>
<a name="line-160"></a>
<a name="line-161"></a><a name="forceHom"></a><span class='hs-comment'>-- | Check whether heterogeneous situation is really homogeneous.</span>
<a name="line-162"></a><span class='hs-comment'>-- If not, give up.</span>
<a name="line-163"></a><span class='hs-definition'>forceHom</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-conid'>Type</span>
<a name="line-164"></a><span class='hs-definition'>forceHom</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-varid'>a</span>
<a name="line-165"></a><span class='hs-definition'>forceHom</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-166"></a> <span class='hs-varid'>noConstraints</span> <span class='hs-varop'>$</span> <span class='hs-varid'>equalType</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span>
<a name="line-167"></a> <span class='hs-varid'>return</span> <span class='hs-varid'>a1</span>
<a name="line-168"></a>
<a name="line-169"></a><a name="addEquality"></a><span class='hs-definition'>addEquality</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-170"></a><span class='hs-definition'>addEquality</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addEqualityHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-171"></a>
<a name="line-172"></a><a name="addEqualityHH"></a><span class='hs-definition'>addEqualityHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-173"></a><span class='hs-definition'>addEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-174"></a> <span class='hs-varid'>reportPostponing</span>
<a name="line-175"></a> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-varid'>modify</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>s</span> <span class='hs-layout'>{</span> <span class='hs-varid'>uniConstr</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Equal</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-conop'>:</span> <span class='hs-varid'>uniConstr</span> <span class='hs-varid'>s</span> <span class='hs-layout'>}</span>
<a name="line-176"></a>
<a name="line-177"></a><a name="takeEqualities"></a><span class='hs-definition'>takeEqualities</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Equality</span><span class='hs-keyglyph'>]</span>
<a name="line-178"></a><span class='hs-definition'>takeEqualities</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>U</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-179"></a> <span class='hs-varid'>s</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>get</span>
<a name="line-180"></a> <span class='hs-varid'>put</span> <span class='hs-varop'>$</span> <span class='hs-varid'>s</span> <span class='hs-layout'>{</span> <span class='hs-varid'>uniConstr</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span> <span class='hs-layout'>}</span>
<a name="line-181"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>uniConstr</span> <span class='hs-varid'>s</span>
<a name="line-182"></a>
<a name="line-183"></a><a name="occursCheck"></a><span class='hs-comment'>-- | Includes flexible occurrences, metas need to be solved. TODO: relax?</span>
<a name="line-184"></a><span class='hs-comment'>-- TODO: later solutions may remove flexible occurences</span>
<a name="line-185"></a><span class='hs-definition'>occursCheck</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Nat</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-186"></a><span class='hs-definition'>occursCheck</span> <span class='hs-varid'>i</span> <span class='hs-varid'>u</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-187"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>fv</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>freeVars</span> <span class='hs-varid'>u</span>
<a name="line-188"></a> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>var</span> <span class='hs-varid'>i</span>
<a name="line-189"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>occurrence</span> <span class='hs-varid'>i</span> <span class='hs-varid'>fv</span> <span class='hs-keyword'>of</span>
<a name="line-190"></a> <span class='hs-comment'>-- Andreas, 2011-04-14</span>
<a name="line-191"></a> <span class='hs-comment'>-- a strongly rigid recursive occurrences signals unsolvability</span>
<a name="line-192"></a> <span class='hs-conid'>StronglyRigid</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-193"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>20</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>"occurs strongly rigidly in"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span>
<a name="line-194"></a> <span class='hs-varid'>throwException</span> <span class='hs-varop'>$</span> <span class='hs-conid'>StronglyRigidOccurrence</span> <span class='hs-varid'>a</span> <span class='hs-varid'>v</span> <span class='hs-varid'>u</span>
<a name="line-195"></a>
<a name="line-196"></a> <span class='hs-conid'>NoOccurrence</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span> <span class='hs-comment'>-- this includes irrelevant occurrences!</span>
<a name="line-197"></a>
<a name="line-198"></a> <span class='hs-comment'>-- any other recursive occurrence leads to unclear situation</span>
<a name="line-199"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-200"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>20</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>"occurs in"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span>
<a name="line-201"></a> <span class='hs-varid'>typeError</span> <span class='hs-varop'>$</span> <span class='hs-conid'>UnequalTerms</span> <span class='hs-conid'>CmpEq</span> <span class='hs-varid'>v</span> <span class='hs-varid'>u</span> <span class='hs-varid'>a</span>
<a name="line-202"></a>
<a name="line-203"></a><a name="%7c-%3e"></a><span class='hs-comment'>-- | Assignment with preceding occurs check.</span>
<a name="line-204"></a><span class='hs-layout'>(</span><span class='hs-varop'>|-></span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Nat</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Term</span><span class='hs-layout'>,</span> <span class='hs-conid'>Type</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-205"></a><a name="i"></a><span class='hs-definition'>i</span> <span class='hs-varop'>|-></span> <span class='hs-layout'>(</span><span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-206"></a> <span class='hs-varid'>occursCheck</span> <span class='hs-varid'>i</span> <span class='hs-varid'>u</span> <span class='hs-varid'>a</span>
<a name="line-207"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>var</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>":="</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span>
<a name="line-208"></a> <span class='hs-varid'>modSub</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>insert</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-varid'>killRange</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span>
<a name="line-209"></a> <span class='hs-comment'>-- Apply substitution to itself (issue 552)</span>
<a name="line-210"></a> <span class='hs-varid'>rho</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>onSub</span> <span class='hs-varid'>id</span>
<a name="line-211"></a> <span class='hs-varid'>rho'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>traverse</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>rho</span>
<a name="line-212"></a> <span class='hs-varid'>modSub</span> <span class='hs-varop'>$</span> <span class='hs-varid'>const</span> <span class='hs-varid'>rho'</span>
<a name="line-213"></a>
<a name="line-214"></a><a name="makeSubstitution"></a><span class='hs-definition'>makeSubstitution</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Sub</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>S</span><span class='hs-varop'>.</span><span class='hs-conid'>Substitution</span>
<a name="line-215"></a><span class='hs-definition'>makeSubstitution</span> <span class='hs-varid'>sub</span>
<a name="line-216"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>null</span> <span class='hs-varid'>sub</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>idS</span>
<a name="line-217"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-varid'>val</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span> <span class='hs-keyglyph'>..</span> <span class='hs-varid'>highestIndex</span><span class='hs-keyglyph'>]</span> <span class='hs-varop'>++#</span> <span class='hs-varid'>raiseS</span> <span class='hs-layout'>(</span><span class='hs-varid'>highestIndex</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-218"></a> <span class='hs-keyword'>where</span>
<a name="line-219"></a> <span class='hs-varid'>highestIndex</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fst</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>findMax</span> <span class='hs-varid'>sub</span>
<a name="line-220"></a> <span class='hs-varid'>val</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>var</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varid'>id</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>lookup</span> <span class='hs-varid'>i</span> <span class='hs-varid'>sub</span>
<a name="line-221"></a>
<a name="line-222"></a><a name="UReduce"></a><span class='hs-comment'>-- | Apply the current substitution on a term and reduce to weak head normal form.</span>
<a name="line-223"></a><a name="UReduce"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>UReduce</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>where</span>
<a name="line-224"></a> <span class='hs-varid'>ureduce</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-varid'>t</span>
<a name="line-225"></a>
<a name="line-226"></a><a name="instance%20UReduce%20Term"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>UReduce</span> <span class='hs-conid'>Term</span> <span class='hs-keyword'>where</span>
<a name="line-227"></a> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>doEtaContractImplicit</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-228"></a> <span class='hs-varid'>rho</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>onSub</span> <span class='hs-varid'>makeSubstitution</span>
<a name="line-229"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>etaContract</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>normalise</span> <span class='hs-layout'>(</span><span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span>
<a name="line-230"></a><span class='hs-comment'>-- Andreas, 2011-06-22, fix related to issue 423</span>
<a name="line-231"></a><span class='hs-comment'>-- To make eta contraction work better, I switched reduce to normalise.</span>
<a name="line-232"></a><span class='hs-comment'>-- I hope the performance penalty is not big (since we are dealing with</span>
<a name="line-233"></a><span class='hs-comment'>-- l.h.s. terms only).</span>
<a name="line-234"></a><span class='hs-comment'>-- A systematic solution would make unification type-directed and</span>
<a name="line-235"></a><span class='hs-comment'>-- eta-insensitive...</span>
<a name="line-236"></a><span class='hs-comment'>-- liftTCM $ etaContract =<< reduce (applySubst rho u)</span>
<a name="line-237"></a>
<a name="line-238"></a><a name="instance%20UReduce%20Type"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>UReduce</span> <span class='hs-conid'>Type</span> <span class='hs-keyword'>where</span>
<a name="line-239"></a> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>El</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>El</span> <span class='hs-varid'>s</span> <span class='hs-varop'><$></span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>t</span>
<a name="line-240"></a>
<a name="line-241"></a><a name="instance%20UReduce%20(HomHet%20t)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>UReduce</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>UReduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-242"></a> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Hom</span> <span class='hs-varop'><$></span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>t</span>
<a name="line-243"></a> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>t1</span> <span class='hs-varid'>t2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Het</span> <span class='hs-varop'><$></span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>t1</span> <span class='hs-varop'><*></span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>t2</span>
<a name="line-244"></a>
<a name="line-245"></a><a name="instance%20UReduce%20(Maybe%20t)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>UReduce</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>UReduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-246"></a> <span class='hs-varid'>ureduce</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>Nothing</span>
<a name="line-247"></a> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varop'><$></span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>t</span>
<a name="line-248"></a>
<a name="line-249"></a><a name="flattenSubstitution"></a><span class='hs-comment'>-- | Take a substitution σ and ensure that no variables from the domain appear</span>
<a name="line-250"></a><span class='hs-comment'>-- in the targets. The context of the targets is not changed.</span>
<a name="line-251"></a><span class='hs-comment'>-- TODO: can this be expressed using makeSubstitution and applySubst?</span>
<a name="line-252"></a><span class='hs-definition'>flattenSubstitution</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Substitution</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Substitution</span>
<a name="line-253"></a><span class='hs-definition'>flattenSubstitution</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>instantiate</span> <span class='hs-varid'>s</span> <span class='hs-varid'>is</span>
<a name="line-254"></a> <span class='hs-keyword'>where</span>
<a name="line-255"></a> <span class='hs-comment'>-- instantiated variables</span>
<a name="line-256"></a> <span class='hs-varid'>is</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-layout'>,</span> <span class='hs-conid'>Just</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>zip</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span><span class='hs-keyglyph'>..</span><span class='hs-keyglyph'>]</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>]</span>
<a name="line-257"></a>
<a name="line-258"></a> <span class='hs-varid'>instantiate</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Nat</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Substitution</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Substitution</span>
<a name="line-259"></a> <span class='hs-varid'>instantiate</span> <span class='hs-varid'>i</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-varid'>fmap</span> <span class='hs-varop'>$</span> <span class='hs-varid'>inst</span> <span class='hs-varid'>i</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-varid'>s</span>
<a name="line-260"></a> <span class='hs-keyword'>where</span>
<a name="line-261"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>s</span> <span class='hs-varop'>!!</span> <span class='hs-varid'>i</span>
<a name="line-262"></a>
<a name="line-263"></a> <span class='hs-varid'>inst</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Nat</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span>
<a name="line-264"></a> <span class='hs-varid'>inst</span> <span class='hs-varid'>i</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>applySubst</span> <span class='hs-varid'>us</span> <span class='hs-varid'>v</span>
<a name="line-265"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>us</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>var</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span><span class='hs-keyglyph'>..</span><span class='hs-varid'>i</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>]</span> <span class='hs-varop'>++#</span> <span class='hs-varid'>u</span> <span class='hs-conop'>:#</span> <span class='hs-varid'>raiseS</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-266"></a>
<a name="line-267"></a><a name="UnificationResult"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>UnificationResult</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Unifies</span> <span class='hs-conid'>Substitution</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>NoUnify</span> <span class='hs-conid'>Type</span> <span class='hs-conid'>Term</span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>DontKnow</span> <span class='hs-conid'>TCErr</span>
<a name="line-268"></a>
<a name="line-269"></a><a name="HomHet"></a><span class='hs-comment'>-- | Are we in a homogeneous (one type) or heterogeneous (two types) situation?</span>
<a name="line-270"></a><a name="HomHet"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span>
<a name="line-271"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span> <span class='hs-comment'>-- ^ homogeneous</span>
<a name="line-272"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Het</span> <span class='hs-varid'>a</span> <span class='hs-varid'>a</span> <span class='hs-comment'>-- ^ heterogeneous</span>
<a name="line-273"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Typeable</span><span class='hs-layout'>,</span> <span class='hs-conid'>Show</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span><span class='hs-layout'>,</span> <span class='hs-conid'>Functor</span><span class='hs-layout'>,</span> <span class='hs-conid'>Foldable</span><span class='hs-layout'>,</span> <span class='hs-conid'>Traversable</span><span class='hs-layout'>)</span>
<a name="line-274"></a>
<a name="line-275"></a><a name="isHom"></a><span class='hs-definition'>isHom</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-276"></a><span class='hs-definition'>isHom</span> <span class='hs-conid'>Hom</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-277"></a><span class='hs-definition'>isHom</span> <span class='hs-conid'>Het</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-278"></a>
<a name="line-279"></a><a name="fromHom"></a><span class='hs-definition'>fromHom</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-280"></a><span class='hs-definition'>fromHom</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span>
<a name="line-281"></a><span class='hs-definition'>fromHom</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-282"></a>
<a name="line-283"></a><a name="leftHH"></a><span class='hs-definition'>leftHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-284"></a><span class='hs-definition'>leftHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span>
<a name="line-285"></a><span class='hs-definition'>leftHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a1</span>
<a name="line-286"></a>
<a name="line-287"></a><a name="rightHH"></a><span class='hs-definition'>rightHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-288"></a><span class='hs-definition'>rightHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span>
<a name="line-289"></a><span class='hs-definition'>rightHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a2</span>
<a name="line-290"></a>
<a name="line-291"></a><a name="instance%20Subst%20(HomHet%20a)"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Subst</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Subst</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-292"></a> <span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-varid'>applySubst</span> <span class='hs-varid'>rho</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span>
<a name="line-293"></a>
<a name="line-294"></a><a name="instance%20PrettyTCM%20(HomHet%20a)"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>PrettyTCM</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>PrettyTCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-295"></a> <span class='hs-varid'>prettyTCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a</span>
<a name="line-296"></a> <span class='hs-varid'>prettyTCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a1</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>"||"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a2</span>
<a name="line-297"></a>
<a name="line-298"></a><a name="TermHH"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>TermHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>HomHet</span> <span class='hs-conid'>Term</span>
<a name="line-299"></a><a name="TypeHH"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>HomHet</span> <span class='hs-conid'>Type</span>
<a name="line-300"></a><a name="TelHH"></a><span class='hs-comment'>--type FunViewHH = FunV TypeHH</span>
<a name="line-301"></a><a name="TelHH"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>TelHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Tele</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-conid'>TypeHH</span><span class='hs-layout'>)</span>
<a name="line-302"></a><a name="TelViewHH"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>TelViewHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>TelV</span> <span class='hs-conid'>TypeHH</span>
<a name="line-303"></a>
<a name="line-304"></a><a name="absAppHH"></a><span class='hs-definition'>absAppHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>t</span> <span class='hs-varid'>tHH</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Abs</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TermHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tHH</span>
<a name="line-305"></a><span class='hs-definition'>absAppHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>substHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>t</span>
<a name="line-306"></a><span class='hs-definition'>absAppHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>NoAbs</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>trivialHH</span> <span class='hs-varid'>t</span>
<a name="line-307"></a>
<a name="line-308"></a><a name="ApplyHH"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>ApplyHH</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>where</span>
<a name="line-309"></a> <span class='hs-varid'>applyHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>HomHet</span> <span class='hs-conid'>Args</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>HomHet</span> <span class='hs-varid'>t</span>
<a name="line-310"></a>
<a name="line-311"></a><a name="instance%20ApplyHH%20Term"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>ApplyHH</span> <span class='hs-conid'>Term</span> <span class='hs-keyword'>where</span>
<a name="line-312"></a> <span class='hs-varid'>applyHH</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-varid'>apply</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-313"></a>
<a name="line-314"></a><a name="instance%20ApplyHH%20Type"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>ApplyHH</span> <span class='hs-conid'>Type</span> <span class='hs-keyword'>where</span>
<a name="line-315"></a> <span class='hs-varid'>applyHH</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-varid'>apply</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-316"></a>
<a name="line-317"></a><a name="substHH"></a><span class='hs-definition'>substHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>t</span> <span class='hs-varid'>tHH</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>TermHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tHH</span>
<a name="line-318"></a><span class='hs-definition'>substHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-num'>0</span>
<a name="line-319"></a>
<a name="line-320"></a><a name="SubstHH"></a><span class='hs-comment'>-- | @substHH u t@ substitutes @u@ for the 0th variable in @t@.</span>
<a name="line-321"></a><a name="SubstHH"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>t</span> <span class='hs-varid'>tHH</span> <span class='hs-keyword'>where</span>
<a name="line-322"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Nat</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TermHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tHH</span>
<a name="line-323"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tHH</span>
<a name="line-324"></a>
<a name="line-325"></a><a name="instance%20SubstHH%20(HomHet%20a)%20(HomHet%20a)"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Free</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-conid'>Subst</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-326"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span>
<a name="line-327"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>u1</span> <span class='hs-varid'>u2</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-328"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>n</span> <span class='hs-varop'>`relevantIn`</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Het</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u1</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u2</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-329"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>Hom</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u1</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-330"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>u1</span> <span class='hs-varid'>u2</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>t1</span> <span class='hs-varid'>t2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Het</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u1</span> <span class='hs-varid'>t1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u2</span> <span class='hs-varid'>t2</span><span class='hs-layout'>)</span>
<a name="line-331"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>id</span>
<a name="line-332"></a>
<a name="line-333"></a><a name="instance%20SubstHH%20Term%20(HomHet%20Term)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-conid'>Term</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-conid'>Term</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-334"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>uHH</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>uHH</span>
<a name="line-335"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Hom</span>
<a name="line-336"></a>
<a name="line-337"></a><a name="instance%20SubstHH%20Type%20(HomHet%20Type)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-conid'>Type</span> <span class='hs-layout'>(</span><span class='hs-conid'>HomHet</span> <span class='hs-conid'>Type</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-338"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>uHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>El</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>El</span> <span class='hs-varid'>s</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnder</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>uHH</span>
<a name="line-339"></a><span class='hs-comment'>-- fmap $ fmap (\ (El s v) -> El s $ substUnderHH n u v)</span>
<a name="line-340"></a> <span class='hs-comment'>-- we ignore sorts in substitution, since they do not contain</span>
<a name="line-341"></a> <span class='hs-comment'>-- terms we can match on</span>
<a name="line-342"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Hom</span>
<a name="line-343"></a>
<a name="line-344"></a><a name="instance%20SubstHH%20(Arg%20a)%20(Arg%20b)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-345"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span>
<a name="line-346"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>trivialHH</span>
<a name="line-347"></a>
<a name="line-348"></a><a name="instance%20SubstHH%20(Dom%20a)%20(Dom%20b)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-349"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span>
<a name="line-350"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>trivialHH</span>
<a name="line-351"></a>
<a name="line-352"></a><a name="instance%20SubstHH%20(Abs%20a)%20(Abs%20b)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-353"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Abs</span> <span class='hs-varid'>x</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-354"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-layout'>(</span><span class='hs-conid'>NoAbs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NoAbs</span> <span class='hs-varid'>x</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-355"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>trivialHH</span>
<a name="line-356"></a>
<a name="line-357"></a><a name="instance%20SubstHH%20(a,b)%20(a',b')"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>SubstHH</span> <span class='hs-varid'>a</span> <span class='hs-varid'>a'</span><span class='hs-layout'>,</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>b</span> <span class='hs-varid'>b'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>a'</span><span class='hs-layout'>,</span><span class='hs-varid'>b'</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-358"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-varid'>x</span><span class='hs-layout'>,</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span>
<a name="line-359"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>trivialHH</span> <span class='hs-varop'>***</span> <span class='hs-varid'>trivialHH</span>
<a name="line-360"></a>
<a name="line-361"></a><a name="instance%20SubstHH%20(Tele%20a)%20(Tele%20b)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>SubstHH</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>SubstHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Tele</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Tele</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-362"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-conid'>EmptyTel</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EmptyTel</span>
<a name="line-363"></a> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-layout'>(</span><span class='hs-conid'>ExtendTel</span> <span class='hs-varid'>t</span> <span class='hs-varid'>tel</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>uncurry</span> <span class='hs-conid'>ExtendTel</span> <span class='hs-varop'>$</span> <span class='hs-varid'>substUnderHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>u</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-varid'>tel</span><span class='hs-layout'>)</span>
<a name="line-364"></a> <span class='hs-varid'>trivialHH</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>trivialHH</span>
<a name="line-365"></a>
<a name="line-366"></a><a name="unifyIndices_"></a><span class='hs-comment'>-- | Unify indices.</span>
<a name="line-367"></a><span class='hs-definition'>unifyIndices_</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>MonadTCM</span> <span class='hs-varid'>tcm</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>FlexibleVars</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tcm</span> <span class='hs-conid'>Substitution</span>
<a name="line-368"></a><span class='hs-definition'>unifyIndices_</span> <span class='hs-varid'>flex</span> <span class='hs-varid'>a</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-369"></a> <span class='hs-varid'>r</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>unifyIndices</span> <span class='hs-varid'>flex</span> <span class='hs-varid'>a</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-370"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>r</span> <span class='hs-keyword'>of</span>
<a name="line-371"></a> <span class='hs-conid'>Unifies</span> <span class='hs-varid'>sub</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varid'>sub</span>
<a name="line-372"></a> <span class='hs-conid'>DontKnow</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>throwError</span> <span class='hs-varid'>err</span>
<a name="line-373"></a> <span class='hs-conid'>NoUnify</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>typeError</span> <span class='hs-varop'>$</span> <span class='hs-conid'>UnequalTerms</span> <span class='hs-conid'>CmpEq</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-varid'>a</span>
<a name="line-374"></a>
<a name="line-375"></a><a name="unifyIndices"></a><span class='hs-definition'>unifyIndices</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>MonadTCM</span> <span class='hs-varid'>tcm</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>FlexibleVars</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tcm</span> <span class='hs-conid'>UnificationResult</span>
<a name="line-376"></a><span class='hs-definition'>unifyIndices</span> <span class='hs-varid'>flex</span> <span class='hs-varid'>a</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-377"></a> <span class='hs-varid'>a</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>reduce</span> <span class='hs-varid'>a</span>
<a name="line-378"></a> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>10</span> <span class='hs-varop'>$</span>
<a name="line-379"></a> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyIndices"</span>
<a name="line-380"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>flex</span><span class='hs-layout'>)</span>
<a name="line-381"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>parens</span> <span class='hs-layout'>(</span><span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-382"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>us</span>
<a name="line-383"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>vs</span>
<a name="line-384"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"context: "</span> <span class='hs-varop'><+></span> <span class='hs-layout'>(</span><span class='hs-varid'>prettyTCM</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>getContextTelescope</span><span class='hs-layout'>)</span>
<a name="line-385"></a> <span class='hs-keyglyph'>]</span>
<a name="line-386"></a> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-layout'>,</span> <span class='hs-conid'>USt</span> <span class='hs-varid'>s</span> <span class='hs-varid'>eqs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>flip</span> <span class='hs-varid'>runStateT</span> <span class='hs-varid'>emptyUState</span> <span class='hs-varop'>.</span> <span class='hs-varid'>runExceptionT</span> <span class='hs-varop'>.</span> <span class='hs-varid'>runWriterT</span> <span class='hs-varop'>.</span> <span class='hs-varid'>flip</span> <span class='hs-varid'>runReaderT</span> <span class='hs-varid'>emptyUEnv</span> <span class='hs-varop'>.</span> <span class='hs-varid'>unUnify</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-387"></a> <span class='hs-varid'>ifClean</span> <span class='hs-layout'>(</span><span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-388"></a> <span class='hs-comment'>-- clean: continue unifying</span>
<a name="line-389"></a> <span class='hs-varid'>recheckConstraints</span>
<a name="line-390"></a> <span class='hs-comment'>-- dirty: just check equalities to trigger error message</span>
<a name="line-391"></a> <span class='hs-varid'>recheckEqualities</span>
<a name="line-392"></a>
<a name="line-393"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>r</span> <span class='hs-keyword'>of</span>
<a name="line-394"></a> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-conid'>ConstructorMismatch</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>NoUnify</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-395"></a> <span class='hs-comment'>-- Andreas 2011-04-14:</span>
<a name="line-396"></a> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-conid'>StronglyRigidOccurrence</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>NoUnify</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-397"></a> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-conid'>GenericUnifyException</span> <span class='hs-varid'>err</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fail</span> <span class='hs-varid'>err</span>
<a name="line-398"></a> <span class='hs-conid'>Right</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-399"></a> <span class='hs-varid'>checkEqualities</span> <span class='hs-varop'>$</span> <span class='hs-varid'>applySubst</span> <span class='hs-layout'>(</span><span class='hs-varid'>makeSubstitution</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-varid'>eqs</span>
<a name="line-400"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maximum</span> <span class='hs-varop'>$</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>flex</span>
<a name="line-401"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Unifies</span> <span class='hs-varop'>$</span> <span class='hs-varid'>flattenSubstitution</span> <span class='hs-keyglyph'>[</span> <span class='hs-conid'>Map</span><span class='hs-varop'>.</span><span class='hs-varid'>lookup</span> <span class='hs-varid'>i</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span><span class='hs-keyglyph'>..</span><span class='hs-varid'>n</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>]</span>
<a name="line-402"></a> <span class='hs-varop'>`catchError`</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>DontKnow</span> <span class='hs-varid'>err</span>
<a name="line-403"></a> <span class='hs-keyword'>where</span>
<a name="line-404"></a> <span class='hs-varid'>flexible</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>i</span> <span class='hs-varop'>`elem`</span> <span class='hs-varid'>flex</span>
<a name="line-405"></a>
<a name="line-406"></a> <span class='hs-varid'>flexibleTerm</span> <span class='hs-layout'>(</span><span class='hs-conid'>Var</span> <span class='hs-varid'>i</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flexible</span> <span class='hs-varid'>i</span>
<a name="line-407"></a> <span class='hs-varid'>flexibleTerm</span> <span class='hs-layout'>(</span><span class='hs-conid'>Shared</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flexibleTerm</span> <span class='hs-layout'>(</span><span class='hs-varid'>derefPtr</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-408"></a> <span class='hs-varid'>flexibleTerm</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-409"></a>
<a name="line-410"></a> <span class='hs-comment'>{- Andreas, 2011-09-12
<a name="line-411"></a> We unify constructors in heterogeneous situations, as long
<a name="line-412"></a> as the two types have the same shape (construct the same datatype).
<a name="line-413"></a> -}</span>
<a name="line-414"></a>
<a name="line-415"></a> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-keyglyph'>::</span>
<a name="line-416"></a> <span class='hs-conid'>TypeHH</span> <span class='hs-comment'>-- ^ The ureduced type of the constructor, instantiated to the parameters.</span>
<a name="line-417"></a> <span class='hs-comment'>-- Possibly heterogeneous, since pars of lhs and rhs might differ.</span>
<a name="line-418"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ the arguments of the constructor (lhs)</span>
<a name="line-419"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ the arguments of the constructor (rhs)</span>
<a name="line-420"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-421"></a> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-varid'>a12</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-422"></a> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-varid'>a12</span> <span class='hs-varid'>vs1</span> <span class='hs-varid'>vs2</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-423"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sep</span>
<a name="line-424"></a> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyConstructorArgs"</span>
<a name="line-425"></a> <span class='hs-comment'>-- , nest 2 $ parens (prettyTCM tel0)</span>
<a name="line-426"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>vs1</span>
<a name="line-427"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>vs2</span>
<a name="line-428"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"constructor type:"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a12</span>
<a name="line-429"></a> <span class='hs-keyglyph'>]</span>
<a name="line-430"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>genericLength</span> <span class='hs-varid'>vs1</span>
<a name="line-431"></a> <span class='hs-comment'>-- since c vs1 and c vs2 have same-shaped type</span>
<a name="line-432"></a> <span class='hs-comment'>-- vs1 and vs2 must have same length</span>
<a name="line-433"></a> <span class='hs-varid'>when</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>genericLength</span> <span class='hs-varid'>vs2</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-434"></a> <span class='hs-conid'>TelV</span> <span class='hs-varid'>tel12</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>telViewUpToHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a12</span>
<a name="line-435"></a> <span class='hs-comment'>-- if the length of tel12 is not n, then something is wrong</span>
<a name="line-436"></a> <span class='hs-comment'>-- e.g. a12 is not a same-shaped pair of types</span>
<a name="line-437"></a> <span class='hs-varid'>when</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>size</span> <span class='hs-varid'>tel12</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-438"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-varid'>tel12</span> <span class='hs-varid'>vs1</span> <span class='hs-varid'>vs2</span>
<a name="line-439"></a>
<a name="line-440"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-keyglyph'>::</span>
<a name="line-441"></a> <span class='hs-conid'>TelHH</span> <span class='hs-comment'>-- ^ The telescope(s) of the constructor args [length = n].</span>
<a name="line-442"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ the arguments of the constructor (lhs) [length = n].</span>
<a name="line-443"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ the arguments of the constructor (rhs) [length = n].</span>
<a name="line-444"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-445"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-446"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-447"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-448"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-conid'>EmptyTel</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-449"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-varid'>tel0</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>ExtendTel</span> <span class='hs-varid'>a</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>rel</span> <span class='hs-varid'>bHH</span><span class='hs-layout'>)</span> <span class='hs-varid'>tel</span><span class='hs-layout'>)</span> <span class='hs-varid'>us0</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-varid'>arg</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>us</span><span class='hs-layout'>)</span> <span class='hs-varid'>vs0</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>v</span> <span class='hs-conop'>:</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-450"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sep</span>
<a name="line-451"></a> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyConArgs"</span>
<a name="line-452"></a> <span class='hs-comment'>-- , nest 2 $ parens (prettyTCM tel0)</span>
<a name="line-453"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>us0</span>
<a name="line-454"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>vs0</span>
<a name="line-455"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"at telescope"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>bHH</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>"..."</span>
<a name="line-456"></a> <span class='hs-keyglyph'>]</span>
<a name="line-457"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>25</span> <span class='hs-varop'>$</span>
<a name="line-458"></a> <span class='hs-layout'>(</span><span class='hs-varid'>text</span> <span class='hs-varop'>$</span> <span class='hs-str'>"tel0 = "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>show</span> <span class='hs-varid'>tel0</span><span class='hs-layout'>)</span>
<a name="line-459"></a>
<a name="line-460"></a>
<a name="line-461"></a> <span class='hs-comment'>-- Andreas, Ulf, 2011-09-08 (AIM XIV)</span>
<a name="line-462"></a> <span class='hs-comment'>-- in case of dependent function type, we cannot postpone</span>
<a name="line-463"></a> <span class='hs-comment'>-- unification of u and v, otherwise us or vs might be ill-typed</span>
<a name="line-464"></a> <span class='hs-comment'>-- skip irrelevant parts</span>
<a name="line-465"></a> <span class='hs-varid'>uHH</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyword'>if</span> <span class='hs-layout'>(</span><span class='hs-varid'>rel</span> <span class='hs-varop'>==</span> <span class='hs-conid'>Irrelevant</span><span class='hs-layout'>)</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>u</span> <span class='hs-keyword'>else</span>
<a name="line-466"></a> <span class='hs-varid'>ifClean</span> <span class='hs-layout'>(</span><span class='hs-varid'>unifyHH</span> <span class='hs-varid'>bHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Het</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-467"></a>
<a name="line-468"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>25</span> <span class='hs-varop'>$</span>
<a name="line-469"></a> <span class='hs-layout'>(</span><span class='hs-varid'>text</span> <span class='hs-str'>"uHH (before ureduce) ="</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>uHH</span><span class='hs-layout'>)</span>
<a name="line-470"></a>
<a name="line-471"></a> <span class='hs-varid'>uHH</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>traverse</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>uHH</span>
<a name="line-472"></a>
<a name="line-473"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>25</span> <span class='hs-varop'>$</span>
<a name="line-474"></a> <span class='hs-layout'>(</span><span class='hs-varid'>text</span> <span class='hs-str'>"uHH (after ureduce) ="</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>uHH</span><span class='hs-layout'>)</span>
<a name="line-475"></a>
<a name="line-476"></a> <span class='hs-varid'>unifyConArgs</span> <span class='hs-layout'>(</span><span class='hs-varid'>tel</span> <span class='hs-varop'>`absAppHH`</span> <span class='hs-varid'>uHH</span><span class='hs-layout'>)</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-477"></a>
<a name="line-478"></a>
<a name="line-479"></a> <span class='hs-comment'>-- | Used for arguments of a 'Def', not 'Con'.</span>
<a name="line-480"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Arg</span> <span class='hs-conid'>Term</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-481"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-482"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-483"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-484"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-varid'>a</span> <span class='hs-varid'>us0</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-varid'>arg</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>us</span><span class='hs-layout'>)</span> <span class='hs-varid'>vs0</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Arg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>v</span> <span class='hs-conop'>:</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-485"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sep</span>
<a name="line-486"></a> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyArgs"</span>
<a name="line-487"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>parens</span> <span class='hs-layout'>(</span><span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-488"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>us0</span>
<a name="line-489"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>vs0</span>
<a name="line-490"></a> <span class='hs-keyglyph'>]</span>
<a name="line-491"></a> <span class='hs-varid'>a</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>a</span> <span class='hs-comment'>-- Q: reduce sufficient?</span>
<a name="line-492"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ignoreSharing</span> <span class='hs-varop'>$</span> <span class='hs-varid'>unEl</span> <span class='hs-varid'>a</span> <span class='hs-keyword'>of</span>
<a name="line-493"></a> <span class='hs-conid'>Pi</span> <span class='hs-varid'>b</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-494"></a> <span class='hs-comment'>-- Andreas, Ulf, 2011-09-08 (AIM XVI)</span>
<a name="line-495"></a> <span class='hs-comment'>-- in case of dependent function type, we cannot postpone</span>
<a name="line-496"></a> <span class='hs-comment'>-- unification of u and v, otherwise us or vs might be ill-typed</span>
<a name="line-497"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>dep</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dependent</span> <span class='hs-varop'>$</span> <span class='hs-varid'>unEl</span> <span class='hs-varid'>a</span>
<a name="line-498"></a> <span class='hs-comment'>-- skip irrelevant parts</span>
<a name="line-499"></a> <span class='hs-varid'>unless</span> <span class='hs-layout'>(</span><span class='hs-varid'>domRelevance</span> <span class='hs-varid'>b</span> <span class='hs-varop'>==</span> <span class='hs-conid'>Irrelevant</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span>
<a name="line-500"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-varid'>dep</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>noPostponing</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span>
<a name="line-501"></a> <span class='hs-varid'>unify</span> <span class='hs-layout'>(</span><span class='hs-varid'>unDom</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-502"></a> <span class='hs-varid'>arg</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>traverse</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>arg</span>
<a name="line-503"></a> <span class='hs-varid'>unifyArgs</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-varop'>`piApply`</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>arg</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-504"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-sel'>__IMPOSSIBLE__</span>
<a name="line-505"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>dependent</span> <span class='hs-layout'>(</span><span class='hs-conid'>Pi</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>NoAbs</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-506"></a> <span class='hs-varid'>dependent</span> <span class='hs-layout'>(</span><span class='hs-conid'>Pi</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>0</span> <span class='hs-varop'>`relevantIn`</span> <span class='hs-varid'>absBody</span> <span class='hs-varid'>c</span>
<a name="line-507"></a> <span class='hs-varid'>dependent</span> <span class='hs-layout'>(</span><span class='hs-conid'>Shared</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dependent</span> <span class='hs-layout'>(</span><span class='hs-varid'>derefPtr</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-508"></a> <span class='hs-varid'>dependent</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-509"></a>
<a name="line-510"></a> <span class='hs-comment'>-- | Check using conversion check.</span>
<a name="line-511"></a> <span class='hs-varid'>recheckEqualities</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-512"></a> <span class='hs-varid'>recheckEqualities</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-513"></a> <span class='hs-varid'>eqs</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>takeEqualities</span>
<a name="line-514"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>checkEqualities</span> <span class='hs-varid'>eqs</span>
<a name="line-515"></a>
<a name="line-516"></a> <span class='hs-comment'>-- | Check using unifier.</span>
<a name="line-517"></a> <span class='hs-varid'>recheckConstraints</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-518"></a> <span class='hs-varid'>recheckConstraints</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mapM_</span> <span class='hs-varid'>unifyEquality</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>takeEqualities</span>
<a name="line-519"></a>
<a name="line-520"></a> <span class='hs-varid'>unifyEquality</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Equality</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-521"></a> <span class='hs-varid'>unifyEquality</span> <span class='hs-layout'>(</span><span class='hs-conid'>Equal</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unifyHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-522"></a>
<a name="line-523"></a> <span class='hs-varid'>i</span> <span class='hs-varop'>|->></span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-524"></a> <span class='hs-varid'>i</span> <span class='hs-varop'>|-></span> <span class='hs-varid'>x</span>
<a name="line-525"></a> <span class='hs-varid'>recheckConstraints</span>
<a name="line-526"></a>
<a name="line-527"></a> <span class='hs-varid'>unifySizes</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-528"></a> <span class='hs-varid'>unifySizes</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-529"></a> <span class='hs-varid'>sz</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varid'>sizeType</span>
<a name="line-530"></a> <span class='hs-varid'>su</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sizeView</span> <span class='hs-varid'>u</span>
<a name="line-531"></a> <span class='hs-varid'>sv</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sizeView</span> <span class='hs-varid'>v</span>
<a name="line-532"></a> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>su</span><span class='hs-layout'>,</span> <span class='hs-varid'>sv</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-533"></a> <span class='hs-layout'>(</span><span class='hs-conid'>SizeSuc</span> <span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-conid'>SizeSuc</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unify</span> <span class='hs-varid'>sz</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-534"></a> <span class='hs-layout'>(</span><span class='hs-conid'>SizeSuc</span> <span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-conid'>SizeInf</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unify</span> <span class='hs-varid'>sz</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-535"></a> <span class='hs-layout'>(</span><span class='hs-conid'>SizeInf</span><span class='hs-layout'>,</span> <span class='hs-conid'>SizeSuc</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unify</span> <span class='hs-varid'>sz</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-536"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unifyAtom</span> <span class='hs-varid'>sz</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-537"></a>
<a name="line-538"></a> <span class='hs-comment'>-- | Possibly heterogeneous unification (but at same-shaped types).</span>
<a name="line-539"></a> <span class='hs-comment'>-- In het. situations, we only search for a mismatch!</span>
<a name="line-540"></a> <span class='hs-comment'>--</span>
<a name="line-541"></a> <span class='hs-comment'>-- TODO: eta for records!</span>
<a name="line-542"></a> <span class='hs-varid'>unifyHH</span> <span class='hs-keyglyph'>::</span>
<a name="line-543"></a> <span class='hs-conid'>TypeHH</span> <span class='hs-comment'>-- ^ one or two types, need not be in (u)reduced form</span>
<a name="line-544"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-545"></a> <span class='hs-varid'>unifyHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-546"></a> <span class='hs-varid'>u</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>.</span> <span class='hs-varid'>constructorForm</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>u</span>
<a name="line-547"></a> <span class='hs-varid'>v</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>.</span> <span class='hs-varid'>constructorForm</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>v</span>
<a name="line-548"></a> <span class='hs-varid'>aHH</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ureduce</span> <span class='hs-varid'>aHH</span>
<a name="line-549"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span>
<a name="line-550"></a> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyHH"</span>
<a name="line-551"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-layout'>(</span><span class='hs-varid'>parens</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span><span class='hs-layout'>)</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-str'>"=?="</span>
<a name="line-552"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>parens</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span>
<a name="line-553"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>":"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>aHH</span>
<a name="line-554"></a> <span class='hs-keyglyph'>]</span>
<a name="line-555"></a> <span class='hs-comment'>-- obtain the (== Size) function</span>
<a name="line-556"></a> <span class='hs-varid'>isSizeName</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varid'>isSizeNameTest</span>
<a name="line-557"></a>
<a name="line-558"></a> <span class='hs-comment'>-- check whether types have the same shape</span>
<a name="line-559"></a> <span class='hs-layout'>(</span><span class='hs-varid'>aHH</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>shapeViewHH</span> <span class='hs-varid'>aHH</span>
<a name="line-560"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>sh</span> <span class='hs-keyword'>of</span>
<a name="line-561"></a> <span class='hs-conid'>ElseSh</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-comment'>-- not a type or not same types</span>
<a name="line-562"></a>
<a name="line-563"></a> <span class='hs-conid'>DefSh</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isSizeName</span> <span class='hs-varid'>d</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>unifySizes</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-564"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-565"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-566"></a>
<a name="line-567"></a> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-keyglyph'>::</span>
<a name="line-568"></a> <span class='hs-conid'>TypeHH</span> <span class='hs-comment'>-- ^ in ureduced form</span>
<a name="line-569"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-570"></a> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-varid'>aHH0</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-571"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>aHH</span><span class='hs-layout'>,</span> <span class='hs-varid'>homogeneous</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>aHH0</span> <span class='hs-keyword'>of</span>
<a name="line-572"></a> <span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>aHH0</span><span class='hs-layout'>,</span> <span class='hs-conid'>True</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-573"></a> <span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>a1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>a2</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a1</span><span class='hs-layout'>,</span> <span class='hs-conid'>True</span><span class='hs-layout'>,</span> <span class='hs-varid'>a1</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- BRITTLE: just checking syn.eq.</span>
<a name="line-574"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>aHH0</span><span class='hs-layout'>,</span> <span class='hs-conid'>False</span><span class='hs-layout'>,</span> <span class='hs-sel'>__IMPOSSIBLE__</span><span class='hs-layout'>)</span>
<a name="line-575"></a> <span class='hs-comment'>-- use @a@ only if 'homogeneous' holds!</span>
<a name="line-576"></a>
<a name="line-577"></a> <span class='hs-varid'>fallback</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-578"></a>
<a name="line-579"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>15</span> <span class='hs-varop'>$</span>
<a name="line-580"></a> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"unifyAtom"</span>
<a name="line-581"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span> <span class='hs-varop'><></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>flexibleTerm</span> <span class='hs-varid'>u</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>text</span> <span class='hs-str'>" (flexible)"</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>empty</span>
<a name="line-582"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"=?="</span>
<a name="line-583"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span> <span class='hs-varop'><></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>flexibleTerm</span> <span class='hs-varid'>v</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>text</span> <span class='hs-str'>" (flexible)"</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>empty</span>
<a name="line-584"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>":"</span> <span class='hs-varop'><+></span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>aHH</span>
<a name="line-585"></a> <span class='hs-keyglyph'>]</span>
<a name="line-586"></a> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>ignoreSharing</span> <span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-varid'>ignoreSharing</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-587"></a> <span class='hs-comment'>-- Ulf, 2011-06-19</span>
<a name="line-588"></a> <span class='hs-comment'>-- We don't want to worry about levels here.</span>
<a name="line-589"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Level</span> <span class='hs-varid'>l</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-590"></a> <span class='hs-varid'>u</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reallyUnLevelView</span> <span class='hs-varid'>l</span>
<a name="line-591"></a> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-592"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>Level</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-593"></a> <span class='hs-varid'>v</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reallyUnLevelView</span> <span class='hs-varid'>l</span>
<a name="line-594"></a> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-595"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Var</span> <span class='hs-varid'>i</span> <span class='hs-varid'>us</span><span class='hs-layout'>,</span> <span class='hs-conid'>Var</span> <span class='hs-varid'>j</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-596"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Var</span> <span class='hs-varid'>i</span> <span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>homogeneous</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>flexible</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>i</span> <span class='hs-varop'>|->></span> <span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-597"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>Var</span> <span class='hs-varid'>j</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>homogeneous</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>flexible</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>j</span> <span class='hs-varop'>|->></span> <span class='hs-layout'>(</span><span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-598"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Con</span> <span class='hs-varid'>c</span> <span class='hs-varid'>us</span><span class='hs-layout'>,</span> <span class='hs-conid'>Con</span> <span class='hs-varid'>c'</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-599"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-varid'>c'</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-600"></a> <span class='hs-varid'>r</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ureduce</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>liftTCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>dataOrRecordTypeHH</span> <span class='hs-varid'>c</span> <span class='hs-varid'>aHH</span><span class='hs-layout'>)</span>
<a name="line-601"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>r</span> <span class='hs-keyword'>of</span>
<a name="line-602"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>a'HH</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-varid'>a'HH</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-603"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-604"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>constructorMismatchHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-605"></a> <span class='hs-comment'>-- Definitions are ok as long as they can't reduce (i.e. datatypes/axioms)</span>
<a name="line-606"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Def</span> <span class='hs-varid'>d</span> <span class='hs-varid'>us</span><span class='hs-layout'>,</span> <span class='hs-conid'>Def</span> <span class='hs-varid'>d'</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-607"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d</span> <span class='hs-varop'>==</span> <span class='hs-varid'>d'</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-608"></a> <span class='hs-comment'>-- d must be a data, record or axiom</span>
<a name="line-609"></a> <span class='hs-varid'>def</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getConstInfo</span> <span class='hs-varid'>d</span>
<a name="line-610"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ok</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>theDef</span> <span class='hs-varid'>def</span> <span class='hs-keyword'>of</span>
<a name="line-611"></a> <span class='hs-conid'>Datatype</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-612"></a> <span class='hs-conid'>Record</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-613"></a> <span class='hs-conid'>Axiom</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-614"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>False</span>
<a name="line-615"></a> <span class='hs-varid'>inj</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>optInjectiveTypeConstructors</span> <span class='hs-varop'><$></span> <span class='hs-varid'>pragmaOptions</span>
<a name="line-616"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>inj</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>ok</span>
<a name="line-617"></a> <span class='hs-keyword'>then</span> <span class='hs-varid'>unifyArgs</span> <span class='hs-layout'>(</span><span class='hs-varid'>defType</span> <span class='hs-varid'>def</span><span class='hs-layout'>)</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-618"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-619"></a> <span class='hs-comment'>-- Andreas, 2011-05-30: if heads disagree, abort</span>
<a name="line-620"></a> <span class='hs-comment'>-- but do not raise "mismatch" because otherwise type constructors</span>
<a name="line-621"></a> <span class='hs-comment'>-- would be distinct</span>
<a name="line-622"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>checkEqualityHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span> <span class='hs-comment'>-- typeError $ UnequalTerms CmpEq u v a</span>
<a name="line-623"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Lit</span> <span class='hs-varid'>l1</span><span class='hs-layout'>,</span> <span class='hs-conid'>Lit</span> <span class='hs-varid'>l2</span><span class='hs-layout'>)</span>
<a name="line-624"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>l1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>l2</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span>
<a name="line-625"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>constructorMismatchHH</span> <span class='hs-varid'>aHH</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-626"></a>
<a name="line-627"></a> <span class='hs-comment'>-- We can instantiate metas if the other term is inert (constructor application)</span>
<a name="line-628"></a> <span class='hs-comment'>-- Andreas, 2011-09-13: test/succeed/IndexInference needs this feature.</span>
<a name="line-629"></a> <span class='hs-layout'>(</span><span class='hs-conid'>MetaV</span> <span class='hs-varid'>m</span> <span class='hs-varid'>us</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>homogeneous</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-630"></a> <span class='hs-varid'>ok</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>instMeta</span> <span class='hs-varid'>a</span> <span class='hs-varid'>m</span> <span class='hs-varid'>us</span> <span class='hs-varid'>v</span>
<a name="line-631"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>40</span> <span class='hs-varop'>$</span>
<a name="line-632"></a> <span class='hs-varid'>vcat</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>fsep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"inst meta"</span><span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>then</span> <span class='hs-str'>"(ok)"</span> <span class='hs-keyword'>else</span> <span class='hs-str'>"(not ok)"</span> <span class='hs-keyglyph'>]</span>
<a name="line-633"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>u</span><span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-str'>":="</span><span class='hs-layout'>,</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>normalise</span> <span class='hs-varid'>u</span> <span class='hs-keyglyph'>]</span>
<a name="line-634"></a> <span class='hs-keyglyph'>]</span>
<a name="line-635"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>unify</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-636"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>addEquality</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-637"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>MetaV</span> <span class='hs-varid'>m</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>homogeneous</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-638"></a> <span class='hs-varid'>ok</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>instMeta</span> <span class='hs-varid'>a</span> <span class='hs-varid'>m</span> <span class='hs-varid'>vs</span> <span class='hs-varid'>u</span>
<a name="line-639"></a> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>40</span> <span class='hs-varop'>$</span>
<a name="line-640"></a> <span class='hs-varid'>vcat</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>fsep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"inst meta"</span><span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>then</span> <span class='hs-str'>"(ok)"</span> <span class='hs-keyword'>else</span> <span class='hs-str'>"(not ok)"</span> <span class='hs-keyglyph'>]</span>
<a name="line-641"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-str'>":="</span><span class='hs-layout'>,</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>normalise</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>]</span>
<a name="line-642"></a> <span class='hs-keyglyph'>]</span>
<a name="line-643"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>ok</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>unify</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-644"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>addEquality</span> <span class='hs-varid'>a</span> <span class='hs-varid'>u</span> <span class='hs-varid'>v</span>
<a name="line-645"></a>
<a name="line-646"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Con</span> <span class='hs-varid'>c</span> <span class='hs-varid'>us</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-647"></a> <span class='hs-varid'>md</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>isEtaRecordTypeHH</span> <span class='hs-varid'>aHH</span>
<a name="line-648"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>md</span> <span class='hs-keyword'>of</span>
<a name="line-649"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-650"></a> <span class='hs-layout'>(</span><span class='hs-varid'>tel</span><span class='hs-layout'>,</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>etaExpandRecord</span> <span class='hs-varid'>d</span> <span class='hs-layout'>(</span><span class='hs-varid'>rightHH</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span> <span class='hs-varid'>v</span>
<a name="line-651"></a> <span class='hs-varid'>b</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>getRecordConstructorType</span> <span class='hs-varid'>d</span>
<a name="line-652"></a> <span class='hs-varid'>bHH</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-varop'>`applyHH`</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span>
<a name="line-653"></a> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-varid'>bHH</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-654"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fallback</span>
<a name="line-655"></a>
<a name="line-656"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>Con</span> <span class='hs-varid'>c</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-657"></a> <span class='hs-varid'>md</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>isEtaRecordTypeHH</span> <span class='hs-varid'>aHH</span>
<a name="line-658"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>md</span> <span class='hs-keyword'>of</span>
<a name="line-659"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-660"></a> <span class='hs-layout'>(</span><span class='hs-varid'>tel</span><span class='hs-layout'>,</span> <span class='hs-varid'>us</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>etaExpandRecord</span> <span class='hs-varid'>d</span> <span class='hs-layout'>(</span><span class='hs-varid'>leftHH</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span> <span class='hs-varid'>u</span>
<a name="line-661"></a> <span class='hs-varid'>b</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>getRecordConstructorType</span> <span class='hs-varid'>d</span>
<a name="line-662"></a> <span class='hs-varid'>bHH</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ureduce</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-varop'>`applyHH`</span> <span class='hs-varid'>parsHH</span><span class='hs-layout'>)</span>
<a name="line-663"></a> <span class='hs-varid'>unifyConstructorArgs</span> <span class='hs-varid'>bHH</span> <span class='hs-varid'>us</span> <span class='hs-varid'>vs</span>
<a name="line-664"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fallback</span>
<a name="line-665"></a>
<a name="line-666"></a> <span class='hs-comment'>-- Andreas, 2011-05-30: If I put checkEquality below, then Issue81 fails</span>
<a name="line-667"></a> <span class='hs-comment'>-- because there are definitions blocked by flexibles that need postponement</span>
<a name="line-668"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fallback</span>
<a name="line-669"></a>
<a name="line-670"></a>
<a name="line-671"></a> <span class='hs-varid'>unify</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-672"></a> <span class='hs-varid'>unify</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unifyHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-673"></a>
<a name="line-674"></a> <span class='hs-varid'>unifyAtom</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>()</span>
<a name="line-675"></a> <span class='hs-varid'>unifyAtom</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unifyAtomHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-676"></a>
<a name="line-677"></a> <span class='hs-comment'>-- The contexts are transient when unifying, so we should just instantiate to</span>
<a name="line-678"></a> <span class='hs-comment'>-- constructor heads and generate fresh metas for the arguments. Beware of</span>
<a name="line-679"></a> <span class='hs-comment'>-- constructors that aren't fully applied.</span>
<a name="line-680"></a> <span class='hs-varid'>instMeta</span> <span class='hs-varid'>a</span> <span class='hs-varid'>m</span> <span class='hs-varid'>us</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-681"></a> <span class='hs-varid'>app</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>inertApplication</span> <span class='hs-varid'>a</span> <span class='hs-varid'>v</span>
<a name="line-682"></a> <span class='hs-varid'>reportSDoc</span> <span class='hs-str'>"tc.lhs.unify"</span> <span class='hs-num'>50</span> <span class='hs-varop'>$</span>
<a name="line-683"></a> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-str'>"inert"</span>
<a name="line-684"></a> <span class='hs-varop'><+></span> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>us</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>parens</span> <span class='hs-varop'>$</span> <span class='hs-varid'>prettyTCM</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>]</span>
<a name="line-685"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>nest</span> <span class='hs-num'>2</span> <span class='hs-varop'>$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"=="</span> <span class='hs-varop'><+></span> <span class='hs-varid'>text</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>app</span><span class='hs-layout'>)</span>
<a name="line-686"></a> <span class='hs-keyglyph'>]</span>
<a name="line-687"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>app</span> <span class='hs-keyword'>of</span>
<a name="line-688"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>False</span>
<a name="line-689"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>v'</span><span class='hs-layout'>,</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-690"></a> <span class='hs-varid'>margs</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyword'>do</span>
<a name="line-691"></a> <span class='hs-comment'>-- The new metas should have the same dependencies as the original meta</span>
<a name="line-692"></a> <span class='hs-varid'>mv</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>lookupMeta</span> <span class='hs-varid'>m</span>
<a name="line-693"></a>
<a name="line-694"></a> <span class='hs-comment'>-- Only generate metas for the arguments v' is actually applied to</span>
<a name="line-695"></a> <span class='hs-comment'>-- (in case of partial application)</span>
<a name="line-696"></a> <span class='hs-conid'>TelV</span> <span class='hs-varid'>tel0</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>telView</span> <span class='hs-varid'>b</span>
<a name="line-697"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>tel</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>telFromList</span> <span class='hs-varop'>$</span> <span class='hs-varid'>take</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-varid'>telToList</span> <span class='hs-varid'>tel0</span>
<a name="line-698"></a> <span class='hs-varid'>b'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>telePi</span> <span class='hs-varid'>tel</span> <span class='hs-layout'>(</span><span class='hs-varid'>sort</span> <span class='hs-conid'>Prop</span><span class='hs-layout'>)</span>
<a name="line-699"></a> <span class='hs-varid'>withMetaInfo'</span> <span class='hs-varid'>mv</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span>
<a name="line-700"></a> <span class='hs-varid'>tel</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getContextTelescope</span>
<a name="line-701"></a> <span class='hs-comment'>-- important: create the meta in the same environment as the original meta</span>
<a name="line-702"></a> <span class='hs-varid'>newArgsMetaCtx</span> <span class='hs-varid'>b'</span> <span class='hs-varid'>tel</span> <span class='hs-varid'>us</span>
<a name="line-703"></a> <span class='hs-varid'>noConstraints</span> <span class='hs-varop'>$</span> <span class='hs-varid'>assignV</span> <span class='hs-varid'>m</span> <span class='hs-varid'>us</span> <span class='hs-layout'>(</span><span class='hs-varid'>v'</span> <span class='hs-varop'>`apply`</span> <span class='hs-varid'>margs</span><span class='hs-layout'>)</span>
<a name="line-704"></a> <span class='hs-varid'>return</span> <span class='hs-conid'>True</span>
<a name="line-705"></a> <span class='hs-varop'>`catchError`</span> <span class='hs-keyglyph'>\</span><span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>False</span>
<a name="line-706"></a>
<a name="line-707"></a> <span class='hs-varid'>inertApplication</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Term</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Term</span><span class='hs-layout'>,</span> <span class='hs-conid'>Type</span><span class='hs-layout'>,</span> <span class='hs-conid'>Args</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-708"></a> <span class='hs-varid'>inertApplication</span> <span class='hs-varid'>a</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span>
<a name="line-709"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ignoreSharing</span> <span class='hs-varid'>v</span> <span class='hs-keyword'>of</span>
<a name="line-710"></a> <span class='hs-conid'>Con</span> <span class='hs-varid'>c</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Con</span> <span class='hs-varid'>c</span> <span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>dataOrRecordType</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a</span>
<a name="line-711"></a> <span class='hs-conid'>Def</span> <span class='hs-varid'>d</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>do</span>
<a name="line-712"></a> <span class='hs-varid'>def</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getConstInfo</span> <span class='hs-varid'>d</span>
<a name="line-713"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ans</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>Def</span> <span class='hs-varid'>d</span> <span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-varid'>defType</span> <span class='hs-varid'>def</span><span class='hs-layout'>,</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-714"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>theDef</span> <span class='hs-varid'>def</span> <span class='hs-keyword'>of</span>
<a name="line-715"></a> <span class='hs-conid'>Datatype</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ans</span>
<a name="line-716"></a> <span class='hs-conid'>Record</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ans</span>
<a name="line-717"></a> <span class='hs-conid'>Axiom</span><span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ans</span>
<a name="line-718"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Nothing</span>
<a name="line-719"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>Nothing</span>
<a name="line-720"></a>
<a name="line-721"></a><a name="dataOrRecordType"></a><span class='hs-comment'>-- | Given the type of a constructor application the corresponding</span>
<a name="line-722"></a><span class='hs-comment'>-- data or record type, applied to its parameters (extracted from the</span>
<a name="line-723"></a><span class='hs-comment'>-- given type), is returned.</span>
<a name="line-724"></a><span class='hs-comment'>--</span>
<a name="line-725"></a><span class='hs-comment'>-- Precondition: The type has to correspond to an application of the</span>
<a name="line-726"></a><span class='hs-comment'>-- given constructor.</span>
<a name="line-727"></a><span class='hs-definition'>dataOrRecordType</span>
<a name="line-728"></a> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>QName</span> <span class='hs-comment'>-- ^ Constructor name.</span>
<a name="line-729"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Type</span> <span class='hs-comment'>-- ^ Type of constructor application (must end in data/record).</span>
<a name="line-730"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Type</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ Type of constructor, applied to pars.</span>
<a name="line-731"></a><span class='hs-definition'>dataOrRecordType</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-varop'>`apply`</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>dataOrRecordType'</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a</span>
<a name="line-732"></a>
<a name="line-733"></a><a name="dataOrRecordType'"></a><span class='hs-definition'>dataOrRecordType'</span> <span class='hs-keyglyph'>::</span>
<a name="line-734"></a> <span class='hs-conid'>QName</span> <span class='hs-comment'>-- ^ Constructor name.</span>
<a name="line-735"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Type</span> <span class='hs-comment'>-- ^ Type of constructor application (must end in data/record).</span>
<a name="line-736"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>QName</span><span class='hs-layout'>,</span> <span class='hs-conid'>Type</span><span class='hs-layout'>,</span> <span class='hs-conid'>Args</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-737"></a> <span class='hs-comment'>-- ^ Name of data/record type,</span>
<a name="line-738"></a> <span class='hs-comment'>-- type of constructor to be applied, and</span>
<a name="line-739"></a> <span class='hs-comment'>-- data/record parameters</span>
<a name="line-740"></a><span class='hs-definition'>dataOrRecordType'</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-741"></a> <span class='hs-comment'>-- The telescope ends with a datatype or a record.</span>
<a name="line-742"></a> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyword'>do</span>
<a name="line-743"></a> <span class='hs-conid'>TelV</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>El</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>def</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>telView</span> <span class='hs-varid'>a</span>
<a name="line-744"></a> <span class='hs-keyword'>let</span> <span class='hs-conid'>Def</span> <span class='hs-varid'>d</span> <span class='hs-varid'>args</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ignoreSharing</span> <span class='hs-varid'>def</span>
<a name="line-745"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span>
<a name="line-746"></a> <span class='hs-varid'>def</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>theDef</span> <span class='hs-varop'><$></span> <span class='hs-varid'>getConstInfo</span> <span class='hs-varid'>d</span>
<a name="line-747"></a> <span class='hs-varid'>r</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>def</span> <span class='hs-keyword'>of</span>
<a name="line-748"></a> <span class='hs-conid'>Datatype</span><span class='hs-layout'>{</span><span class='hs-varid'>dataPars</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Just</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-conid'>(,)</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>defType</span> <span class='hs-varop'><$></span> <span class='hs-varid'>getConstInfo</span> <span class='hs-varid'>c</span>
<a name="line-749"></a> <span class='hs-conid'>Record</span> <span class='hs-layout'>{</span><span class='hs-varid'>recPars</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Just</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-conid'>(,)</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>getRecordConstructorType</span> <span class='hs-varid'>d</span>
<a name="line-750"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>Nothing</span>
<a name="line-751"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-layout'>,</span> <span class='hs-varid'>a'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>a'</span><span class='hs-layout'>,</span> <span class='hs-varid'>genericTake</span> <span class='hs-varid'>n</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>r</span>
<a name="line-752"></a>
<a name="line-753"></a><a name="dataOrRecordTypeHH"></a><span class='hs-comment'>-- | Heterogeneous situation.</span>
<a name="line-754"></a><span class='hs-comment'>-- @a1@ and @a2@ need to end in same datatype/record.</span>
<a name="line-755"></a><span class='hs-definition'>dataOrRecordTypeHH</span> <span class='hs-keyglyph'>::</span>
<a name="line-756"></a> <span class='hs-conid'>QName</span> <span class='hs-comment'>-- ^ Constructor name.</span>
<a name="line-757"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TypeHH</span> <span class='hs-comment'>-- ^ Type(s) of constructor application (must end in same data/record).</span>
<a name="line-758"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TCM</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>TypeHH</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ Type of constructor, instantiated possibly heterogeneously to parameters.</span>
<a name="line-759"></a><span class='hs-definition'>dataOrRecordTypeHH</span> <span class='hs-varid'>c</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-conid'>Hom</span> <span class='hs-varop'><$></span> <span class='hs-varid'>dataOrRecordType</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a</span>
<a name="line-760"></a><span class='hs-definition'>dataOrRecordTypeHH</span> <span class='hs-varid'>c</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-761"></a> <span class='hs-varid'>r1</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>dataOrRecordType'</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a1</span>
<a name="line-762"></a> <span class='hs-varid'>r2</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>dataOrRecordType'</span> <span class='hs-varid'>c</span> <span class='hs-varid'>a2</span> <span class='hs-comment'>-- b2 may have different parameters than b1!</span>
<a name="line-763"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>r1</span><span class='hs-layout'>,</span> <span class='hs-varid'>r2</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-764"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d1</span><span class='hs-layout'>,</span> <span class='hs-varid'>b1</span><span class='hs-layout'>,</span> <span class='hs-varid'>pars1</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d2</span><span class='hs-layout'>,</span> <span class='hs-varid'>b2</span><span class='hs-layout'>,</span> <span class='hs-varid'>pars2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>d2</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Just</span> <span class='hs-varop'>$</span>
<a name="line-765"></a> <span class='hs-comment'>-- Andreas, 2011-09-15 if no parameters, we can stay homogeneous</span>
<a name="line-766"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>null</span> <span class='hs-varid'>pars1</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>null</span> <span class='hs-varid'>pars2</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>b1</span>
<a name="line-767"></a> <span class='hs-comment'>-- if parameters, go heterogeneous</span>
<a name="line-768"></a> <span class='hs-comment'>-- TODO: make this smarter, because parameters could be equal!</span>
<a name="line-769"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>Het</span> <span class='hs-layout'>(</span><span class='hs-varid'>b1</span> <span class='hs-varop'>`apply`</span> <span class='hs-varid'>pars1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b2</span> <span class='hs-varop'>`apply`</span> <span class='hs-varid'>pars2</span><span class='hs-layout'>)</span>
<a name="line-770"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Nothing</span>
<a name="line-771"></a>
<a name="line-772"></a><a name="isEtaRecordTypeHH"></a><span class='hs-comment'>-- | Return record type identifier if argument is a record type.</span>
<a name="line-773"></a><span class='hs-definition'>isEtaRecordTypeHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>MonadTCM</span> <span class='hs-varid'>tcm</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>tcm</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>QName</span><span class='hs-layout'>,</span> <span class='hs-conid'>HomHet</span> <span class='hs-conid'>Args</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-774"></a><span class='hs-definition'>isEtaRecordTypeHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>liftTCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>isEtaRecordType</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-775"></a><span class='hs-definition'>isEtaRecordTypeHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-776"></a> <span class='hs-varid'>m1</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>isEtaRecordType</span> <span class='hs-varid'>a1</span>
<a name="line-777"></a> <span class='hs-varid'>m2</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>liftTCM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>isEtaRecordType</span> <span class='hs-varid'>a2</span>
<a name="line-778"></a> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>m1</span><span class='hs-layout'>,</span> <span class='hs-varid'>m2</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-779"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d1</span><span class='hs-layout'>,</span> <span class='hs-varid'>as1</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d2</span><span class='hs-layout'>,</span> <span class='hs-varid'>as2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>d2</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>d1</span><span class='hs-layout'>,</span> <span class='hs-conid'>Het</span> <span class='hs-varid'>as1</span> <span class='hs-varid'>as2</span><span class='hs-layout'>)</span>
<a name="line-780"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>Nothing</span>
<a name="line-781"></a>
<a name="line-782"></a>
<a name="line-783"></a><a name="ShapeView"></a><span class='hs-comment'>-- | Views an expression (pair) as type shape. Fails if not same shape.</span>
<a name="line-784"></a><a name="ShapeView"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ShapeView</span> <span class='hs-varid'>a</span>
<a name="line-785"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PiSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-786"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>FunSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>a</span>
<a name="line-787"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>DefSh</span> <span class='hs-conid'>QName</span> <span class='hs-comment'>-- ^ data/record</span>
<a name="line-788"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>VarSh</span> <span class='hs-conid'>Nat</span> <span class='hs-comment'>-- ^ neutral type</span>
<a name="line-789"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>LitSh</span> <span class='hs-conid'>Literal</span> <span class='hs-comment'>-- ^ built-in type</span>
<a name="line-790"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>SortSh</span>
<a name="line-791"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>MetaSh</span> <span class='hs-comment'>-- ^ some meta</span>
<a name="line-792"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>ElseSh</span> <span class='hs-comment'>-- ^ not a type or not definitely same shape</span>
<a name="line-793"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Typeable</span><span class='hs-layout'>,</span> <span class='hs-conid'>Show</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span><span class='hs-layout'>,</span> <span class='hs-conid'>Functor</span><span class='hs-layout'>)</span>
<a name="line-794"></a>
<a name="line-795"></a><a name="shapeView"></a><span class='hs-comment'>-- | Return the type and its shape. Expects input in (u)reduced form.</span>
<a name="line-796"></a><span class='hs-definition'>shapeView</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Type</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-layout'>(</span><span class='hs-conid'>Type</span><span class='hs-layout'>,</span> <span class='hs-conid'>ShapeView</span> <span class='hs-conid'>Type</span><span class='hs-layout'>)</span>
<a name="line-797"></a><span class='hs-definition'>shapeView</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-798"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ignoreSharing</span> <span class='hs-varop'>$</span> <span class='hs-varid'>unEl</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>of</span>
<a name="line-799"></a> <span class='hs-conid'>Pi</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>NoAbs</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FunSh</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span>
<a name="line-800"></a> <span class='hs-conid'>Pi</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PiSh</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-801"></a> <span class='hs-conid'>Def</span> <span class='hs-varid'>d</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>DefSh</span> <span class='hs-varid'>d</span>
<a name="line-802"></a> <span class='hs-conid'>Var</span> <span class='hs-varid'>x</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>VarSh</span> <span class='hs-varid'>x</span>
<a name="line-803"></a> <span class='hs-conid'>Lit</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LitSh</span> <span class='hs-varid'>l</span>
<a name="line-804"></a> <span class='hs-conid'>Sort</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SortSh</span>
<a name="line-805"></a> <span class='hs-conid'>MetaV</span> <span class='hs-varid'>m</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>MetaSh</span>
<a name="line-806"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ElseSh</span>
<a name="line-807"></a>
<a name="line-808"></a><a name="shapeViewHH"></a><span class='hs-comment'>-- | Return the reduced type(s) and the common shape.</span>
<a name="line-809"></a><span class='hs-definition'>shapeViewHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeHH</span><span class='hs-layout'>,</span> <span class='hs-conid'>ShapeView</span> <span class='hs-conid'>TypeHH</span><span class='hs-layout'>)</span>
<a name="line-810"></a><span class='hs-definition'>shapeViewHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-811"></a> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>shapeView</span> <span class='hs-varid'>a</span>
<a name="line-812"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Hom</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>fmap</span> <span class='hs-conid'>Hom</span> <span class='hs-varid'>sh</span><span class='hs-layout'>)</span>
<a name="line-813"></a><span class='hs-definition'>shapeViewHH</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-814"></a> <span class='hs-layout'>(</span><span class='hs-varid'>a1</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh1</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>shapeView</span> <span class='hs-varid'>a1</span>
<a name="line-815"></a> <span class='hs-layout'>(</span><span class='hs-varid'>a2</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>shapeView</span> <span class='hs-varid'>a2</span>
<a name="line-816"></a> <span class='hs-varid'>return</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>,</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>sh1</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh2</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-817"></a>
<a name="line-818"></a> <span class='hs-layout'>(</span><span class='hs-conid'>PiSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h1</span> <span class='hs-varid'>r1</span> <span class='hs-varid'>a1</span><span class='hs-layout'>)</span> <span class='hs-varid'>b1</span><span class='hs-layout'>,</span> <span class='hs-conid'>PiSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h2</span> <span class='hs-varid'>r2</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-varid'>b2</span><span class='hs-layout'>)</span>
<a name="line-819"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>h1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>h2</span> <span class='hs-keyglyph'>-></span>
<a name="line-820"></a> <span class='hs-conid'>PiSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h1</span> <span class='hs-layout'>(</span><span class='hs-varid'>min</span> <span class='hs-varid'>r1</span> <span class='hs-varid'>r2</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-layout'>(</span><span class='hs-varid'>absName</span> <span class='hs-varid'>b1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-layout'>(</span><span class='hs-varid'>absBody</span> <span class='hs-varid'>b1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>absBody</span> <span class='hs-varid'>b2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-821"></a>
<a name="line-822"></a> <span class='hs-layout'>(</span><span class='hs-conid'>FunSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h1</span> <span class='hs-varid'>r1</span> <span class='hs-varid'>a1</span><span class='hs-layout'>)</span> <span class='hs-varid'>b1</span><span class='hs-layout'>,</span> <span class='hs-conid'>FunSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h2</span> <span class='hs-varid'>r2</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span> <span class='hs-varid'>b2</span><span class='hs-layout'>)</span>
<a name="line-823"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>h1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>h2</span> <span class='hs-keyglyph'>-></span>
<a name="line-824"></a> <span class='hs-conid'>FunSh</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dom</span> <span class='hs-varid'>h1</span> <span class='hs-layout'>(</span><span class='hs-varid'>min</span> <span class='hs-varid'>r1</span> <span class='hs-varid'>r2</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>a1</span> <span class='hs-varid'>a2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Het</span> <span class='hs-varid'>b1</span> <span class='hs-varid'>b2</span><span class='hs-layout'>)</span>
<a name="line-825"></a>
<a name="line-826"></a> <span class='hs-layout'>(</span><span class='hs-conid'>DefSh</span> <span class='hs-varid'>d1</span><span class='hs-layout'>,</span> <span class='hs-conid'>DefSh</span> <span class='hs-varid'>d2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>d2</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>DefSh</span> <span class='hs-varid'>d1</span>
<a name="line-827"></a> <span class='hs-layout'>(</span><span class='hs-conid'>VarSh</span> <span class='hs-varid'>x1</span><span class='hs-layout'>,</span> <span class='hs-conid'>VarSh</span> <span class='hs-varid'>x2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>VarSh</span> <span class='hs-varid'>x1</span>
<a name="line-828"></a> <span class='hs-layout'>(</span><span class='hs-conid'>LitSh</span> <span class='hs-varid'>l1</span><span class='hs-layout'>,</span> <span class='hs-conid'>LitSh</span> <span class='hs-varid'>l2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>l1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>l2</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>LitSh</span> <span class='hs-varid'>l1</span>
<a name="line-829"></a> <span class='hs-layout'>(</span><span class='hs-conid'>SortSh</span><span class='hs-layout'>,</span> <span class='hs-conid'>SortSh</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SortSh</span>
<a name="line-830"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>ElseSh</span> <span class='hs-comment'>-- not types, or metas, or not same shape</span>
<a name="line-831"></a>
<a name="line-832"></a>
<a name="line-833"></a><a name="telViewUpToHH"></a><span class='hs-comment'>-- | @telViewUpToHH n t@ takes off the first @n@ function types of @t@.</span>
<a name="line-834"></a><span class='hs-comment'>-- Takes off all if $n < 0$.</span>
<a name="line-835"></a><span class='hs-definition'>telViewUpToHH</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TypeHH</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Unify</span> <span class='hs-conid'>TelViewHH</span>
<a name="line-836"></a><span class='hs-definition'>telViewUpToHH</span> <span class='hs-num'>0</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>TelV</span> <span class='hs-conid'>EmptyTel</span> <span class='hs-varid'>t</span>
<a name="line-837"></a><span class='hs-definition'>telViewUpToHH</span> <span class='hs-varid'>n</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-838"></a> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-varid'>sh</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>shapeViewHH</span> <span class='hs-varop'>=<<</span> <span class='hs-varid'>liftTCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>traverse</span> <span class='hs-varid'>reduce</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-839"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>sh</span> <span class='hs-keyword'>of</span>
<a name="line-840"></a> <span class='hs-conid'>PiSh</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>absV</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-varid'>absName</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>telViewUpToHH</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>absBody</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-841"></a> <span class='hs-conid'>FunSh</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>absV</span> <span class='hs-varid'>a</span> <span class='hs-str'>"_"</span> <span class='hs-varop'><$></span> <span class='hs-varid'>telViewUpToHH</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>raise</span> <span class='hs-num'>1</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-842"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-varop'>$</span> <span class='hs-conid'>TelV</span> <span class='hs-conid'>EmptyTel</span> <span class='hs-varid'>t</span>
<a name="line-843"></a> <span class='hs-keyword'>where</span>
<a name="line-844"></a> <span class='hs-varid'>absV</span> <span class='hs-varid'>a</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-conid'>TelV</span> <span class='hs-varid'>tel</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>TelV</span> <span class='hs-layout'>(</span><span class='hs-conid'>ExtendTel</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Abs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>tel</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span>
</pre></body>
</html>
