Как мне использовать fix, и как это работает?

Question

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

fix :: (a -> a) -> a
fix f = let x = f x in x

Как именно это возвращает фиксированную точку?

Я решил попробовать это в командной строке:

Prelude Data.Function> fix id
...

И там висит. Теперь, чтобы быть справедливым, это на моем старом macbook, который отчасти медленный. Однако эта функция не может быть слишком дорогой в вычислительном отношении, поскольку все, что передается в id, возвращает ту же вещь (не говоря уже о том, что она не потребляет процессорное время). Что я делаю неправильно?

Answer 1

Вы не делаете ничего плохого. fix id это бесконечный цикл.

Когда мы говорим, что fix возвращает наименьшую фиксированную точку функции, мы подразумеваем, что в смысле теории области. Так fix (\x -> 2*x-1) не собирается возвращаться 1потому что хотя 1 является фиксированной точкой этой функции, она не является наименьшей в упорядочении домена.

Я не могу описать порядок доменов одним или двумя абзацами, поэтому я отсылаю вас к ссылке на теорию доменов выше. Это отличный учебник, легко читаемый и довольно поучительный. Я очень рекомендую это.

Для вида с 10000 футов, fix является функцией более высокого порядка, которая кодирует идею рекурсии. Если у вас есть выражение:

let x = 1:x in x

Что приводит к бесконечному списку [1,1..]Вы можете сказать то же самое, используя fix:

fix (\x -> 1:x)

(Или просто fix (1:)), который говорит, что найди мне фиксированную точку (1:) функция, IOW значение x такой, что x = 1:x... так же, как мы определили выше. Как вы можете видеть из определения, fix это не что иное, как эта идея - рекурсия, заключенная в функцию.

Это действительно общая концепция рекурсии - вы можете написать любую рекурсивную функцию таким образом, включая функции, которые используют полиморфную рекурсию. Так, например, типичная функция Фибоначчи:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Может быть написано с использованием fix сюда:

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

Упражнение: расширить определение fix чтобы показать, что эти два определения fib эквивалентны.

Но для полного понимания читайте о теории предметной области. Это действительно классные вещи.

Answer 2

Я вовсе не претендую на то, что понимаю это, но если это кому-нибудь поможет... тогда иди.

Рассмотрим определение fix, fix f = let x = f x in x, Ошеломляющая часть заключается в том, что x определяется как f x, Но подумай минутку.

x = f x

Поскольку x = f x, то мы можем подставить значение x на правой стороне этого, верно? И потому...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

Таким образом, хитрость заключается в том, чтобы прекратить, f должен генерировать какую-то структуру, чтобы позже f может шаблон соответствовать этой структуре и завершить рекурсию, фактически не заботясь о полном "значении" ее параметра (?)

Если, конечно, вы не хотите делать что-то вроде создания бесконечного списка, как иллюстрировал Luqui.

Факторное объяснение TomMD - это хорошо. Тип подписи исправления (a -> a) -> a, Подпись типа для (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) является (b -> b) -> b -> b, другими словами, (b -> b) -> (b -> b), Таким образом, мы можем сказать, что a = (b -> b), Таким образом, исправление берет на себя нашу функцию, которая a -> aили действительно (b -> b) -> (b -> b)и вернет результат типа a, другими словами, b -> bиными словами, другая функция!

Подождите, я думал, что это должно было вернуть фиксированную точку... не функцию. Ну, это так, вроде (так как функции являются данными). Вы можете себе представить, что это дало нам окончательную функцию для поиска факториала. Мы дали ему функцию, которая не знает, как выполнить рекурсию (следовательно, одним из параметров для нее является функция, используемая для рекурсии), и fix научил его как рекурсировать.

Помнишь, как я это сказал f должен генерировать какую-то структуру, чтобы позже f образец может соответствовать и заканчиваться? Ну, это не совсем верно, я думаю. TomMD проиллюстрировал, как мы можем расширить x применить функцию и шаг к базовому случаю. Для своей функции он использовал if/then, и это является причиной прекращения. После многократных замен in часть всего определения fix в конце концов перестает быть определено с точки зрения x и это когда это вычислимо и завершено.

