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

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

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

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

Источник

3 ответа

Решение

Есть много примеров построения corecursive данных с 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.

Обобщая примеры

Все три примера здесь являются по существу рекурсивными функциями, преобразованными в corecursive потоки, т.е. они имеют некоторое начальное состояние 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))

что мы и хотели

Источник

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

repeat :: a -> [a]
repeat x = fix (x:)
Источник

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

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],

Источник
Другие вопросы по тегам