[Haskell] Fwd: Mutually dependent functions

[David House]

   For example

      numbers = 1 : map (1 +) numbers

   works fine
   [snip]
   But

      infinity = 1 + infinity

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

Another nice way to think about this is in terms of fixed points. Remember that
an equation like:

 numbers = 1 : map (1 +) numbers

Is equivalent to a version using fix:

 numbers = fix (\ns -> 1 : map (1 +) ns)

So numbers gets assigned the fixpoint of the function \ns -> 1 : map (1 +) ns.
We can easily see that the list of positive integers [1, 2, 3...] is a fixpoint
of that function, because adding 1 to every element and sticking a 1 on the
front results in the positive integers again. On the other hand, the equation
for infinity:

 infinity = fix (1 +)

Results in infinity = _|_, because there is no fixpoint of the function (1 +)
(there is no number that, when you add one to it, results in that same number.)
Interestingly, though, if you define Peano natural numbers:

 data Nat = Z | S Nat

 -- For example:
 zero = Z
 one = S Z
 two = S (S Z)
 infinity = S infinity

Then infinity is _not_ _|_, but is in fact S (S (S ...)). This may not seem very
useful, but say we were to write an Ord instance for Nat:

 instance Ord Nat where
   Z   `compare` Z   = EQ
   S _ `compare` Z   = GT
   Z   `compare` S _ = LT
   S n `compare` S m = n `compare` m

(I.e. compare works by unwrapping S constructors from its two arguments and
seeing which one runs out first.) Then infinity serves as a value which is GT
than all other values.

-David House, dmhouse at gmail.com