Answer 3

Вам нужен способ завершения точки фиксации. Расширяя ваш пример, очевидно, что он не закончится:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

Вот реальный пример использования исправления (обратите внимание, что я не пользуюсь исправлением часто, и, вероятно, я устал / не беспокоился о читаемом коде, когда писал это):

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, вы говорите! Ну, да, но здесь есть несколько действительно полезных моментов. Прежде всего, ваш первый fix Аргумент обычно должен быть функцией, которая является регистром 'recurse', а второй аргумент - это данные, по которым нужно действовать. Вот тот же код, что и для именованной функции:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

Если вы все еще в замешательстве, то, возможно, факториал будет более простым примером:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Обратите внимание на оценку:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

О, ты только что видел это? Тот x стала функцией внутри нашего then ветка.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

В вышесказанном вы должны помнить x = f xотсюда два аргумента x 2 в конце вместо просто 2,

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

И я остановлюсь здесь!

Answer 4

Одно четкое определение: вы могли бы тоже заново придумать исправление!

Answer 5

Насколько я понимаю, он находит значение для функции, так что выводит то же, что вы ей даете. Уловка в том, что он всегда будет выбирать неопределенный (или бесконечный цикл, в haskell, неопределенный и бесконечный циклы одинаковы) или любой другой, имеющий больше неопределенных. Например, с идентификатором,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

Как видите, undefined является фиксированной точкой, поэтому fix выберу это. Если вы вместо этого делаете (\x->1:x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

Так fix не могу выбрать неопределенное. Чтобы сделать его немного более связанным с бесконечными циклами.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

Опять небольшая разница. Так что же такое фиксированная точка? Давайте попробуем repeat 1,

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

Это то же самое! Поскольку это единственная фиксированная точка, fix должен остановиться на этом. сожалею fix, нет бесконечных циклов или неопределенных для вас.

Answer 6

Как указывали другие, каким-то образом отражает суть рекурсии. Другие ответы уже отлично объясняют, как это работает. Итак, давайте посмотрим под другим углом и посмотрим, как можно вывести обобщение, исходя из конкретной проблемы: мы хотим реализовать функцию факториала.

Давайте сначала определим нерекурсивную факториальную функцию. Мы будем использовать его позже, чтобы «загрузить» нашу рекурсивную реализацию.

      factorial n = product [1..n]

Аппроксимируем факториальную функцию последовательностью функций: для каждого натурального числа совпадает с до включительно . Явно сходится к бесконечности.

      factorial_0 n = if n == 0 then 1 else undefined
factorial_1 n = n * factorial_0(n - 1)
factorial_2 n = n * factorial_1(n - 1)
factorial_3 n = n * factorial_2(n - 1)
...

Вместо того, чтобы выписывать вручную для каждогоn, мы реализуем фабричную функцию, которая создает их для нас. Мы делаем это, выделяя общие черты и абстрагируя вызовы, делая их параметром фабричной функции.

      factorialMaker f n = if n == 0 then 1 else n * f(n - 1)

Используя эту фабрику, мы можем создать ту же сходящуюся последовательность функций, что и выше. Для каждогоfactorial_nнам нужно передать функцию, которая вычисляет факториалы доn - 1. Мы просто используемfactorial_[n - 1]с предыдущего шага.

      factorial_0 = factorialMaker undefined
factorial_1 = factorialMaker factorial_0
factorial_2 = factorialMaker factorial_1
factorial_3 = factorialMaker factorial_2
...

Если вместо этого мы передаем нашу реальную факториальную функцию, мы материализуем предел ряда.

      factorial_inf = factorialMaker factorial

Но поскольку этот предел является реальной факториальной функцией, мы имеемfactorial = factorial_infи поэтому

      factorial = factorialMaker factorial

Это означает, что это фиксированная точка .

Наконец, мы получаем функцию, которая возвращает данные. Мы делаем это, абстрагируясь и превращая это в аргументfix. (т.е.fсоответствует иfix fк ):

      fix f = f (fix f)

Теперь мы находимfactorialпутем вычисления неподвижной точкиfactorialMaker.

      factorial = fix factorialMaker