[Haskell] Fwd: Mutually dependent functions

[Tillmann Rendel]

Hi Michael,

Michael Speer schrieb:
> I know it is possible with ghc to have a function that accepts its 
> own output as its input so long as it does not utilize that piece of 
> output in generating itself. [...]
> 
> It seems though, if you try this same trick with two different 
> functions that rely on each others input and output, that [...] the
> generated program causes the stack to overflow as each function tries
> to force the other one to evaluate first and neither bows out
> releasing an output of promises so that the two functions can
> resolve.  [...]  I specifically refer to the linked function `oexn' (
> or-extracted-function-nodes ) that performs this feat.  Or would if
> the program worked after being compiled.

This has nothing to do with how many functions you have working with 
some input. The evaluation order of haskell expressions is induced by 
the data dependencies between haskell expressions. This work's fine as 
long as the data dependencies aren't circular.

For example

   numbers = 1 : map (1 +) numbers

works fine because the value of the i'th element of numbers depends only 
on the value of the (i-1)'th element of numbers, but not on it's own value:

   the first element is given as 1.
   the second element is the first element + 1, so it is 2.
   the third element is the second element + 1, so it is 3.
   and so on...

But

   infinity = 1 + infinity

doesn't work at all, because the value of infinity depends on it's own 
value.

> The code I reference is located at :
> 
> http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-sometimes.html

Your code contains the following definitions (among others):

> exn (c:_) n l = ( [ [ ( Just c , (n+1) ) ] ] , (n+1) )
> aexn (b:[]) n l = exn b n l 
> oexn (g:[]) n l = let ( ns , x ) = ( aexn g x l )
>                    in ( [] , ns , x )

The definition of exn says that the second component of exn's result 
depends on it's second argument. The definition of oexn feeds the second 
component of exn's result back as it's second argument. This creates a 
data dependency loop and the value of the third component of oexn is not 
defined.

Your code is actually similiar to my infinity example above.


Your code looks complicated, partly because you normalize some string 
representations instead of creating a domain specific algebraic data 
type. Wich aproach of the website you link to do you follow? Have you 
considered using a parser combinator library?

   Tillmann