Как мне использовать 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 является фиксированной точкой этой функции, она не является наименьшим в порядке следования доменов.

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

Для вида с высоты 10 000 футов 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 = fx, тогда мы можем подставить значение 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'sфакториальное объяснение это хорошо.Тип подписи исправления (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).Таким образом, fix принимает нашу функцию, которая 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, для вас нет бесконечных циклов или неопределенных.