[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.
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
More information about the Haskell
mailing list