[Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime
robdockins at fastmail.fm
Thu Apr 6 13:00:54 EDT 2006
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
[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
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).
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell-Cafe