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

Ответ 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 эквивалентны.

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

Ответ 2

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

Рассмотрим определение 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). Таким образом, fix принимает нашу функцию, которая a -> a или действительно, (b -> b) -> (b -> b), и вернет результат типа a, другими словами, b -> b, другими словами, другую функцию!

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

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

Ответ 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 -->

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

Ответ 4

Одно четкое определение Возможно, вы снова изобрели исправление!

Ответ 5

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

λ <*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 не может выбрать undefined. Чтобы сделать его немного более связанным с бесконечными циклами.

λ <*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, нет бесконечных циклов или undefined для вас.