Полезные экземпляры "fix" на нефункциональных типах?

Каждый раз, когда я использовал fix :: (a -> a) -> a, это было в типе 

((a -> b) -> a -> b) -> a -> b

Для некоторых a и b. Существует ли на самом деле какое-то применение fix, где его параметр типа не является экземпляром типа функции, кроме такой тривиальной вещи, как fix (const 0)? Какова цель оставления подписи в самом общем виде?

3 10
haskell combinators recursion

3 ответа:

Есть много примеров построения корекурсивных данных с помощью 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)), а затем минусы (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) etc для некоторой функции 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))
Именно этого мы и хотели.
8

Я не знаю, считаете ли вы этот пример тривиальным, но вы можете использовать fix напрямую (без использования функции) для создания данных: 

repeat :: a -> [a]
repeat x = fix (x:)
10

Последовательность Фибоначчи, например: 

fibs = fix ((1:) . (1:) . (zipWith (+) <*> tail))

Или функция forever: 

forever x = fix (x >>)

Или другой вариант последовательности Фибоначчи: 

fibs :: State (Int, Int) [Int]
fibs = fix $ \loop -> do
    (x, y) <- get
    put (y, y + x)
    (x :) <$> loop

main = print $ take 15 $ fst $ runState fibs (1, 1)

Отпечатки [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610].

5