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

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 value x так что x = 1:x... так же, как мы определили выше. Как вы можете видеть из определения, fix это не что иное, как эта идея - рекурсия инкапсулирована в функцию.

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

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 Может ли шаблон соответствовать этой структуре и прекратить рекурсию, не заботясь о полном «значении» его параметра (?)

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

Факторное объяснение Томмда хорошо. Подпись типа Fix (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

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

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

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

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

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

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.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, нет бесконечных петлей или не определенных для вас.