Each data type in Haskell contains one element, which is usually "invisible". It's called "bottom" and denoted by (_|_). Naturally (_|_) of type Int and (_|_) of type Char are different; however, they are denoted as if they are the same, 'cause there isn't much difference between them. Anyway, if you try to calculate something which happens to be (_|_) and your program would throw an error or loop forever. Now, since there is (_|_)::Int and (_|_)::Char, there are also ((_|_), (_|_)) :: (Int, Char) as well as (1, (_|_)) :: (Int, Char) and ((_|_), 'a') :: (Int, Char); all of them are different from (_|_) :: (Int, Char). If a value contains (_|_) somewhere inside it, we say that it is less defined than the value obtained from it by replacing (_|_)s with something else. For example, (_|_) is less defined than ((_|_),(_| _)), which is less defined than (1, (_|_)) or ((_|_), 'a'); and both of them are less defined than (1, 'a'). 'fix' is a function which maps a function 'f' to the LEAST defined x such that f x = x. Such 'x' always exists; it could be (_|_), but it could be something else. For example, (^^2) is a strict function, which means that (_|_)^^2 = (_|_); therefore fix (^^2) = (_|_) - which you've discovered yourself. A stupid example: fix (\a -> (1, snd a)) = (1, (_|_)). (_|_) is not the right answer: (\a -> (1, snd a)) (_|_) = (1, snd (_|_)) = (1, (_| _)) which isn't (_|_). Another, less stupid example: fix (\a -> (1, fst a)) = (1, 1) - which doesn't contain (_|_) anywhere inside it. See, (_|_) is not the right answer here: (\a -> (1, fst a)) (_|_) = (1, fst (_|_)) = (1, (_|_)), which isn't (_|_). But (1, (_|_)) is not the right answer either: (\a -
(1, fst a)) (1, (_|_)) = (1, fst (1, (_|_))) = (1, 1).
On 19 Feb 2009, at 17:00, Khudyakov Alexey wrote:
Hello,
While browsing documentation I've found following function
-- | @'fix' f@ is the least fixed point of the function @f@, -- i.e. the least defined @x@ such that @f x = x@. fix :: (a -> a) -> a fix f = let x = f x in x
I have two questions. How could this function be used? I'm unable to imagine any. Naive approach lead to nothing (no surprise):
Prelude Data.Function> fix (^^2) <interactive>: out of memory (requested 2097152 bytes)
Second question what does word `least' mean?`a' isn't an Ord instance.
-- Khudyakov Alexey _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe