<br>
Oops, I just realized that you gave me the answer, namely that it won't find fixed points of numeric sets of equations.<br>
<br>
Pity, that would really have made Haskell useful for this kind of scientific computing.<br>
<br>
<br><br><div><span class="gmail_quote">On 4/5/06, <b class="gmail_sendername">Brandon Moore</b> &lt;<a href="mailto:brandonm@yahoo-inc.com">brandonm@yahoo-inc.com</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Michael Goodrich wrote:<br>&gt; Looks like my calulation involves a self referential set of definitions.<br>&gt;<br>&gt; Is Haskell not able to deal with a self referential set of definitions?<br>&gt;<br>&gt;&nbsp;&nbsp;I was frankly hoing it would since otherwise there is then&nbsp;&nbsp;the specter
<br>&gt; of sequence, i.e. that I have to finesse the order in which things are<br>&gt; calculated so as to avoid it.<br>&gt;<br>&gt; Thoughts?<br><br>Lazy evaluation is great with self-referential definitions, but id<br>
doesn't do so well with ill-founded definitions. It also won't find<br>fixpoints of numeric equations. Here are some examples, and then some<br>explanation.<br><br>Things that work:<br><br>{- for interactive use in ghci -}
<br>let ones = 1:ones<br>--infinite list of ones<br>let counting = 1:map (+1) counting<br>-- infinite list counting up from one<br>let fibs = 1:1:zipWith (+) fibs (tail fibs)<br>--fibbonacci numbers<br><br>{- A larger program.
<br>&nbsp;&nbsp;&nbsp;&nbsp;turns references by name into direct references<br>&nbsp;&nbsp;&nbsp;&nbsp;Try on a cyclic graph, like<br>&nbsp;&nbsp;&nbsp;&nbsp;buildGraph [(&quot;a&quot;,[&quot;b&quot;]),(&quot;b&quot;,[&quot;a&quot;])]<br>&nbsp;&nbsp;-}<br>import Data.List<br>import Data.Map
 as Map<br><br>data Node = Node String [Node]<br>type NodeDesc = (String, [String])<br><br>buildNode :: Map String Node -&gt; NodeDesc -&gt; Node<br>buildNode env (name,outlinks) =<br>&nbsp;&nbsp; Node name (concat [Map.lookup other finalBinds | other &lt;- outlinks])
<br><br>buildGraph :: [(String,[String])] -&gt; [Node]<br>buildGraph descs = nodes<br>&nbsp;&nbsp; where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; buildExtend binds desc@(name,_) =<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let node = buildNode finalBinds desc
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;in (Map.insert name node binds, node)<br><br><br>Things that will not work:<br><br>let x = x<br>-- no information on how to define x<br><br>let x = 2*x + 1<br>-- this is not treated algebraically<br><br>
let broke = 1:zipWith (+) broke (tail broke)<br>-- the second element depends on itself<br><br><br>Recursive definitions in Haskell can be explained by<br>saying that they find the least-defined fixedpoint of the equations.
<br>Every type in Haskell has all the usual values you would have in a<br>strict language, plus an undefined value which corresponds to a<br>nonterminating computation. Also, there are values where subterms<br>of different types are undefined values of that type rather.
<br><br>For example, with pairs of numbers there are these posibilites<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (x,y)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;&nbsp;&nbsp;&nbsp; \<br>(_|_,x)&nbsp;&nbsp; (x,|_|)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\&nbsp;&nbsp;&nbsp;&nbsp; /<br>&nbsp;&nbsp;&nbsp;&nbsp; (_|_,_|_)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_|_<br>where x and y represent any defined number, and _|_ is &quot;undefined&quot;,
<br>or a non-terminating computation. A value on any line is<br>considered more defined than values on lower lines. Any value which can<br>be obtained from another by replacing subterms with _|_ is less defined,<br>if neither can be made from the other that way than neither is more
<br>defined that the other.<br><br><br>Think of a definition like x = f x. That will make x the least-defined<br>value which is a fixedpoint of f. For example, numeric operations are<br>(generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and
<br>_|_ is a fixedpoint of \x -&gt; 2*x + 1.<br><br>for broke, consider the function f = \l -&gt; 1:(zipWith (+) l (tail l))<br>f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = 1:zipWith (+) (1:_|_) _|_<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = 1:_|_<br>so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because<br>_|_:_|_ is not a fixedpoint, and<br>f _|_ = 1:&lt;something&gt;, so _|_ is not a fixedpoint either. If I try that<br>definition of broke, ghci prints &quot;[1&quot; and hangs, indicating that the
<br>rest of the list is undefined.<br><br>If multiple definitions are involved, think of a function on a tuple of<br>all the definitions:<br><br>x = y<br>y = 1:x<br><br>corresponds to the least fixedpoint of (\(x,y) -&gt; (y,1:x))
<br><br>The recursiveness in the graph example is more tedious to analyze like<br>this, but it works out the same way - whatever value of &quot;finalBinds&quot; is<br>fed into the recursive equation, you get out a map built by taking the
<br>empty map and adding a binding for each node name. Chase it around a few<br>more times, and you'll get some detail about the nodes.<br><br>Also, posting code really helps if you want specific advice. Thanks to<br>the hard work of compiler writers, the error message are usually precise
<br>enough for a message like this to describe the possibilites. If you<br>enjoy my rambling I suppose you should keep posting error messages :)<br><br>Brandon<br><br>&gt; cheers,<br>&gt;<br>&gt; -Mike<br>&gt;<br>&gt;<br>
&gt; ------------------------------------------------------------------------<br>&gt;<br>&gt; _______________________________________________<br>&gt; Haskell-Cafe mailing list<br>&gt; <a href="mailto:Haskell-Cafe@haskell.org">
Haskell-Cafe@haskell.org</a><br>&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br><br><br></blockquote></div><br>