[Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime error message:

[Robert Dockins]

On Apr 6, 2006, at 11:25 AM, Michael Goodrich wrote:

> Thanks so much for your help. I should have made clear that I was  
> aware that the definitions were mutually dependent.  What I was  
> hoping was that Haskell could solve this for me without my having  
> to resort to effectively finessing any sequencing considerations.
>
> Perhaps I am really asking it to do too much.
>
> This I thought might be reasonable since one is supposed to be  
> achieving a sequence-less style of programming.  But this would  
> seem to be a counter example where  I will be essentially forced to  
> implement a sequential processing semantic in a language  
> environment which ostensibly would deny me such (for my own good I  
> understand).
>
> Thoughts?

[snip a bunch of code]

I'm not an expert, but I'll take a crack at this.  What you seem to  
want is a numeric fixpoint, wherein each variable in the mutually  
recursive set of equations is assigned a value that causes all  
equations to hold.  This is called a fixpoint because it represents a  
point where the function in n-space generated by the n equations maps  
to itself.

The notion of a fixpoint usually found in functional programming  
languages is a little different -- it is specifically the "least  
fixed point".  Now, I'm getting a little out of my depth here, but I  
think that the Kleene fixpoint theorem tells us that the least  
fixpoint of the kind of function in the previous paragraph must be  
bottom - ie, non-termination (which, GHC can sometimes detect, in  
which case it prints the <<loop>> error you saw).  You can't use the  
least fixpoint mechanism that the programming language gives you to  
calculate the those kind of numeric fixpoints, because the least  
fixpoint is completely uninteresting and not what you want.

In haskell, the standard techinque for this kind of thing is to  
calculate an "infinite" list of successive approximations to the  
answer and choosing an element from the list according to some  
criteria (usually absolute or relative convergence of successive  
elements).  You can easily build such a list with 'Data.List.iterate'.

This should work for all attractive fixpoints of the function when  
given an appropriate initial approximation (modulo floating point  
rounding errors, as always).



Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG