packages feed

ChasingBottoms-1.2.2: docs/Test-ChasingBottoms-Approx.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--Rendered using the Haskell Html Library v0.2-->
<HTML
><HEAD
><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
><TITLE
>Test.ChasingBottoms.Approx</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock.js" TYPE="text/javascript"
></SCRIPT
></HEAD
><BODY
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="topbar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
></TD
><TD CLASS="title"
>Chasing Bottoms</TD
><TD CLASS="topbut"
><A HREF="index.html"
>Contents</A
></TD
><TD CLASS="topbut"
><A HREF="doc-index.html"
>Index</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="modulebar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><FONT SIZE="6"
>Test.ChasingBottoms.Approx</FONT
></TD
><TD ALIGN="right"
><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="infohead"
>Portability</TD
><TD CLASS="infoval"
>non-portable (GHC-specific)</TD
></TR
><TR
><TD CLASS="infohead"
>Stability</TD
><TD CLASS="infoval"
>experimental</TD
></TR
><TR
><TD CLASS="infohead"
>Maintainer</TD
><TD CLASS="infoval"
>http://www.cs.chalmers.se/~nad/</TD
></TR
></TABLE
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Description</TD
></TR
><TR
><TD CLASS="doc"
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Synopsis</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>class</SPAN
> <A HREF="#t%3AApprox"
>Approx</A
> a  <SPAN CLASS="keyword"
>where</SPAN
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="#v%3AapproxAll"
>approxAll</A
> :: <A HREF="Test-ChasingBottoms-Nat.html#t%3ANat"
>Nat</A
> -&gt; a -&gt; a</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aapprox"
>approx</A
> :: <A HREF="Test-ChasingBottoms-Nat.html#t%3ANat"
>Nat</A
> -&gt; a -&gt; a</TD
></TR
></TABLE
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Documentation</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>class</SPAN
> <A NAME="t%3AApprox"
></A
><B
>Approx</B
> a  <SPAN CLASS="keyword"
>where</SPAN
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="ndoc"
><P
><TT
><A HREF="Test-ChasingBottoms-Approx.html#t%3AApprox"
>Approx</A
></TT
> is a class for approximation functions as described
in The generic approximation lemma, Graham Hutton and Jeremy
Gibbons, Information Processing Letters, 79(4):197-201, Elsevier
Science, August 2001, <A HREF="http://www.cs.nott.ac.uk/~gmh/bib.html"
>http://www.cs.nott.ac.uk/~gmh/bib.html</A
>.
</P
><P
>Instances are provided for all members of the <TT
><A HREF="http://www.haskell.org/ghc/docs/latest/html/libraries/base-3.0.0.0/Data-Generics-Basics.html#t%3AData"
>Data</A
></TT
> type class. Due
to the limitations of the <A HREF="http://www.haskell.org/ghc/docs/latest/html/libraries/base-3.0.0.0/Data-Generics.html"
>Data.Generics</A
> approach to generic
programming, which is not really aimed at this kind of application,
the implementation is only guaranteed to perform correctly, with
respect to the paper (and modulo any bugs), on non-mutually-recursive
sum-of-products datatypes. In particular, nested and mutually
recursive types are not handled correctly with respect to the
paper. The specification below is correct, though (if we assume that
the <TT
><A HREF="http://www.haskell.org/ghc/docs/latest/html/libraries/base-3.0.0.0/Data-Generics-Basics.html#t%3AData"
>Data</A
></TT
> instances are well-behaved).
</P
><P
>In practice the <TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3AapproxAll"
>approxAll</A
></TT
> function can probably be more useful than
<TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3Aapprox"
>approx</A
></TT
>. It traverses down <EM
>all</EM
> subterms, and it should be possible
to prove a variant of the approximation lemma which <TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3AapproxAll"
>approxAll</A
></TT
>
satisfies.
</P
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="section4"
>Methods</TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A NAME="v%3AapproxAll"
></A
><B
>approxAll</B
> :: <A HREF="Test-ChasingBottoms-Nat.html#t%3ANat"
>Nat</A
> -&gt; a -&gt; a</TD
></TR
><TR
><TD CLASS="doc"
><TT
><TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3AapproxAll"
>approxAll</A
></TT
> n x</TT
> traverses <TT
>n</TT
> levels down in <TT
>x</TT
> and replaces all
 values at that level with bottoms.
</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v%3Aapprox"
></A
><B
>approx</B
> :: <A HREF="Test-ChasingBottoms-Nat.html#t%3ANat"
>Nat</A
> -&gt; a -&gt; a</TD
></TR
><TR
><TD CLASS="doc"
><TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3Aapprox"
>approx</A
></TT
> works like <TT
><A HREF="Test-ChasingBottoms-Approx.html#v%3AapproxAll"
>approxAll</A
></TT
>, but the traversal and
 replacement is only performed at subterms of the same monomorphic
 type as the original term. For polynomial datatypes this is
 exactly what the version of <TT
>approx</TT
> described in the paper above
 does.
</TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="section4"
><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Approx')" ALT="show/hide"
> Instances</TD
></TR
><TR
><TD CLASS="body"
><DIV ID="i:Approx" STYLE="display:block;"
><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="http://www.haskell.org/ghc/docs/latest/html/libraries/base-3.0.0.0/Data-Generics-Basics.html#t%3AData"
>Data</A
> a =&gt; <A HREF="Test-ChasingBottoms-Approx.html#t%3AApprox"
>Approx</A
> a</TD
></TR
></TABLE
></DIV
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 0.7</TD
></TR
></TABLE
></BODY
></HTML
>