Ответ 1
Существует много примеров построения исходных данных с помощью fix. Я недостаточно разбираюсь в общей теории, но кажется, что любой тип данных, подобный потоку, в котором вы всегда можете вывести еще одно значение с учетом потока до сих пор, можно вычислить с помощью fix без подавая ему тип функции.
Примеры
Самый простой пример (данный в ответе кактуса) - повторяющийся поток значений, например
x = [1, 1, 1, 1, 1, 1, 1, 1, ...]
Это удовлетворяет уравнению
(1:) x = x
и может быть произведено
>> fix (1:)
[1,1,1,1,1,1,1,1,1,1,...]
Несколько более сложный пример - натуральные числа
n = [0, 1, 2, 3, 4, 5, 6, ...]
которые удовлетворяют уравнению
0 : map (+1) n = n
и может быть произведено
>> fix ((0:) . map (+1))
[0,1,2,3,4,5,6,7,8,9,...]
Факторные числа могут быть сгенерированы наиболее легко, если мы посмотрим на пару (n,f), где f является n -ным факториальным числом -
x = [(0,1), (1,1), (2,2), (3,6), (4,24), (5,120), ...]
которые фиксированы, если взять пару (n,f) в (n+1, f*(n+1)), а затем cons (0,1) в начало списка. Таким образом, они могут быть сгенерированы с помощью
>> fix $ \xs -> (0,1) : map (\(n,f) -> (n+1,f*(n+1))) xs
[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720),(7,5040),...]
Число фибоначчи может быть сгенерировано аналогично, как и в user3237465.
Обобщение примеров
Все три примера здесь являются по существу рекурсивными функциями, преобразованными в корекурсивные потоки, т.е. они имеют некоторое начальное состояние s, а значения, испускаемые потоком, - это s, f s, f (f s) и т.д. для некоторой функции f. Общим методом для этого является функция iterate
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
который может быть определен в терминах fix -
iterate f x = x : map f (iterate f x)
= (x:) . (map f) $ iterate f x
= fix ((x:) . map f)
Таким образом, любой поток, который повторно применяет функцию к некоторому состоянию, можно записать в терминах fix (хотя, конечно, вы можете просто использовать iterate вместо fix - частный случай правила, fix не требуется на языке, который допускает рекурсивные выражения let).
Примеры без потока
Для примера, который не является потоком, рассмотрим бинарные деревья со значениями в ветвях -
data Tree a = Tip | Bin a (Tree a) (Tree a) deriving (Show)
Если нам нужно бинарное дерево, узлы которого помечены в первом порядке, обратите внимание, что мы могли бы исправить такое дерево, взяв две копии самого себя и увеличив все значения в левом и правом ветвях соответствующим количество, определяемое следующей функцией -
fun :: (Num a) => Tree a -> Tree a
fun t = Bin 1 (incr 1 t) (incr 2 t)
where
incr n (Bin a l r) = Bin (a+n) (incr m l) (incr m r)
where
m = 2 * n
Используя простую функцию takeLevels для отображения только начальной части дерева, мы вычисляем неподвижную точку как
>> takeLevels 3 $ fix fun
Bin 1 (Bin 2 (Bin 4 Tip Tip) (Bin 5 Tip Tip)) (Bin 3 (Bin 6 Tip Tip) (Bin 7 Tip Tip))
что мы хотели.