Sophie: ghc-0:6.10.4-1mdv2010.0 i586

ghc-6.10.4-1mdv2010.0.i586.rpm

<!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
>Dataflow</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"
></SCRIPT
><SCRIPT TYPE="text/javascript"
>window.onload = function () {setSynopsis("mini_Dataflow.html")};</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"
>ghc-6.10.4: The GHC API</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"
>Dataflow</FONT
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></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"
><A HREF="#v%3Afixedpoint"
>fixedpoint</A
> ::  (node -&gt; [node]) -&gt; (node -&gt; <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> node -&gt; s -&gt; <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> s) -&gt; [node] -&gt; s -&gt; s</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"
><A NAME="v:fixedpoint"
><A NAME="v%3Afixedpoint"
></A
></A
><B
>fixedpoint</B
> ::  (node -&gt; [node]) -&gt; (node -&gt; <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> node -&gt; s -&gt; <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> s) -&gt; [node] -&gt; s -&gt; s</TD
></TR
><TR
><TD CLASS="doc"
><P
>Solve the fixed-point of a dataflow problem.
</P
><P
>Complexity: O(N+H*E) calls to the update function where:
   N = number of nodes,
   E = number of edges,
   H = maximum height of the lattice for any particular node.
</P
><P
>Sketch for proof of complexity:
 Note that the state is threaded through the entire execution.
 Also note that the height of the latice at any particular node
 is the number of times update can return non-Nothing for a
 particular node.  Every call (except for the top level one)
 must be caused by a non-Nothing result and each non-Nothing
 result causes as many calls as it has out-going edges.
 Thus any particular node, n, may cause in total at
 most H*out(n) further calls.  When summed over all nodes,
 that is H*E.  The N term of the complexity is from the initial call
 when update will be passed <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
>.
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 2.4.2</TD
></TR
></TABLE
></BODY
></HTML
>