# [Haskell] Fwd: Mutually dependent functions

David House dmhouse at gmail.com
Tue Jun 12 05:51:40 EDT 2007

```   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.

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
```