[Haskell] Fwd: Mutually dependent functions
Tillmann Rendel
rendel at rbg.informatik.tu-darmstadt.de
Mon Jun 11 18:06:59 EDT 2007
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
More information about the Haskell
mailing list